共享存储多核系统中的确定性重放机制研究

在共享存储多核系统中，并行程序往往存在对共享内存的冲突访问，从而导致程序每次执行的路径不尽相同，这种不确定性是并行程序调试中的一个主要障碍。通过硬件支持使得并行程序每次执行路径一致，即实现确定性重放是解决该问题的有效方法。本课题研究如何在共享存储多核系统中高效地支持确定性重放，主要研究内容包括：（1）如何使得访存记录数量少，研究通过建立精确的访存依赖关系来抑制访存记录信息的产生，以减少记录条数；（2）如何使得重放执行速度快，研究通过记录偏移逻辑时钟的方法来减少重放时的并行度损失，以提高重放执行速度；（3）如何使得硬件结构简单，研究利用Bloom-Filter机制来高效记录访存信息，以降低硬件逻辑开销。通过上述三方面的研究，本课题将提出一种访存记录数量少、重放执行速度快、硬件逻辑结构简单的确定性重放机制，以高效地支持并行程序调试。

本课题研究了共享存储多核系统中并行程序的确定性重放问题，针对目前系统的不足，提出了基于高效硬件辅助的并行程序确定性重放方法，降低系统中存储日志开销的方法、提高重放执行的速度。具体而言，本研究的主要创新点及贡献包括：. （1）减少访存记录的方法. 为了解决系统级重放方法不能有效地辅助应用程序员调试多线程并行程序，本课题研究了面向用户态多线程并行程序的硬件辅助的确定性重放方法。与实现系统级重放相比，重放用户态并行程序存在两个挑战：第一，在多任务的系统中用户态程序的外部执行环境复杂，硬件检测到的依赖关系可能来自系统程序或其它的任务，对重放被监控的用户态程序而言，这些依赖关系是多余的；第二，除了程序的外部输入与程序内的访存依赖关系，重放用户态并行程序存在由上下文切换与系统调用之间的数据共享产生的依赖关系，本课题称之为隐式依赖关系，这类关系与核心态代码有关，监控复杂。.针对上述挑战，我们提出了依赖关系过滤机制与隐式依赖关系的检测与记录方法，该方法通过软件协助来记录信号、系统调用与操作系统调度相关的序关系。. （2）提高重放执行速度的方法. 为了降低日志的存储开销，本课题研究了记录过程中的访存依赖关系约减方法，提出了利用逻辑时间内的定序关系约减访存依赖的方法。首先，为了达到最佳的依赖关系约减效果，本项研究建立了全局同步的逻辑时间，为了降低同步日志的存储开销，提出了一种懒惰的逻辑时钟同步方法，此外针对本课题提出的访存依赖约减方法，分别基于目录的缓存一致性协议与侦听的缓存一致性协议，提出了相应的逻辑时间同步算法。. （3）高效的硬件结构支持. 针对本课题中提出的上述方法，我们设计了相应的硬件支持方案，主要解决以下问题：（1）如何通过硬件管理程序的访存地址，（2）如何通过硬件管理逻辑时间。模拟评估结果表明，本研究所提出的方法所增加的运行时开销仅为9%。在顺序一致性模型下，每执行千条指令所记录的访存依赖关系的存储开销为0.11 Bytes。此外，分别在4核、8核、16核模拟平台上评估本课题所提出约减方法的可扩展性，实验结果表明每执行千条指令的平均存储开销分别为0.14、0.15、0.06 Bytes，其中最大值是平均值的4倍。