Deterministic Message Passing for Distributed Parallel Computing

Kai LU
Xiaoping WANG
Wenzhe ZHANG
Gen LI

IEICE TRANSACTIONS on Information and Systems   Vol.E96-D    No.5    pp.1068-1077
Publication Date: 2013/05/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E96.D.1068
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
determinism,  message-passing,  debugging,  distributed computing,  

Full Text: PDF>>
Buy this Article

The nondeterminism of message-passing communication brings challenges to program debugging, testing and fault-tolerance. This paper proposes a novel deterministic message-passing implementation (DMPI) for parallel programs in the distributed environment. DMPI is compatible with the standard MPI in user interface, and it guarantees the reproducibility of message with high performance. The basic idea of DMPI is to use logical time to solve message races and control asynchronous transmissions, and thus we could eliminate the nondeterministic behaviors of the existing message-passing mechanism. We apply a buffering strategy to alleviate the performance slowdown caused by mismatch of logical time and physical time. To avoid deadlocks introduced by deterministic mechanisms, we also integrate DMPI with a lightweight deadlock checker to dynamically detect and solve these deadlocks. We have implemented DMPI and evaluated it using NPB benchmarks. The results show that DMPI could guarantee determinism with incurring modest runtime overhead (14% on average).