作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2008, Vol. 34 ›› Issue (17): 274-275,. doi: 10.3969/j.issn.1000-3428.2008.17.098

• 开发研究与设计技术 • 上一篇    下一篇

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

廖名学,何晓新,范植华   

  1. (中国科学院软件研究所,北京 100080)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2008-09-05 发布日期:2008-09-05

Static Detection Algorithm of Deadlock in MPI Synchronization Communication Sequential Model

LIAO Ming-xue, HE Xiao-xin, FAN Zhi-hua   

  1. (Institute of Software, Chinese Academy of Sciences, Beijing 100080)
  • Received:1900-01-01 Revised:1900-01-01 Online:2008-09-05 Published:2008-09-05

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

关键词: MPI程序, 算法, 死锁, 静态分析

Abstract: Detecting deadlocks in MPI synchronization communication programs is very difficult, which needs building program models. All complex models are based on sequential models. The sequential model is mapped into a set of character strings and its deadlock detection problem is translated into an equivalent multi-queue string matching problem. An algorithm is devised and implemented to statically detect deadlocks in sequential models of MPI synchronization communication programs. This algorithm is better than usual circle-detection methods and can adapt well to dynamic message stream.

Key words: MPI, algorithm, deadlock, static analysis

中图分类号: