论文部分内容阅读
日益重要的线延迟、变化的工作负载、功耗以及设计/验证复杂度等问题共同促进了片上多核处理器时代的到来。然而,当前主流的商用片上多核处理器主要针对多线程应用,单个串行程序的加速很难受益于多核结构。鉴于目前大量的应用仍然属于串行程序,并行编程方法迟迟不能获得推广,研究在片上多核处理器上串行程序的加速问题具有重要的理论意义和实际的应用需求。一方面,尽管传统的单核处理器挖掘指令级并行的技术(例如超标量、超长指令字等)仍然会发挥重要作用,但是该类技术已经基本成熟,并且能够预期的性能提升空间变得越来越有限;另一方面,因为片上多核处理器能够支持多个线程同时运行,包括并行编译、推测多线程以及基于线程的预取技术等在内的基于多线程的方法逐渐成为串行程序加速领域的研究热点和发展趋势。
传统的并行编译和推测多线程技术必须保证从串行程序中派生出来的多线程遵守串行程序的原有语义,从而导致保守的线程构造策略和复杂的硬件机制。然而,基于线程的预取机制能够有效地分离性能和正确性要求,是在片上多核处理器上加速串行程序(尤其是访存敏感程序)的理想途径之一。其主要思想是,利用硬件或软件从串行执行的线程中生成预取线程,这些预取线程和原有线程同时运行。由于预取线程一般可以看作是原有线程的“精简版本”,它往往比原有线程运行得快,因此预取线程负责预先执行原有线程中频繁失效的访存指令(长延迟访存指令),并把这些执行结果提前反馈给原有线程以达到加速程序执行的目的。
基于片上多核处理器的预取线程机制的核心问题是:如何让预取线程及时、准确地预取长延迟访存指令。围绕这一核心问题,本文深入研究了基于片上多核处理器的预取线程机制,主要创新和贡献如下:
第一,基于片上多核处理器结构,设计并实现了一种动态预取线程机制,详细描述了片上多核处理器支持动态预取线程机制需要的硬件基础设施。主要提出:①“影子寄存器”机制。该机制用于支持线程间的快速寄存器传递和低成本的线程初始化;②“自循环”线程构造策略。该策略使得同一个预取线程能够预执行多个长延迟访存指令,从而有效扩大了预取线程的预取范围,改善了预取的时效性。实验结果表明,针对从SPECCPU2000,Olden Benchmark以及Stream Benchmark选取的11个访存敏感的测试程序,在双核配置的情况下,采用基本线程构造策略性能平均提高3.8﹪;采用“自循环”策略,中国科学院博士学位论文-基于片上多核处理器的预取线程机制的研究(摘要)性能平均提高25.9﹪。
第二,提出一种混合预取线程机制,有效地弥补了动态预取线程在理解程序执行语义方面存在的缺陷,进一步提高了预取线程的准确度和及时性。混合预取线程机制在动态预取线程机制的基础上,根据Profiling信息的指导,识别出动态预取线程难以有效预取的访存指令,由静态线程构造工具构造对应的静态预取线程,从而有效地将静态和动态预取线程机制结合起来,以动态预取线程为主,以静态预取线程为辅,充分发挥二者的优势。本文深入分析了动态预取线程面临的挑战,在此基础上针对性地设计了静态预取线程的线程构造策略。针对从SPEC CPU2000,Olden Benchmark选取的10个访存敏感的测试程序,在双核处理器配置的情况下,采用动态预取线程机制,性能平均提高20.3﹪;采用新的预取线程机制,性能平均提高31.9﹪。
第三,提出一种基于程序结构的预取线程机制,作为动态预取线程以及混合预取线程等基于执行的预取线程机制的补充,有效地加速了一类具有紧凑型连接式数据结构的应用-“树类应用”。通过挖掘树、图等数据结构蕴含的访存并行性,提出基于程序结构的预取线程构造策略,详细探讨了“树类应用”关键程序结构(例如递归和分支结构)的识别方法,在片上多核处理器上利用预取线程机制来加速“树类应用”。与前人研究相比,该机制不需要大容量的表结构,而且在线程构造方式上比传统的动态预取线程机制简单。对于选取的1O个访存敏感的“树类应用”测试程序,在双核处理器配置的情况下,采用该预取线程机制IPC平均提高24.2﹪。
理论分析和实验数据表明,本文提出的基于线程的预取机制能够有效地在片上多核处理器上加速串行程序。本文工作以“龙芯3号”多核处理器结构设计为研究背景,为未来多核处理器的设计,尤其是在多核处理器上加速串行程序方面做了有意义的探索工作。