Prophet推测多线程系统设计与实现

推测多线程技术通过推测执行的方式开发应用程序的线程级并行性,以提高程序执行性能。该技术一般通过执行模型来检测运行时可能的线程推测错误情况,并采取合适的机制恢复程序正确运行。描述的Prophet是一种基于硬件实现的推测多线程执行模型。重点描述了Prophet执行模型针对执行模型设计的关键问题的解决方案,包括Prophet的线程状态控制和多版本的Cache系统,Prophet的多版本Cache系统提供了推测数据缓存功能,并使用基于总线监听的Cache协议实现了数据依赖违规检测。还给出了使用Olden基准程序对Prophet执行模型进行功能和性能测试的结果,并分析说明了Prophet系统可以有效地开发应用程序的线程级并行性。

基于模糊聚类的推测多线程划分算法

推测多线程(Speculative Multithreading,SpMT)技术是一种实现非规则程序自动并行化的有效途径.然而,如何有效评估由诸如控制、数据依赖等因素导致的多种并行开销并实现最优线程划分一直是制约加速比性能提升的关键问题.基于启发式规则的传统划分方法虽然可以取得一定的加速效果,但由于启发式规则只能对多种并行开销进行定性评估,因而导致只能得到经验上较优的线程划分.针对传统划分方法的局限性,文中首次提出并实现了一种基于模糊聚类的线程划分方法.在该方法中,作者首先提出一种评估模型来定量评估各种并行开销,然后通过深入分析各种并行开销来确定最佳的线程解搜索空间,最终利用聚类方法实现有效线程解空间搜索以求取更优的线程划分.基于Olden程序集的测试结果表明,文中提出的线程划分方法可以有效地对非规则程序进行划分,其平均加速比可达到1.85.

一种应用代价评估的推测多线程路径预测方法

推测多线程技术对于自动并行化非规则程序是有效的,然而基于控制流图和分支预测方法的线程划分方法,不可避免地受到划分路径上存在的控制依赖和数据依赖制约.针对现有的路径预测方法在考虑控制依赖影响的同时却不能有效地综合考虑数据依赖影响的问题,提出一种新的基于代价评估的路径预测方法,通过引入数据依赖模型,综合评估控制和数据依赖两种影响因素,寻求一条具有近似最小推测开销的推测划分路径.实验结果表明,文中提出的路径预测方法能够计算出代价更小的推测划分路径,并取得了更好的加速比性能,总体上系统可以得到2.43%的加速比性能提升.

一种基于路径优化的推测多线程划分算法

推测多线程(speculative multithreading,简称SpMT)技术是一种实现非规则程序自动并行化的有效途径.然而,基于控制流图和分支预测技术的线程划分方法,不可避免地会受到划分路径上所存在的控制依赖和数据依赖的制约.目前,在传统的线程划分算法中存在的一个重要问题是,在对划分路径进行选取时只考虑了控制依赖影响却不能有效地综合考虑数据依赖的影响,进而导致不能选取最佳的划分路径.因此,针对传统方法中这种依赖评估方法效率低下的问题,设计并实现了一种基于路径优化的线程划分算法.该算法通过引入基于程序切片技术的预计算方法,建立一种路径评估方法来评估程序间的控制和数据依赖.同时,引入控制线程体大小的启发式规则,以便有效地解决负载不平衡的问题.基于Olden测试集的测试结果表明,所提出的算法可以有效地对非规则程序进行划分,其平均加速比可以达到1.83.

SpMT WaveCache:开发数据流计算机中的推测多线程

推测多线程技术(Speculative Multithreading,SpMT)是通过推测地执行多个线程来开发线程级并行性,提高超标量处理器性能.通过增加额外的硬件单元,比如线程同步单元(Thread Synchronization Unit,TSU)、线程上下文表(Thread Context Table,TCT)和线程内存历史表(Thread Memory History,TMH),扩展了事务性内存系统,提高了基于波标量指令集系统结构(WaveScalar ISA)实现的WaveCache模拟器的性能.同时,还提出了一种新的两级线程级事务提交机制.最后,采用了6个来自SPEC、Media和Mibench测试程序集的真实测试程序,评估了推测多线程WaveCache(SpMT WaveCache)的性能.实验表明,SpMT WaveCache比超标量系统结构提高了2～3倍的性能,是一种有效的开发动态数据流计算机性能的方法.

支持推测多线程的扩展多核模拟器Prophet+

推测多线程技术是软硬件协同开发非规则应用程序的线程级并行性的有效方法.通过体系结构对推测并行执行模式的支持,编译器产生推测多线程目标代码实现自动并行化加速.文中针对硬件平台如何有效支持程序运行过程的分析及测试,提出了一种支持推测并行执行模式的超标量流水线结构和一种基于独立栈的运行时内存空间管理方法.通过对Prophet模拟器扩展实现,并经Olden基准程序测试表明,扩展后的Prophet+在保持Prophet模拟器性能的前提下,提高了模拟器的精度和灵活性.

面向片上多核处理器的推测多线程机制下的独立栈模型

在推测多线程并行执行时,各线程中借助共享栈来实现函数调用的过程存在互斥访问问题,为此提出了一种采用片上多处理器(CMP)的推测多线程机制下的独立栈函数调用模型,核栈采用一对一方式,栈之间的有机配合支持推测多线程中的函数调用.通过在模拟器端添加两条指令实现栈空间的管理,从而消除了共享栈模型中的加锁问题.为了保证程序正常运行,编译器对生成的代码作相应的调整,模拟器方面则增添了get和update两条指令,以便管理相应的栈空间.因为独立栈函数调用方法消除了共享栈模型中的栈加锁问题,使得成功线程发起的数目有不同程度的提高,从而提高了程序的并行加速比.Olden基准程序的测试表明,独立栈模型相对于共享栈模型使程序的平均并行加速比提高了3.85%.但是,由于影响程序推测并行加速比的因素复杂,某些测试程序也出现了独立栈的加速比低于共享栈的情况.

一种基于推测代价评估的推测多线程并行粒度调节方法

传统的推测多线程技术总是假定程序的并行粒度大小应该随着处理器核资源数目的增加而增大,未考虑不同数目的处理器核资源对程序自身并行性能的影响作用。针对这个问题,提出一种自适应的循环并行粒度调节方法用于优化处理器核资源的分配过程。以推测级为单位,通过动态收集循环中所有推测线程的性能量化分析结果,进行推测代价评估。并利用评估结果动态调整循环的并行粒度大小,优化所分配到的处理器核资源的数目,以减少不必要的推测代价。实验表明,该方法不但在SPEC CPU基准测试程序集上能取得较好的性能提升,而且进一步优化了推测时的能耗开销。

基于推测多线程技术的程序可视化方法与实现

程序可视化的目的是使程序的内部结构以及行为变得更容易被理解,辅助程序员基于程序的行为进行推理,包括调试程序以及评估程序运行时的资源利用情况。本文以面向片上多处理器的推测多线程编译系统为基础,提出一种基于SUIF编译框架的推测多线程程序可视化方法,实现对推测多线程程序的视图显示和性能评估,同时,本文以C源程序作为输入,利用所设计的可视化平台,进行实例分析,表明可视化方法在推测多线程自动并行化中有实用意义。

延时敏感的推测多线程调度策略

随着大规模片上多核处理器的发展,越来越多的核被集成到一个芯片上。一方面,总会有一些核处于空闲状态;另一方面,受功耗限制片上单核比较简单,导致单线程性能较弱。通过在片上多核处理器上支持推测多线程机制,可以利用空闲的片上资源来加速串行程序执行,提高单线程性能。决定推测多线程执行性能的一些额外开销,比如缓存缺失率上升、冲突检测开销、线程提交开销以及推测线程重新执行开销等,对片上多核处理器访存时延和核间通信时延非常敏感。传统的多线程调度算法因为没有考虑到推测多线程机制的特点,在用于推测多线程调度时效果不佳。提出的延时敏感的推测多线程调度算法,利用推测多线程在剖析、编译阶段产生的访存特性统计和实时访存记录,计算程序的数据重心,逐步将推测多线程调度到数据重心周围的相邻几个核中执行;同时,在推测线程调度过程中充分利用提交成功的线程和推测失败的线程留在缓存中的数据,提高缓存利用率。实验结果表明,推测多线程机制执行中,采用延时敏感的推测多线程调度策略相对于广泛采用的优先级调度策略能够取得平均16.8%的性能提升;相对于最近提出的基于非一致性数据访问优化的集群线程调度策略能够取得平均10.1%的性能提升。

利用连续两阶段在线剖析优化多线程推测执行

针对当前推测多线程优化中使用的离线剖析受到训练输入集限制的问题,提出一种根据在线剖析结果自动变换推测多线程程序的动态优化方法.该方法在程序运行时执行剖析和优化工作,不需要单独的剖析过程以及通用的训练输入集.该方法也适用于那些运行时行为特征呈阶段性变化的程序.实验表明,在指导事务划分和选择并行循环方面,动态优化方法能够达到和静态优化方法相似的效果,完全可以在离线剖析失效时被使用.

基于人工免疫算法的推测多线程线程划分参数的优化（英文）

目的:用人工免疫算法优化线程划分过程的主要影响因素,使不同应用获得最优划分方案。创新点:将智能算法应用到推测多线程技术,实现该技术在线程划分过程中的优化。方法:首先,根据启发式规则提取影响线程划分的五个参数,分别是DT,TSL,TSU,SDL,SDU。五个参数根据启发式规则确定取值范围,步长变化是随机的。将加速比设定为目标,五个参数变化形成解空间,优化目标是在解空间中寻找最优解(图6),即找出各个应用最优的划分策略。利用人工免疫算法搜索解空间,找到最优解(表4)。结论:针对Olden测试集中每个测试函数获得最优划分参数值(图10-20),测试集中的函数在四核平台上的测试性能较之机器学习方法线程划分算法提高3.00%,较之启发式规则线程划分方法性提高8.92%。

一种数据结构制导的线程划分方法与执行模型

在对程序进行并行化时,为了保证结果的正确性,并行编译器只能采取一种保守的策略,也就是,如果它不能确定两段代码在并行执行时是否会发生冲突,它就不允许这两段代码并行执行.虽然这种做法保证了正确性,但同时也限制了对并行性的开发.在这种背景下,许多推测多线程方法被提了出来,这些方法通过允许可能冲突的代码段并行执行来把握更多的并行机会,同时,通过从冲突中恢复来保证结果的正确性.然而,传统推测多线程方法所使用的"沿控制流将串行程序划分为多个线程"的做法并不适合不同数据结构上的操作在控制流中相互交错的情况,因为如果沿控制流将程序线性地划分为多个线程,则同一个数据结构上的操作将被分到不同的线程中,从而非常容易发生冲突.为了有效地对这些程序进行并行化,提出了一种基于数据结构的线程划分方法与执行模型.在这种方法中,程序中的对象被划分成多个组,同一组中对象上的操作被分派到同一个线程中去执行,从而降低了在同一个数据结构上发生冲突的可能性.