课题负责人：刘淘英
起止时间：2001年9月—2003年9月

　　本课题集中于解决消息传递与软件DSM程序的并行调试问题，研究消息传递并行程序和软件DSM并行程序的行为模式、调试方法和实现技术，通过整合两种编程模型的并行调试技术，建立通用的并行调试模型，设计支持两种编程模式的通用并行调试器。具体如下： ①针对软件DSM程序的并行调试技术，包括动态数据竞争检测； ②针对消息传递程序的并行调试技术，包括消息流向分析； ③两者都适用的并行调试技术，包括全局断点、重放技术、渐增检查点技术； ④整合两种编程模型的并行调试技术，设计通用的并行调试器。

研究目标

　　从理论上研究和分析消息传递并行程序和软件DSM并行程序的行为模式、调试方法和实现技术研究内容：本项目主要研究消息传递型和软件DSM型并行程序的调试技术。研究工作分两个部分，第一部分侧重研究消息传递并行程序和软件DSM并行程序的特殊行为模式、调试方法和实现技术，第二部分研究通用并行调试技术。

　　1. 消息传递型程序的并行调试技术消息流向分析： 消息发送和接收的不匹配是消息传递并行程序容易出错的地方。send、receive可以直接从源码中检查，但有些隐蔽的发送如广播等容易被疏漏，因而造成程序的异常行为。我们的研究是由程序源码发现消息传递流向结构，进行分析，找出错点。不正确的同步消息语句会引起死锁，而异步消息的发送接收缓冲区可能会在系统还没有使用完毕时就被用户覆盖。

　　2. 软件DSM的并行调试技术数据竞争的动态检测：对于基于共享存储器编程模型的并行程序，存在数据竞争情况。数据竞争是指针对同一个共享变量的两个操作（其中至少有一个是写操作）之间没有用同步语句隔开。数据竞争一般是由于错误的同步造成的，比如缺少必要的同步语句或同步语句的位置错误，并且这样的错误造成程序运行的不确定性，因此很难调试。利用程序静态分析数据相关性发现数据竞争问题被证明是NP-完全问题，效果不是很好。我们的研究内容就是在虚拟共享存储系统平台上，实现对虚拟共享变量的运行时数据竞争检测。由于软件DSM系统通过高速缓存一致性协议来维护共享存储器的一致性，在设计动态竞争检测机制时可以利用高速缓存一致性协议提供的一些信息来减少开销。全局断点：一旦到达一个用户感兴趣的点（即断点）时，让并行程序的所有进程停下来，然后通过检查进程的状态来找出错误原因。主要有以下问题：①如何在并行程序中正规定义断点条件？②如何检查断点条件是否满足？由于软件DSM程序实际上是由多个分布在不同机器上的进程组成的分布式程序，一个断点条件可能需要多个进程同时满足某个条件时才触发，因此需要有分布式算法来检查断点条件是否满足；③一旦到达断点后，如何让并行程序的所有进程停到一个全局一致状态，并能继续恢复执行?由于存在通信延迟，分布式程序恰好停在一个全局一致状态是很困难的；④如何定义这个全局一致状态?用户应该很容易能根据一个全局一致状态来推断程序的行为，定位程序错误位置。

　　3.通用并行调试技术设计实现基于消息传递的应用的并行调试器和基于软件DSM应用的并行调试器，并整合这两种不同模式的并行程序调试方式，形成通用的并行调试器。主要的研究重点在于①如何表示并行应用；②断点、应用程序并发执行等的表示；③全局共享空间在调试器中的表示；④消息传递的表示与网络负载的表示；⑤应用中两种不同模式同时使用在调试器中的表示。

　　此外还要研究其它在并行调试中非常重要的技术：

　　重放技术：调试并行程序的一个固有问题是并行程序执行具有不确定性，也就是说，对于同样的输入，程序的两次执行可能不一样。传统的循环调试（cycle debugging）方法是利用程序执行的确定性来定位错误的，因此在调试并行程序时不能使用。针对消息传递系统和软件分布式共享存储系统，根据获得同步变量来的次序来定义重放概念，并提出实现重放的方法。
检查点：检查点方法在程序运行时，将一些信息记录到稳定的外存储器中，在程序发生错误恢复时，从记录下来的信息中恢复出一个一致状态，然后程序从这个一致状态恢复执行。检查点技术与重放技术结合可以实现渐增重放。渐增重放方法使程序不需要从头开始执行，只需要后退到错误位置之前重新执行即可。通过利用检查点得到的一致状态，然后在通过记录一些信息，可以实现从一个检查点之后开始重放。通过在消息传递应用和软件DSM系统上研究一般重放技术，然后进一步结合检查点技术是很有意义的。