多核结构上的线程级推测关键技术研究

论文摘要

进入21世纪以来,随着半导体工艺技术的发展,微处理器芯片体系结构由于受到功耗与设计复杂度等问题的限制开始进入多核时代,但是传统的串行程序模型与串行地址空间模型并没有发生实质性变化,并行的多核结构模型与串行的计算理论模型之间发生了矛盾。线程级推测技术的提出为缓解这一矛盾,使用多核结构加速串行程序提供了可能。目前,有关该技术的研究仍然停留在学术研究阶段,距离应用还有较大的距离,仍有许多关键技术有待深入研究。因此“多核结构上的线程级推测关键技术研究”对于探索在多核微处理器芯片上加速传统串行应用的有效方法具有重要的学术意义和实际应用价值。本文围绕线程级推测的若干关键技术问题开展了深入系统的研究,主要涉及线程级推测并行性的定位与分析、线程级推测程序的表示与变换、支持线程级推测的单芯片多处理器（Chip Multi-processor,CMP）结构模型三个方面。（1）在线程级推测并行性的定位与分析的研究中,本文提出了判定“特定应用程序是否适合推测执行”的准则,以及分析、定位应用程序中线程级推测并行性的理论与方法,并设计实现了针对线程级推测的剖析工具。（2）在线程级推测程序的表示与变换的研究中,本文为实现循环结构和子程序结构的线程级推测执行,设计实现了基本的运行时系统,完成了循环结构和子程序结构的线程化执行,简化了线程级推测程序的设计,并通过扩充系统调用的方法避免了对编译器的大幅度改动。（3）在支持线程级推测的CMP结构模型的研究中,本文考察了在CMP结构上实现线程级推测所需的硬件支持,提出了一种线程级推测硬件体系结构模型。（4）搭建了多核芯片结构的行为级模拟实验平台,开展了软硬件协同的性能分析与优化工作。通过大量的实验,完成了对多核芯片基本设计空间的搜索,获得了对线程级推测技术中的若干关键问题的新认识。本文选取SPEC CPU 2000中的程序作为研究对象。通过对应用程序中固有的线程级推测并行性的研究,我们发现:（1）程序中存在着大量的返回值可预测的子程序结构,这些子程序结构平均占据了超过50%的运行时间,简单的Last-value函数返回值预测方案已经足以取得令人满意的预测成功率。（2）程序中粒度较小的循环结构较粒度较大的循环结构多,循环展开合并技术对于控制推测线程的粒度是必要的。（3）无论是循环结构还是子程序结构,访存数据依赖都是普遍存在的,在推测执行的过程中适当地插入同步与通信对于提高线程级推测的性能具有重要意义。（4）由于受到应用本身并行特性的限制,基于4发射超标量内核的线程级推测技术所能有效利用的处理器内核数目小于4。通过搭建具体的行为级模拟平台、开展软硬件协同的性能分析与优化,我们还发现:（1）单一总线互连网络很难承担线程级推测执行过程中的数据通信负载,按照功能分裂总线的多总线互连方案可以在一定程度上缓解该问题,但是当处理器数目大于4时,多总线互连方案将成为系统性能瓶颈。（2）使用复杂的宽发射处理器内核（发射宽度大于2）构造线程级推测系统是不必要的,但是乱序发射技术是必须的。（3）线程级推测的性能很大程度依赖于编译技术,优化的线程划分方案与适当的同步通信机制是影响线程级推测性能的两个关键因素。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 研究背景
• 1.2 论文目标与研究内容
• 1.3 研究步骤和实验方案
• 1.4 论文的写作安排
• 第2章 相关的研究工作分析
• 2.1 线程级推测技术发展概况
• 2.2 线程级推测典型技术方案
• 2.2.1 Multiscalar方案
• 2.2.2 Hydra方案
• 2.2.3 STAMPede方案
• 2.2.4 其他线程级推测技术方案
• 2.3 其他相关研究工作
• 2.4 我们研究工作的定位
• 2.5 小结
• 第3章 应用中的线程级推测并行性研究
• 3.1 线程划分方案与推测执行模型
• 3.1.1 线程划分方案
• 3.1.2 循环结构的推测执行模型
• 3.1.3 子程序结构的推测执行模型
• 3.2 线程级推测并行性分析方法
• 3.2.1 循环结构的推测并行性判定准则
• 3.2.2 子程序结构的推测并行性判定准则
• 3.3 线程级推测并行性剖析工具
• 3.3.1 剖析工作总体框架
• 3.3.2 子程序结构剖析工具ProRV&ProFun的设计
• 3.3.3 循环结构剖析工具ProLoop的设计
• 3.4 实验结果及其分析
• 3.4.1 ProRV&ProFun的实验数据与结论
• 3.4.2 ProLoop的实验数据与结论
• 3.5 小结
• 第4章 线程级推测程序的表示与变换
• 4.1 处理器状态及其转换
• 4.2 子程序结构的表示与变换
• 4.3 循环结构的表示与变换
• 4.4 系统软硬件接口
• 4.5 小结
• 第5章 线程级推测体系结构模型设计
• 5.1 基本结构模型
• 5.2 推测执行的硬件支持
• 5.2.1 推测读机制
• 5.2.2 推测写机制
• 5.3 线程级推测模拟器的设计
• 5.4 小结
• 第6章 实验分析
• 6.1 运行时系统代价分析
• CALL的代价'>6.1.1 SP_CALL的代价
• FOR/SP_WHILE的代价'>6.1.2 SP_FOR/SP_WHILE的代价
• 6.1.3 小结
• 6.2 微体系结构性能分析
• 6.2.1 总线性能
• 6.2.2 发射宽度对性能的影响
• 6.3 软硬件协同工作的分析与优化
• 6.3.1 线程粒度对性能的影响
• 6.3.2 伪相关的消除
• 6.3.3 编译优化对性能的影响
• 6.3.4 有关性能的其他讨论
• 6.4 小结
• 第7章 结束语
• 7.1 论文工作总结
• 7.2 本文的主要创新
• 7.3 未来的研究工作
• 参考文献
• 在读期间发表的学术论文与取得的研究成果
• 在读期间参与的科研项目
• 致谢