论文部分内容阅读
随着半导体工艺技术的进步,面向多核和众核处理器的设计方法逐渐成为学术界和工业界研究热点。然而,由于众核处理器芯片结构复杂,编程环境复杂,同时应用程序的优化策略相互影响,因此,在众核处理器上映射并行算法是一件较为困难的事情。选取几类具有代表性的算法在众核结构上进行优化,可以帮助处理器设计者更清楚地理解应用程序的行为特征,从而可以反馈给处理器设计者,以便于完善处理器的结构设计。同时,在一个给定的众核处理器结构上优化程序,可以分析优化措施对程序性能的影响,帮助并行程序员找到合适的优化方法,最终提升程序性能。因此,本文选取了三类典型应用程序:科学和工程计算,网络处理的应用和流处理应用,研究了这三类应用在不同优化方法:负载均衡,细粒度快速同步,硬件结构支持的数据缓存和硬件结构支持的快速线程问通讯等对程序性能的影响。通过时钟精确的众核结构模拟器进行性能评测与分析,这些方法取得了较好的效果。
本文的主要贡献包括:
●第一,针对科学和工程计算中的LU分解算法进行优化,主要采用负载均衡方法对LU分解算法进行优化,其主要贡献如下:提出了一个加速比模型,同时也提出了一个负载均衡算法DABP(Dynamic Absolute Balance Policy),该算法通过对LU分解按照每次迭代次数不同而分配不同的任务,尽可能将计算任务均匀地分配到不同的处理器核上执行,有效地利用了处理器资源;为了评估2Dscatter、BRX(Bit Reverse XOR)和DABP三种负载均衡算法的效果,提出了两种不同的评价负载均衡的函数,这两个函数验证了DABP算法的有效性;在众核结构Godson-T上仿真了3种算法,试验结果表明,在使用64个处理器核的情况下,DABP算法加速比达到46,是3个算法中性能最好的。
●第二,使用细粒度同步方法对2D wavefront算法和LU分解算法进行优化,其主要贡献如下:根据处理器体系结构的特征和算法执行中的访存模式提出了数据分布方式和线程划分方式,以及线程之间的同步方法,以减少算法执行中的数据等待时间和线程间的同步开销,加速算法的执行。基于众核处理器Godson-T对其进行了模拟评估。试验表明,2D wavefront的相对加速比接近线性,而且执行时间仅为粗粒度轮询同步方式的53.2%。LU分解在使用细粒度同步消除全局barrier后,性能提升了13.1%。试验结果进一步验证了细粒度同步机制在通讯密集和使用全局同步的程序中都能显著改善并行程序的性能,并且有良好的可扩展性。
●第三,面向网络处理算法中的路由表查找算法提出了优化方法:首先详细分析了IP包查找算法在众核结构上的程序特点;提出了一种众核结构支持的并行IP包查找算法SRL(SPM based Routing Lookup)。SRL采用硬件结构支持的方法,混合配置SPM与Cache,高效地利用了数据的局部性,提升了并行程序的性能。在随机产生和使用开源工具两种情况下分别产生测试数据进行仿真,试验结果表明,在程序IPC,一级数据Cache缺失造成的开销和一级数据Cache平均访问延迟等方面都有较大的性能提升。当路由表和输入包规模大小都为100000,在使用64个线程时,IPC相对基准算法提升了8%。
●第四,面向流处理应用程序提出了优化方法:提出了一个通讯开销评价模型,通过这个模型可以评估线程间的通讯开销;提出了一个基于事件驱动的方法,该方法用于计算并行程序的执行时间;提出了一种基于硬件结构支持的流处理程序映射方法,该方法用处理器核内的SPM(Scratch-Pad Memory)来传递数据,减少了对共享Cache的访问,降低了通讯开销。通过大量仿真试验,验证了该方案的有效性。