面向多核/众核体系结构的确定性并行关键技术研究

摘要

如今多核已经逐渐取代单核成为当今CPU的主流，未来CPU可能集成更多的核，进入众核时代。然而，随着并行度的增加，并行程序的开发和维护成本也在相应增加。在并行程序中，由于数据竞争、同步竞争、消息竞争等因素的影响，程序在给定的输入下多次运行可能会产生不同的结果,这就是并行程序的不确定性。不确定性是并行程序的一种基本属性，它导致并行程序的缺陷不能充分暴露且不可复现，进而使得并行程序在开发、调试、测试、入侵检测、容错等领域都要比其串行版本要困难得多。为了解决这个问题，近些年学术界提出了确定性并行技术。确定性并行技术的目标是使并行程序在给定的输入下运行，总能得到相同的执行路径和输出结果。这样就可以将并行程序的复杂性简化到和串行程序一样的水平，因此会极大地降低并行程序的开发和维护成本。然而，目前的确定性并行技术还存在着很多问题。例如硬件支持的确定性并行系统存在着移植性问题，并且目前没有真实的硬件实现。纯软件实现的确定性并行系统开销十分巨大。此外，确定性并行系统在可扩展性、稳定性、确定性等方面都存在着不同程度的问题。本文的目的是面向多核/众核体系结构，研究与之适应的确定性并行技术，实现高效可用的确定性并行运行时系统。本研究主要内容包括：
　　⑴全并行的确定性控制技术。针对目前线程级确定性并行系统存在的并行度低下的问题，我们研究了全并行的确定性控制技术。该技术解决了一个关键技术问题，即在不弱化确定性目标和内存一致性的前提下，如何最大限度地开发确定性并行系统的并行度。为此，我们引入了确定性同步点，通过在同步点中利用内存拥有权交换技术代替串行执行技术来解决访存冲突，消除不确定性，从而在不牺牲确定性和内存一致性的前提下提升了系统并行度。在此基础上，我们还根据线程之间的通信频率来动态地调节所插入的同步点密度。这样我们就可以平衡同步点的开销和同步点开发的并行度所获得的性能提升。基于这个技术，我们设计和实现了纯软件的FPDet确定性系统。实验表明，和同类的确定性系统DMP（同样保持强确定性和顺序一致性）相比，FPDet系统性能提升了约40％。
　　⑵确定性消息传递技术。确定性消息传递技术研究面向的是进程级并行，解决多个进程协同运行时的不确定问题。消息传递模型如MPI是进程级并行中普遍使用的一种同步和通信方法。针对MPI模型中存在的混杂消息传递和异步消息传递操作所引起不确定性问题，我们通过引入逻辑时钟，利用确定性消息等待技术和确定性消息映射技术解决上述问题，并利用缓冲机制和死锁检测机制来缓解和消除死锁，实现了进程级并行的确定性控制。我们实现了DMPI确定性消息传递运行时系统，在NPB测试程序集上的实验表明，DMPI系统性能损失只有大约14%。
　　⑶无全局同步的确定性并行技术。目前强确定性系统无一例外使用全局同步来消除不确定性，然而全局同步会带来正确性、性能和可扩展性等方面的问题。为了解决这个问题，我们提出了一种新的内存一致性模型DLRC(Deterministic Lazy Release Consistency)。DLRC模型将线程内存修改对于其他线程的可见性推迟到线程同步时，并保证线程能看到一个内存修改当且仅当该内存修改依据同步所引起的happens-before时序关系发生在线程当前执行的指令之前。DLRC模型能够限制数据竞争，使得数据竞争的结果依赖于happens-before关系，即同步语句的顺序。同时DLRC仅仅利用了程序自身定义的同步，而不引入额外的全局同步。在此 DLRC模型的基础之上，我们利用弱确定性技术消除同步语句竞争，实现了一个无全局同步的强确定性系统RFDet。实验表明，和目前最快的纯软件确定性系统DThreads相比，RFDet性能提升了近一倍。
　　⑷目前的确定性技术依然是学术界的研究热点，并且技术逐渐走向成熟和实用。我们的研究同时支持进程级并行和线程级并行两级并行，实现了一套高效的面向多核/众核体系结构的确定性解决方案。实验表明，本文提出的这些技术和方法是有效的，通过这些技术和方法，我们将确定性并行技术的研究向前推进了一步，使得确定性并行系统的性能和可用性有了很大程度的提高。

目录

封面

声明

目录

中文摘要

英文摘要

第一章 绪论

1.1 研究背景

1.2 研究内容及贡献

1.3 文章结构

第二章 相关研究

2.1 确定性运行时技术

2.2 其他确定性并行技术

2.3 记录-回放技术

2.4 确定性并行系统评价

第三章 全并行的确定性控制技术

3.1 FPDet系统设计

3.2 自适应的轮长度调节机制

3.3 FPDet实现技术

3.4 评测

3.5 讨论

3.6 本章小结

第四章 确定性消息传递技术

4.1 MPI的不确定性因素

4.2 确定性消息传递技术

4.3 优化

4.4 评测

4.5 本章小结

第五章 无全局同步的确定性并行技术

5.1全局同步问题

5.2 设计思想

5.3 DLRC模型

5.4 DLRC模型的软件实现

5.5 确定性同步顺序

5.6 RFDet实现细节和优化

5.7 评测

5.8 讨论

5.9 本章小结

第六章 结论与展望

6.1 工作总结

6.2 研究展望

致谢

参考文献

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