MPI程序同步通信基本模型死锁检测

本文提出了MPI程序的同步通信模型及三个基本简化模型,给出了判定这些基本模型是否死锁的方法和定理并予以了严格证明.简化模型的死锁检测理论和方法是真实MPI程序死锁检测的必要基础.这些方法基于程序静态分析,必要时进行运行时检测,它们对两种简化模型可以在程序编译前确定是否死锁,对另外一种模型,在编译前可静态确定部分死锁,运行中可确定其他死锁.我们的理论可以证明MPI程序死锁检测主流算法的正确性,其方法可以减少它们对客户源代码或MPI profiling接口的修改量,从而大大降低死锁检测开销,并可在运行前判定死锁.

MPI同步通信顺序模型死锁静态检测算法

静态检测MPI程序同步通信死锁比较困难,通常需要建立程序模型.顺序模型是其他所有复杂模型的基础.通过一种映射方法将顺序模型转化为字符串集合,将死锁检测问题转化为等价的多队列字符申匹配问题,从而设计并实现了一种MPI同步通信顺序模型的静态死锁检测算法.该算法的性能优于通常的环检测方法,并能适应动态消息流.

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

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

基于初等运动的多机器人避碰及死锁预防

该文以一实际应用为背景提出了多移动机器人避碰及死锁预防算法 ,该算法将机器人的运行环境形式化地描述为初等运动集、冲突图、总任务集及机器人作业集 ,利用集合论、图论的有关方法及技术实现了多机器人间的避碰与死锁预防 .当机器人的运行环境改变时 ,只需要对相应的集合描述文件进行修改 ,而不用对程序做任何改动 .算法的另一个特点是利用避碰算法巧妙地完成了死锁预防 .仿真和实际运行证明了该算法高效可靠 .

柔性制造系统中死锁避免的充要条件第二部分：资源的动态分配规则

本文根据在第一部分中推导出来的描述资源竞争的着色ＲＯＰＮ给出在柔性制造系统中无死锁运行的充分必要条件，从而得出相应的控制规律。它是一种资源动态分配的策略，它决定当一个资源空闲时，是否可以分配给一个任务，可以的话先分配给谁，以保证系统无死锁，并使得资源利用率最大。

柔性制造系统中死锁避免的充要条件第一部分：资源竞争过程的建模

柔性制造系统的主要特点是多种不同类型的工件同时在系统中加工，这些工件竞争系统的有限资源，导致象系统死锁等这样的不希望事件的发生，本文用一种Ｐｅｔｒｉ网模型，称之为着色面向资源的Ｐｅｔｒｉ网（着色ＲＯＰＮ）来描述系统中的这一竞争过程；这一模型揭示了资源竞争过程的本质特点，从而为寻求死锁避免的充要条件提供了基础。