面向程序局部性的并行优化技术研究

论文摘要

现在的并行程序开发面临着两个十分重要的问题。首先,多核处理器的出现以及逐渐普及,对并行程序设计开发提出了更高的要求。其次,随着工艺水平的进步和处理器体系结果的发展,处理器的速度已经远远超过了存储器的速度,并且这种速度上的差异在逐渐扩大,从而导致了“存储墙”的出现。传统的程序并行化技术固然可以利用多核的特性,但其基本不考虑程序的局部性,导致程序的运行性能较差。本文针对循环嵌套结构中的一类程序,研究出了一套面向程序局部性的并行优化方法。首先,本文提出了一种新的并行划分方法。该划分方法考虑了同线程内不同访存之间（U-U）的重用关系,并尽量利用这种重用关系来提高程序的局部性。而后,本文还提出了一种基于新并行划分方法的程序优化方法。该优化方法考虑了线程间访存（T-T）的重用关系,并且也同样利用这种重用关系进一步增强程序的局部性。此外,我们还在研究中发现了局部性在层次存储结构中的“漂移”现象。最后,我们通过实验证明,使用该套方法对程序并行优化,可以显著降低程序的运行时间,提高程序的运行效率。我们还给出了该套方法的编译实现框架,并进行了总结与展望。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题背景
• 1.2 相关研究工作
• 1.2.1 片上多核处理器（CMP）
• 1.2.2 并行计算与并行程序
• 1.2.3 层次存储结构
• 1.2.4 重用与局部性
• 1.3 研究现状
• 1.4 本文工作及创新
• 1.5 论文结构
• 第二章 基于访存模式的循环分类方法
• 2.1 访存模式
• 2.1.1 线性访存模式
• 2.1.2 非线性访存模式
• 2.2 基于访存模式的循环分类方法
• 2.2.1 循环体单访存流
• 2.2.2 循环体多访存流
• 2.3 本文研究对象
• 第三章 面向线程内访存局部性的并行划分技术研究
• 3.1 单核处理器系统下程序局部性优化方法简介
• 3.2 多核处理器下面向程序局部性的并行划分技术研究
• 3.2.1 二维情况典型程序的并行划分技术研究
• 3.2.2 三维情况典型程序的并行划分技术研究
• 3.3 最大重用区域划分方法
• 3.4 小结
• 第四章 面向线程间访存局部性的优化技术研究
• 4.1 典型程序分析研究
• 4.2 基于最大重用区域划分方法的优化技术
• 4.3 小结
• 第五章 并行优化技术的编译实现框架设计及性能评测
• 5.1 编译实现框架
• 5.1.1 SUIF2 编译器简介
• 5.1.2 编译实现框架设计
• 5.2 性能评测
• 5.2.1 测试环境及测试方案
• 5.2.2 第三章测试结果
• 5.2.3 第四章测试结果
• 第六章 结束语
• 6.1 工作总结
• 6.2 未来展望
• 致谢
• 参考文献
• 作者在学期间取得的学术成果