面向多核处理器确定性重演的内存竞争记录机制研究

摘要

随着多核处理器的流行,共享内存多线程程序成为挖掘多核处理器系统并行性的重要手段。然而,共享内存多线程程序在执行时存在不确定性,即在相同输入下,同一程序在同一台多核处理器系统上运行多次,运行的结果可能会不同。这种执行时的不确定性给共享内存多线程程序的编写、调试和应用等都带来了很大挑战。
　　划分为记录和重演两个阶段的确定性重演机制是解决共享内存多线程程序执行不确定性的有效手段。确定性重演机制通过在记录阶段记录程序运行时存在的不确定性信息,在重演阶段使用所记录的不确定性信息强迫程序再现原始的执行结果。内存竞争作为不确定性信息的主要来源,记录的信息量大、记录时带来的开销大,使得内存竞争记录成为实现多核处理器确定性重演的关键。本文研究高效的、硬件实现的内存竞争记录机制,针对当前硬件实现的内存竞争记录机制面临的挑战,力求在内存竞争日志、硬件资源消耗、带宽开销、重演速度等方面取得好的研究成果。
　　首先,本文提出了分段式内存竞争记录机制。点到点的内存竞争记录方式在重演方面具有优势,具有良好的应用前景,但其硬件实现带来了较大的硬件资源消耗。因此,本文开展了低硬件消耗的点到点内存竞争记录方式的研究,提出了支持并发重演的分段式内存竞争记录机制。该机制用当前发生序—冲突发生时冲突双方所在处理器核的当前指令计数值构成的依赖关系表示冲突,无需保存冲突双方对应内存操作的指令计数值;采用分段的可推导约减算法,约减掉可以被已记录的当前发生序推导出来的冲突;对于已被替换出cache的内存块对应的冲突,则使用最大近似段时戳法进行检测。在硬件实现中,该机制为每个内存块存储一个用具有更小尺寸的段号标记的cache块时戳,降低了硬件消耗;同时,采用间隔指令计数值替换指令计数值,进一步优化了内存竞争日志。仿真结果表明,该机制带来的硬件消耗低,也减小了内存竞争日志,降低了带宽开销。
　　其次,本文提出了基于签名的循环式内存竞争记录机制。通过在cache中增加时戳字段实现内存竞争记录功能,会影响系统原有的cache结构,给多核处理器的设计带来很大挑战。因此,为了所添加的内存竞争记录功能不影响原有系统的cache结构,本文研究了基于签名的循环式内存竞争记录机制。签名是一种高效的硬件实现机制,在内存竞争检测方面可以获得较好的时间和空间效率。该记录机制仅为每个处理器核添加若干个小尺寸的读签名和写签名,通过使用签名的插入和查找操作实现冲突的检测,在无需更改原有cache结构的同时,进一步降低了硬件消耗。在此基础上,该机制又采用循环发生序约减连续同向的当前发生序,在能够实现并发确定性重演的前提下,进一步优化了内存竞争日志。在硬件实现中,该记录机制采用一种简洁的方向检测机制检测连续同向的当前发生序,无需添加太多额外的硬件资源就可以实现循环发生序的记录。仿真结果表明,该机制相比已有的点到点内存竞争记录机制,在无需更改原有cache结构的前提下,硬件消耗、内存竞争日志和带宽开销都得到了很大改善。
　　第三,本文提出了同步敏感的内存竞争记录机制。内存竞争只是内存冲突的一部分,也并非所有的内存竞争都影响确定性重演,因此,如果在内存竞争记录时过滤掉不影响确定性重演的冲突,将会有效减小内存竞争日志。因此,本文研究了同步敏感的内存竞争记录机制。该机制通过离线的方式分析同步操作带来的冲突对确定性重演的影响,将同步操作引入的冲突划分为有害的同步冲突和无害的同步冲突,无害的同步冲突不会影响确定性重演,可以不予记录。该机制通过添加两条新的指令能够识别常用的锁和障碍两种同步操作,并将它们引入的不影响确定性重演的同步冲突在冲突检测阶段过滤掉。仿真结果表明,该机制有效减小了内存竞争日志,也进一步降低了带宽开销。
　　第四,本文提出了分离式内存竞争记录机制。重演速度是衡量内存竞争记录机制优劣的一个非常重要的方面,而原有的并发重演算法存在效率低下问题。因此,为了进一步提高并发重演的速度,本文提出了分离式内存竞争记录机制。该机制分别在一致性协议的应答方和请求方分开记录当前发生序对应的先发生方和后发生方,仅在需要记录内存竞争时向一致性协议的应答消息中添加一位冲突记录标志位,减小了记录阶段的通信开销。同时引入一种大小自适应的记录格式,在记录内存竞争时,处理器核根据先发生方及后发生方的大小选择合适的记录格式,减小了单个记录的尺寸。更重要的是,在这种分离式内存竞争记录方式下,冲突先发生方所在处理器核能够在重演时积极主动的为冲突后发生方创建并发送唤醒消息,提高了重演的速度。仿真结果表明,该机制在重演速度、内存竞争日志及带宽开销方面均具有较高的性能。
　　本文在以下5个方面明显改善了已有点到点内存竞争记录机制的性能:内存竞争日志、硬件资源消耗、带宽开销、重演速度及可应用性。相比其他记录方式,也在以下方面具有明显的优势:内存竞争日志、带宽开销、重演速度及可应用性。

目录

封面

中文摘要

英文摘要

目录

第1章 绪 论

1.1 课题背景及研究的目的和意义

1.2 确定性重演介绍

1.3 内存竞争及内存竞争记录国内外研究现状

1.4 内存竞争记录性能评价方法

1.5 本文研究的问题与成果

1.6 本文的组织结构

第2章 分段式内存竞争记录机制

2.1 引言

2.2 相关背景

2.3 分段式内存竞争记录方式

2.4 基于分段的内存竞争检测与记录

2.5 优化内存竞争日志

2.6 分段式内存竞争记录器

2.7 仿真结果与评价

2.8 本章小结

第3章 基于签名的循环式内存竞争记录机制

3.1 引言

3.2 基于签名的冲突检测

3.3 用循环发生序优化内存竞争日志

3.4 签名实现的循环式内存竞争记录器

3.5 仿真结果与评价

3.6本章小结

第4章 同步敏感的内存竞争记录机制

4.1 引言

4.2 相关背景

4.3 同步冲突

4.4 同步敏感的内存竞争检测和记录

4.5 同步敏感内存竞争记录器

4.6 仿真结果与评价

4.7 本章小结

第5章 分离式内存竞争记录机制

5.1 引言

5.2 内存竞争记录方式

5.3 重演策略

5.4 分离式内存竞争的检测与记录

5.5 分离式内存竞争记录重演器

5.6 仿真结果与评价

5.7本章小结

结论

参考文献

攻读博士学位期间发表的论文及其它成果

声明

致谢

个人简历