多核环境下针对不规则应用程序的非投机并行策略

摘要

多核处理器成为主流的通用处理器，具有计算能力强、功耗低和设计复杂度低等优点。不规则应用程序中含有大量复杂的控制流和数据流，难以充分利用多核处理器带来的宝贵资源。自动并行化技术可有效地解决这一问题，将串行程序转换为可以并发执行的多线程程序，发挥多核潜能。投机并行是自动并行化技术的一个研究热点。研究人员通过在程序中加入投机因素，增加并行的机会。然而，投机并行需要花费额外的代价处理误投机。因此，非投机并行成为新的研究热点。
　　目前，非投机并行可以从不规则应用程序中提取独立多线程、流水线多线程以及环型多线程。但是，当前技术经常面临处理器负载不均衡、扩展性差以及线程间通信延迟敏感等问题。而且，非投机并行主要采用静态分析(编译器)，应用程序中由指针别名引起的问题难以解决影响并行程序的执行效率。为了解决上述问题，提出一系列新的措施和解决方案：
　　针对传统环型多线程技术对线程间通信延迟敏感的问题，提出一个自动并行化算法DOcyclical。DOcyclical利用基于优先权的动态调度策略降低线程间通信频率，避免通信延迟出现在并行程序执行的关键路径，增强程序对通信延迟的抵抗性。此外，DOcyclical将基于优先权的动态调度与节点融合策略相结合还可以保持处理器负载尽可能均衡。为了验证DOcyclical算法的有效性，利用两套标准测试程序(SPEC CPU2006和StreamIt)分别在二、四、六核处理器进行测试，实验结果表明DOcyclical算法对线程间通信延迟极不敏感。而且，DOcyclical算法可以超过当前经典算法，如DSWP、PS-DSWP和HELIX，平均21-50％、16-27%、15-25%的性能。
　　针对静态分析不能消除程序中冗余的依赖关系且难以对程序执行重用性分析的问题，提出一个动态分析框架DSspirit。DSspirit利用基于哈希的策略消除程序中冗余的数据依赖关系，利用基于值的策略分析程序的重用性，确定经常引起缓存缺失(cache misses)的指令，并向编译器提供可预取的对象。为了验证DSspirit的有效性，利用三套标准测试应用程序(SPEC CPU2006、MPI2007和OMP2012)在Intel i7-4700处理器进行测试。实验结果表明DSspirit可以克服静态分析的缺陷，消除程序中冗余的依赖关系，并提供有预取价值的对象。而且，自动并行化技术中利用动态分析框架DSspirit可以获取平均20%的性能提升。
　　针对缓存缺失(cache misses)总是影响并行程序执行效率的问题，提出一个基于动态分析的预取算法，该算法利用运行时环境确定经常引起缓存缺失的指令，并根据指令的访问特征制定不同的预取方案。为了验证预取算法的有效性，利用两套标准测试程序(SPEC CPU2006和MPI2007)在Intel i7-4700处理器进行测试。实验结果表明预取算法可以明显地提升并行程序的缓存命中率，缩短程序的总体执行时间。
　　为了保证多线程程序对通信延迟不敏感且具有较高的缓存命中率，设计一个自动并行化系统HSparallel，该系统首先利用动态分析框架DSspirit确定具有预取价值的对象，然后利用自动并行化算法DOcyclical避免通信延迟出现在并行程序执行的关键路径，同时利用预取算法提高程序的缓存命中率。为了验证HSparallel的有效性，利用两套标准测试程序(SPEC CPU2006和MPI2007)在Intel i7-4700处理器进行测试。实验结果表明HSparallel可以带来显著的性能提升。而且，HSparallel超过当前主流算法，如Paralax和文献[1,2]，平均19%、21%和17%的性能。
　　最后，以上所有算法、框架和系统都完全开发于LLVM编译器，并写入到该编译器的后端。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 研究背景与意义

1.2 国内外研究现状

1.3 本文研究的主要内容

1.4 论文的组织结构

2 自动并行化

2.1 依赖关系

2.2 典型的自动并行化技术

2.3 本章小结

3 对线程间通信延迟不敏感的环型多线程算法

3.1 研究动机

3.2 DOcyclical算法

3.3 实验结果

3.4 本章小结

4 数据依赖关系分析和跨距特征分析的框架

4.1 研究动机

4.2 DSspirit的基本框架

4.3 基于动态分析的预取算法

4.4 实验结果

4.5 本章小结

5 一个完整的自动并行化系统

5.1 研究动机

5.2 HSparallel自动并行化系统

5.3 实验结果

5.4 本章小结

6 总结与展望

6.1 主要工作总结

6.2 研究展望

致谢

参考文献

附录1 攻读学位期间发表论文目录

附录2 攻读博士学位期间参加课题目录