全节点空间MPI同步通信死锁检测

Deadlock Detection in MPI Synchronization Communication Through Whole Node Space

针对全节点空间上MPI同步通信程序死锁检测的现有穷举方法的弱点,提出了该场景中MPI程序的两种参数化模型:一次参数化模型和二次参数化模型。通过分析一次参数化模型的一类不变式的性质,给出了该模型的死锁检测算法。提出了同构节点空间的一系列概念和性质并由此设计出该算法的几种优化方法,以加快某些特定程序模型死锁检测的过程。仿真实验表明该算法及其优化方法比现有方法的性能提高若干数量级。

Aiming at the deficiency of current exhaustive methods for deadlock detection in MPI synchronization communication programs through whole node space, two parameterized models were proposed to describe MPl programs in such scene： one-parameter model and two-parameter model. Based on the analysis on properties of a type of invariant in one-parameter model, an algorithm was proposed to detect deadlocks in such model. A series of concepts and properties of isomorphic node space were proposed and thus some methods were devised to optimize this algorithm to accelerate the process of deadlock detection in some special program model. Simulation experiments show that the performance of this algorithm and its improved methods are over about some orders of magnitude higher than that of the current methods.