确定性并行技术研究

As threads often race to access shared memories and resources, parallel programs are inherently nondeterministic, which indicates that multiple executions of the same program under the same input may produce different outputs. Nondeterminism brings challenges in many aspects such as programming, debugging, testing and fault tolerance, thus it greatly reduces the reliability of parallel programs and even cause the reliability wall. The technique of Deterministic multithreading (DMT) makes output only related to input by controlling shared memory accesses of threads. Deterministic multithreading could solve the above problems thoroughly, thus bringing new opportunities to parallel computing. However, current DMT implementations may not be compatible to legacy codes or incur prohibitive time & space overhead, which damages their practicability. To solve these problems, this project plans to investigate on approaches for improving DMT. The major work of this project is to optimize deterministic runtime in compatibility and time & space overhead. To further improve DMT, this project also plans to apply a variety of optimizations, including performing program analysis, using hardware supports and designing a determinism-oriented programming model. By these researches, this project is expected to improve the practicability of deterministic multithreading, and thus supports parallel computing.

由于线程之间对共享内存和资源的竞争访问，并行程序的执行普遍存在着不确定性问题，即程序在相同输入下多次执行可能得到不同的结果。不确定性给并行程序在开发、调试、测试和容错等方面带来了挑战，严重降低了并行程序的可靠性，甚至导致可靠性墙问题。确定性并行技术通过控制线程对共享内存和资源的访问，使程序的执行结果仅依赖于输入。确定性并行技术能够从根本上解决目前并行程序存在的诸多问题，给并行程序的发展带来了新的机遇。然而目前确定性并行技术还存在着性能开销过大、兼容性差等方面的问题，制约了确定性并行技术的实用化。针对这些问题，本课题将以确定性运行时技术为核心展开研究，重点研究确定性运行时技术的兼容性优化和时空优化；同时分别从程序分析技术、硬件支持技术和编程模型等多个层次展开研究，为确定性运行时技术提供更大的优化空间。通过这些研究推动确定性并行技术的实用化，为并行程序的持续发展提供技术支撑。

课题在已有工作的基础之上，进一步提出了面向多核并行程序的确定性懒惰释放一致性实现方法和一种快速的全系统模拟器确定性回放方法，对于解决确定性运行时的时空开销问题以及兼容性问题起到了关键性的作用。课题围绕着确定性运行时技术在程序分析、硬件支持技术和编程模型等方面进一步展开研究，在静态数据竞争检测的误报剔除技术，基于程序切片的并行错误检测技术、基于程序例化的面向强确定性执行的程序分析技术，无全局同步的弱确定性执行技术以及基于硬件虚拟化的进程级确定性执行环境等方面也取得了进展和突破。通过这些技术的研究，在一定程度上推动了确定性运行时系统的实用化，完成了课题制定的研究目标。