面向新型异构众核系统的多设备协同并行计算关键技术研究

摘要

近年来，由多核CPU和众核加速器而构成的新型异构众核系统以其高性能、低能耗和低成本等优势在高性能计算领域得到了迅猛发展，基于异构众核系统而开发的并行应用也日益增多。但由于异构众核系统复杂的体系结构以及简单易用的异构协同并行编程模型的缺乏，导致绝大部分并行应用仅能有效利用异构众核系统中某一类计算设备，这造成了异构众核系统中其它计算设备的浪费，难以充分发挥异构众核系统的性能优势。因此，如何充分利用异构众核系统中所有可用的计算设备来高效协同执行并行应用已成为一个迫切需要解决的课题。
　　异构协同并行计算旨在充分利用异构众核系统中多个任意类型的计算设备来相互协作、并行地执行指定的计算任务，以提高异构众核系统的计算性能。然而异构系统中不同类型的计算设备具有完全不同的体系结构、指令集、计算能力、存储能力和通信能力等，这给异构协同并行计算带来了极大的挑战。本文围绕面向新型异构众核系统的多设备协同并行计算的关键技术展开了较为深入的分析和研究。本文的研究工作主要集中在以下四个方面:
　　(1)为降低异构协同并行编程难度、减轻编程负担并高效支持基于异构众核系统的数据级并行应用的多设备协同并行计算，提出了一个基于指导语句的异构协同并行编程框架(简称OpenHCPP)。通过扩展广为使用的OpenMP给编程人员提供了一种更为简单灵活的方式来充分利用异构众核系统中所有可用的计算设备来协同执行数据级并行应用。借助于OpenHCPP提供的源到源的编译器和运行时系统，编程人员无须关心如何在参与协同并行计算的各设备间高效地划分计算任务和传输数据。实验结果表明采用OpenHCPP能有效提高基于异构众核系统的数据级并行应用的开发效率和执行效率。
　　(2)为能在异构众核系统中利用多个计算设备合理高效地协同执行数据级并行应用，提出了两种高效支持异构协同并行计算的设备间动态任务调度策略，包括反馈式动态弹性任务调度策略和抢占式动态弹性任务调度策略。前者较适合于计算和数据均匀分布的且计算内核仅需执行一次或少量重复执行的数据级并行应用，而后者较适合于计算和数据非均匀分布的且/或计算内核需大量重复执行的数据级并行应用。实验结果表明，采用本文提出的设备间动态任务调度策略不仅能让各计算设备得到充分利用、设备之间达到较好的负载均衡，而且能避免频繁的设备初始化、kernel启动、设备间数据传输和设备间同步所带来的开销。
　　(3)鉴于异构众核系统中设备间通信容易成为某些数据级并行应用的多设备协同并行计算的性能瓶颈，为有效隐藏、减少或避免设备间通信开销，提出了一种增量式数据传输方法和一种基于软件流水线的通信优化方法。前者基于反馈式动态弹性任务调度，充分考虑了如何避免设备间重复冗余的数据传输，实现了能有效避免设备间重复传输的反馈式动态任务调度;后者基于反馈式动态弹性任务调度和抢占式动态弹性任务调度，充分考虑了如何尽可能地重叠加速器端计算内核执行与主机-加速器间数据传输，实现了能有效隐藏设备间通信开销的反馈式动态弹性任务调度和抢占式动态弹性任务调度。实验结果表明，采用本文提出的设备间通信优化方法能显著改进某些存在较大设备间通信开销的数据级并行应用的多设备协同并行计算的整体性能。
　　(4)综合应用所提出的异构协同并行编程框架、设备间任务调度策略和设备间通信优化方法，实现了一个复杂应用-求解子集和问题的并行二表算法-的高效CPU-GPU协同并行计算。鉴于并行二表算法的生成阶段的异构协同并行计算中易出现设备间负载不均衡且存在较大设备间通信开销，在生成阶段的CPU-GPU协同并行执行中采用了避免设备间重复传输的反馈式动态任务调度策略。针对并行二表算法的剪块与搜索阶段存在计算和数据分布不均匀的问题，在剪块与搜索阶段的CPU-GPU协同并行执行中采用了抢占式动态弹性任务调度策略。实验结果表明本文提出的求解子集和问题的并行二表算法的CPU-GPU协同并行实现显著优于CPU/GPU-only并行实现，这得益于CPU和GPU的充分利用、CPU-GPU间良好的负载均衡以及CPU-GPU间较小的通信开销。

目录

声明

摘要

插图索引

附表索引

第1章 绪论

1．1 研究背景

1．1．1 新型异构众核系统的体系结构

1．1．2 基于异构众核系统的并行应用

1．1．3 异构协同并行计算面临的挑战

1．2 研究现状

1．2．1 异构众核系统中的编程模型

1．2．2 异构众核系统中的任务调度

1．2．3 异构众核系统中的通信优化

1．3 研究内容及贡献

1．3．1 本文的研究内容

1．3．2 本文的主要贡献

1．4 本文组织结构

第2章 基于指导语句的异构协同并行编程框架OpenHCPP

2．1 引言

2．2 相关工作

2．3 OpenHCPP并行编程框架的设计

2．3．1 OpenHCPP总体架构设计

2．3．2 设备间静态任务调度

2．3．3 OpenMP导语和子句的扩展

2．3．4 OpenHCPP编程案例

2．4 OpenHCPP并行编程框架的实现

2．4．1 OpenHCPP编译器

2．4．2 OpenHCPP运行时系统

2．5 实验评测

2．5．1 实验设置

2．5．2 可编程性评测

2．5．3 性能评测

2．6 小结

第3章 异构协同并行计算中设备间动态任务调度

3．1 引言

3．2 相关工作

3．2．1 Quick调度策略

3．2．2 Split调度策略

3．3 反馈式动态弹性任务调度策略

3．4 抢占式动态弹性任务调度策略

3．5 实验评测

3．5．1 多种动态任务调度策略性能对比

3．5．2 初始块大小性能影响分析

3．5．3 动态调度开销分析

3．6 小结

第4章 异构协同并行计算中设备问通信优化

4．1 引言

4．2 相关工作

4．3 增量式数据传输方法

4．3．1 增量式数据传输的产生背景

4．3．2 避免重复传输的反馈式动态任务调度

4．3．3 增量式数据传输的应用

4．4 基于软件流水线的通信优化方法

4．4．1 基于软件流水线的通信优化的基本思想

4．4．2 隐藏通信开销的反馈式动态弹性任务调度

4．4．3 隐藏通信开销的抢占式动态弹性任务调度

4．5 实验评测

4．5．1 通信优化前后性能对比

4．5．2 多GPU实验测试

4．5．3 与StarPU和OmpSs的性能比较

4．6 小结

第5章 异构协同并行计算在求解子集和问题中的应用

5．1 引言

5．2 相关工作

5．3 求解子集和问题的并行二表算法

5．3．1 并行二表算法的生成阶段

5．3．2 并行二表算法的剪块阶段

5．3．3 并行二表算法的搜索阶段

5．4 并行二表算法的异构协同并行实现

5．4．1 生成阶段的异构协同并行实现

5．4．2 剪块与搜索阶段的异构协同并行实现

5．5 实验评测

5．5．1 实验设置

5．5．2 不同并行实现的性能对比

5．5．3 不同测试平台的性能对比

5．5．4 不同背包容量的性能对比

5．6 小结

第6章 结论与展望

6．1 工作总结

6．2 研究展望

参考文献

致谢

攻读学位期间所完成的论文

攻读学位期间所参与的科研项目