MPICH同步通信程序死锁检测研究

MPI是分布式内存并行处理计算机上开发基于消息传递应用系统的事实标准，主要用于并行计算机和集群的高性能运算，MPICH是其重要实现。MPI程序可能发生死锁，而且调试困难，国际上主要采用运行时动态调试方法。但是，这些方法的致命缺陷是发现死锁后，死锁造成的损失已无可挽回；况且，它们无法用于全节点空间上。为解决这些问题，针对MPICH点对点同步通信程序，本文提出了一种静态方法。 根据静态方法程序建模的需要，开发了一种基于JavaCC技术的编译器前端工具，该工具对MPICH程序进行编译产生程序语法树。 提出一种MPICH同步通信程序的建模方法，并设计出一种模型构造器遍历语法树来构造模型。根据程序性质，模型构造器可构造出三种模型：无参数模型，一次参数化模型和二次参数化模型。无参数模型不含任何参数；一次参数化模型含有一个并行节点ID的参数；二次参数化模型含有并行节点ID以及并行节点数量两个参数。构造出一种优化算法将全节点空间上的一次参数化模型转化为无参数模型之后进行死锁判定；对二次参数化模型，采用穷举方法转化为无参数模型后进行死锁判定。 针对非对称条件程序死锁性质的不确定性，提出对称条件假设。根据该假设，无参数模型被转化为循环嵌套模型之后再进行死锁判定。 为提高循环嵌套模型死锁判定效率，提出比例方程组概念。设计出建立并求解比例方程组的线性时空复杂度算法。比例方程组无解有两种情况：比例方程组包含第一类或者第二类比例冲突。提出比例冲突相关的方法，在常数时间内通过分析循环模型中产生冲突的几个循环的循环次数是否满足死锁条件来判断死锁。在比例方程组有解的情况下，给出了一种算法截取该模型的常数个循环片断进行死锁判定。为对循环片断进行死锁判定，开发了一种线性时空复杂度算法将片断顺序化后进行死锁判定。 为进一步提高算法效率，对Java哈希表类库进行了优化，使该库能够完全避免由于存取比例数据而产生的哈希碰撞。 理论证明，实验表明，该方法能够在运行前，最坏情况下以线性时空复杂度，判定点对点MPICH同步通信程序在全节点空间的死锁性质。