论文部分内容阅读
多核处理器的发展使得并行编程越来越流行。但是并行程序执行行为的不确定性，使得它们中存在错误难以测试和调试，这给程序员的工作带来巨大的困难和挑战。而且，隐藏在并行程序中的错误可能会给用户带来严重的影响。 因此，若干研究针对于如何提高并行程序的正确性，其中并行程序的错误重现能够有效的帮助程序员进行调试，是提高并行程序正确性的重要手段。在并行程序的错误重现中，如何高效的确定各个线程对于共享内存访问的顺序是最重要的问题。因此，本文的研究集中于如下两个方面:(1)识别并行程序中的同步操作，利用同步操作包含的顺序关系确定部分线程间共享内存访问的顺序;(2)利用商业处理器提供的局部时钟，高效的确定线程间共享内存访问的顺序。本文的贡献主要包括以下几点: 本文提出了基于程序行为的动态同步识别技术。该方法通过控制并行程序的执行，利用前向测试和后向测试两种算法来识别其中的同步操作，同时排除由于长延迟操作和锁操作造成的干扰，并通过降低测试线程数量以及降低测试点的数量优化算法的执行效率。本文在同步识别系统SyncTester中实现了上述各项技术，并通过与动态同步识别系统ISSTA08、Helgrind+系统进行比较，说明本文的技术能够更有效的识别并行程序中的同步操作。 本文提出了计算处理器核间局部时钟差值区间的方法。为了利用局部时钟确定线程间共享内存访问的顺序，必须确定核间局部时钟的差值。本文设计了程序测试和统计测试两种方法计算核间局部时钟差值的区间。其中程序测试方法可以得到必然包括该局部时钟差值的一个区间，而利用统计测试的方法，能够在极高的置信度的条件下，将核间局部时钟差值的区间缩小到10个周期以内。 本文提出了一种基于局部时钟的线程间共享内存访问的定序方法。在该方法中，并行程序的各个线程在执行过程中只需要记录局部时钟的值和少量线程私有信息，无需线程间同步操作，有效地降低了运行时开销;同时在离线分析阶段，利用局部时钟带有的时间信息，能够有效的推导线程间操作的顺序，降低离线分析开销。本文将该技术应用到两个著名的并行程序错误重现系统PRES和CLAP，降低了PRES系统1％～85％的运行时记录开销而没有影响它的错误重现能力，降低CLAP系统84.66％～99.99％的求解开销同时在绝大部分情况下仅额外带来不超过10％的运行时开销。