支持多核并行程序确定性重放的高效访存冲突记录方法  

High Efficient Memory Race Recording Scheme for Parallel Program Deterministic Replay Under Multi-Core Architecture

作　　者：刘磊[1,2] 黄河 唐志敏[1] 

机构地区：[1]中国科学院计算技术研究所计算机系统结构重点实验室,北京100190 [2]中国科学院研究生院,北京100049 [3]美普思科技有限公司,上海210021

出　　处：《计算机研究与发展》2012年第1期64-75,共12页Journal of Computer Research and Development

基　　金：国家"九七三"重点基础研究发展计划基金项目(2005CB321600;2011CB302500);国家自然科学基金重点项目(60736012);国家自然科学基金创新研究群体科学基金项目(60921002);国家"八六三"高技术研究发展计划基金项目(2009AA01Z103);国家杰出青年科学基金项目(60925009);北京市自然科学基金项目(4092044)

摘　　要：多核系统中并行程序执行过程的不确定性给程序调试带来了很大的困难.准确记录初始执行中冲突访存的次序是并行程序确定性重放的基础.提出了通过建立精确happens-before关系记录访存冲突的方法.此方法利用简洁高效的地址冲突检测机制确定冲突访存操作在执行中所处happens-before序关系的位置,可以抑制部分记录信息的产生,从而有效减少记录信息.与其他方式方法相比,可以进一步压缩17%的记录条数.采用逻辑向量时钟描述冲突访存操作间的happens-before关系,与采用标量时钟相比,可以避免happens-before关系的误识,降低重放执行时并行度的损失.Current shared memory multi-core and multiprocessor systems are nondeterministic.When these systems execute a multithreaded application,even if supplied with the same input,they could produce a different output each time.It frustrates debugging and limits the ability to properly test multithreaded code,and is becoming a major stumbling block to the much-needed widespread adoption of parallel programming.The support for deterministic replay of multithreaded execution is greatly helpful in finding concurrency bugs.A memory race recording scheme,named Rainbow,is proposed.Its core idea is to make inter-thread communications fully deterministic.The unique feature of Rainbow is that it precisely sets up happens-before relationships between conflicting memory operations among different threads.By using effective,bloom-filter based,coherence history queue,Rainbow removes redundant happens-before relations implied in the already generated log and enables a compact log.Rainbow adds the modest hardware to the base multi-core processors,and the coherence protocol is unmodified.The analysis results show that Rainbow reduces the log size by 17% of a state-of-the-art scheme,and the records execution speed is similar to that of release consistency（RC） execution and replays at about 93% of its speed.The determinism can be provided with little performance cost using our architecture proposals on the state-of-the-art hardware,and the software-only approaches can be utilized on existing systems without problem.

关 键 词：确定性重放 缓存一致性协议 访存冲突 多核 并行程序 

分 类 号：TP303[自动化与计算机技术—计算机系统结构]