面向多线程程序的确定性并行关键技术研究

摘要

多核平台的普及扩大了对多线程程序的需求，然而多线程程序的编写、测试和调试一直是一个重大的研究挑战。其中一个关键的挑战是多线程程序的不确定性。程序可能会受到不确定线程交织的影响，产生不可预知的结果。确定性并行技术保证程序在相同的输入下总是被执行相同的线程交织，这极大地方便了多线程程序的调试，也使缺陷更容易重现。在确定性并行的多种实现方式中，基于运行时的确定性并行技术（即确定性执行技术）可以兼容现有的不确定性代码，因此成为当前的研究热点。确定性执行技术又可以概括地分为强确定性执行技术和弱确定性执行技术。强确定性执行技术允许程序有数据竞争，而弱确定性执行技术只能保证无数据竞争程序的确定性。
　　然而当前确定性执行技术仍然存在着实用性不强的问题。例如，强确定性执行技术的开销较大。弱确定性执行技术虽然开销较小，但是需要开发者预先消除程序的数据竞争。本文针对多线程程序开发阶段和运行阶段的不同特点，分别研究高效且具有良好可扩展性的强确定性执技术和弱确定性执行技术。
　　1）静态数据竞争检测的误报剔除技术。消除数据竞争是软件开发阶段的一项重要工作。静态数据竞争检测可以检测出所有可能的数据竞争，这不但可以使弱确定性执行技术的应用成为可能，还可以辅助强确定性执行系统减少插桩开销。然而，与其他程序分析工具一样，静态数据竞争检测也有较高的误报率。造成误报率过高的一个重要原因是静态分析方法往往过于保守地估计一个线程所能访问的内存范围。针对这个问题，我们提出线程例化（Thread Specialization）技术。线程例化可以静态地区分线程。通过在静态时就确定线程的数量和每个线程的ID，我们可以将并行程序转换成一个数据流和控制流都简化的版本。在这个例化后的程序上进行静态数据竞争检测，我们将得到更精确的结果。为了进一步减少误报，我们在线程例化的基础上提出了三个优化。懒惰调整（Lazy Adjusting）可以在数据流分析过程中延时调整动态多维数组的值；代码段分析（Code Region Analysis）和阶段分析（Phase Analysis）可以剔除大部分原先因为忽视happens-before时序关系而造成的误报。以上三个优化的结合平均可以减少77.8％的误报，同时可以减少57.9%的动态插桩点。
　　2）面向强确定性执行的程序分析技术。强确定性执行系统即使在有数据竞争存在的情况下也能保证确定性。当前，保证数据竞争确定性的一种常用方法是通过缓冲对共享内存的访问来隔离线程。但是缓冲所有共享访存的开销是相当大的。我们提出一种面向强确定性执行的静态分析技术 DRDet。我们认为不是所有对共享内存的访问都需要缓冲，事实上只需要缓冲与数据竞争有关的共享访存。所谓的与数据竞争有关的共享访存，包括所有可能的数据竞争，以及其他可能与这些数据竞争访问相同变量的访存操作。DRDet采用可靠的静态数据竞争检测工具来检测所有可能的数据竞争，并通过别名分析找到其他与数据竞争有关的共享访存。然而实验显示，别名分析的不精确性使得很大一部分共享访存被标记为与数据竞争有关。缓冲这些访存操作仍然会带来很大的性能开销。针对这个问题， DRDet采用了两个优化来减少用于查询别名分析的访存数量。我们在一个经典的强确定性执行系统上实现了DRDet静态分析。实验结果表明，DRDet在保持确定性和可扩展性的前提下将该系统的执行开销降低了1.6倍。
　　3）无全局同步的弱确定性执行技术。现有的弱确定性执行系统几乎都会在程序执行中引入额外的全局同步，影响了程序的性能和可扩展性。针对此问题，我们提出一种新的线程执行模式——令牌自由模式（Token-Free Mode）。处在令牌自由模式的线程会主动放弃得到的令牌，从而避免部分线程因为长时间占有令牌而造成其他线程等待。基于这种技术，我们实现了一个负载均衡的弱确定性运行时系统——LBDR（Load-Balanced Deterministic Runtime）。LBDR通过令牌自由模式来避免串行化，并且无需全局同步。实现结果表明，和经典的弱确定性执行系统Parrot相比，LBDR的性能提升了1.17倍。
　　4）面向流水线并行的确定性执行技术。现有的确定性执行系统在流水线并行程序上的效率普遍较低，主要的原因是确定性执行会打乱流水线并行程序的负载均衡。针对这个问题，我们在 LBDR系统中为程序员提供了一种性能指导语句——同步自由区（Synchronization-Free Sections）。同步自由区可以以一种确定的方式把令牌从同步密集线程向非同步密集线程转移。另外，针对流水线并行程序容易出现单线程执行的情况，LBDR可以在不破坏确定性的前提下动态消除单线程区内不必要的确定性调度操作。实验结果表明，我们的系统在流水线并行程序上的性能比Parrot平均提高了22.5%。

目录

声明

第一章 绪论

1.1 研究背景

1.2 相关研究

1.3 研究内容及贡献

1.4 文章结构

第二章 静态数据竞争检测的误报剔除技术

2.1 静态数据竞争检测的误报问题

2.2 线程例化

2.3 懒惰调整

2.4 Happens-before分析

2.5 评测

2.6 本章小结

第三章 面向强确定性执行的程序分析技术

3.1 强确定性执行系统的效率问题

3.2 系统设计

3.3 Loads-in-Quantum缓冲策略

3.4 评测

3.6 本章小结

第四章 无全局同步的弱确定性执行技术

4.1 弱确定性的全局同步问题

4.2 LBDR系统设计

4.3 令牌自由模式

4.4 LBDR系统实现

4.5 评测

4.6 讨论

4.7 本章小结

第五章 面向流水线并行的确定性执行技术

5.1 流水线并行的负载不均衡问题

5.2 面向流水线并行的确定性执行技术

5.3 评测

5.4 本章小结

第六章 结论与展望

6.1 工作总结

6.2 研究展望

致谢

参考文献

作者在学期间取得的学术成果