基于确定性重演的多核程序并发错误消除方法研究

Because of the nondeterminism of memory interleavings among threads, shared memory multi-core programs are prone to error. However, current concurrency bug processing methods are difficult to ensure the execution quality of multi-core programs. In order to solve this problem, we study concurrency bug eliminating methods based on deterministic replay. .Deterministic replay can replay multi-core programs correctly in the previous execution order, providing a new way to eliminate concurrency bugs. Based on deterministic replay, this study focuses on attribution abstracting, recording, filtering of interleaving traces and concurrency bug elimination. We first study dynamic abstracting methods for the code attributions corresponding to interleavings based on hardware to improve the performance. Then we study concurrent interleaving recording strategies with high efficiency for multi-core processors with snoop-based coherence protocol. In filtering interleaving traces, we study classification methods based on machine learning to filter the benign interleavings from traces. Considering the overhead, we study efficient anticipating strategies and bug avoiding methods based on hardware to eliminate concurrency bugs. Finally, we build a prototype system for concurrency bug elimination to implement performance evaluation. Our study has important significance for improving the production run quality of multi-core programs and multi-core bug processing architecture design.

共享内存的多核程序因为线程间内存交互顺序的不确定，极易发生并发错误，但现有错误处理方法难以确保程序的运行质量。为解决这一问题，本项目拟基于确定性重演原理，研究硬件实现的并发错误消除方法。.确定性重演能够实现程序重现以前的执行轨迹，为程序生产运行时的并发错误消除提供了新途径。本项目基于确定性重演，围绕交互特征提取、交互踪迹记录、交互踪迹过滤和并发错误消除四个方面展开研究。在交互特征提取方面，研究硬件支持的程序特征动态提取方法；在交互踪迹记录方面，考虑到应用前景，面向采用监听一致性协议的现代多核处理器，研究高效的并发式记录策略；在交互踪迹过滤方面，研究基于机器学习的交互顺序分类方法，过滤掉不影响程序执行结果的良性交互；在并发错误消除方面，研究硬件实现的低开销并发错误预测和避免方法；最后，构建原型系统并进行性能评测。本项目的研究对提高多核程序的运行质量和多核处理器错误处理结构设计具有重要的意义。

因为线程间的交互存在不确定性，多核程序的并发错误难以复现，导致诊断并发错误非常耗时且困难重重。现有调试和和测试阶段的并发错误处理方法难以暴露所有的线程间交互顺序，生产运行阶段的并发错误检测和消除是提高软件运行质量非常必要的补充。而确定性重演技术通过限制程序线程间的交互顺序，可以确保相同输入下程序的任意次执行结果都是一致的，在并发错误处理方面具有得天独厚的优势。因此，本项目基于确定性重演原理，研究多核程序生产运行阶段的并发错误的检测和消除方法，以提高软件在生产运行阶段的正确性。针对这一问题，本项目围绕内存竞争记录、交互踪迹提取和分类、交互踪迹过滤、确定性重演和并发错误消除这些个方面进行了深入研究，提出了一系列有效的解决方法。在内存竞争记录方面，从记录形式出发提出了并发式内存竞争记录方法，能够有效记录面向snoop协议的内存竞争，降低了硬件开销和日志尺寸；针对距离对内存竞争的影响因素，使用可重写滑动窗口保存并发竞争域内的内存操作，设计了基于滑动窗口的内存竞争记录方法，能有效记录更易引发错误的内存竞争。针对交互踪迹提取和分类，利用无序映射的散列表有序组织踪迹，缩小了错误检测的搜索空间，利用栈快速匹配交互不变量来标记线程交互。针对踪迹的过滤问题，分别从Image、Section、Instruction和Code四个级别去除不必要的监视存储器操作，设计了基于分层过滤的方法交互踪迹优化方法。针对确定性重演，采用稀疏线程切换点的策略实现了轻量级的并发错误记录和重放算法，减少记录规模，提升了确定性重放速度。针对并发错误的消除，使用滑动窗口技术实时预测并发错误拐点，有效的调节了多核程序内存竞争双方的执行顺序，避免了距离较近的内存竞争的发生。本项目所提出的算法为多线程程序的调试和测试供了有效的参考，推动多核程序调试领域及硬件调试支撑方面的进步，有助于进一步提升计算机系统的可靠性和容错性。