面向多核处理器的数据流程序编译关键技术研究

摘要

随着多核处理器已经成为主流和工业标准，如何在屏蔽底层细节简化编程的同时充分利用处理器核间的并行性来提高程序性能，已经成为编程的一个巨大挑战。C、C++和Fortran等基于单指令流和统一存储结构的传统编程模型已经无法适应多核处理器结构。基于领域的数据流编程（Dataflow Programming）模型将媒体应用特性与程序设计语言相结合，在简化编程的同时，为编译器在多核处理器下的优化提供了大量的并行性，因此受到广泛的关注。然而，多核处理器间的通信和同步开销以及大量媒体处理应用的实时性要求对程序的性能提出了新的挑战。针对以上数据流程序所面临的实时性和代码的高效性等问题，本文对数据流程序编译所涉及的主要关键技术进行了系统研究。
　　 针对当前数据流语言的语法不易理解和难以编程的问题，设计并实现了一种数据流编程语言DFBrook和相应的编译系统原型。DFBrook通过在标准C 语言中扩展数据流模型，实现了数据流和C 语言的混合编程。程序员可以通过在C 语言中嵌入数据流代码来实现对特定程序模块的数据流执行。编译系统对数据流语言进行识别后，利用同步数据流图作为相应的中间代码表示，同时根据目标系统结构特点，对数据流程序进行并行优化，并生成面向目标多核处理器的多线程代码。
　　 为了减小数据流程序在多核处理器上的通信开销，提出了一种针对实时数据流程序的低通信软件流水调度模型。模型利用整数线性规划理论对软件流水调度中的计算、通信资源以及流水线执行的阶段等进行统一的形式化建模，将低通信软件流水调度问题表示为一个整数线性规划问题MCRO （Minimizing Communication atRate-OptimAlscheduling），在满足实时应用需求的响应时间限制的同时，使处理器核间的通信开销达到最小。通过扩展MCRO 调度模型，使之适用于DFBrook 语言在Cell 处理器上的执行。将MCRO 调度方法与传统软件流水的表调度List、PAPS（Periodic Admissable Parallel Schedule）以及RO （Rate Optimal）调度进行性能比较，实验结果表明，MCRO 调度比表调度List和PAPS 调度在流水线的计算速率和通信开销上都有较大的性能改进，比RO 调度在通信开销上也有较大的性能提高。为了满足多核处理器的内存受限结构，提出了一种面向存储受限结构的软件流水调度方法。方法基于低通信软件流水调度模型，对每个处理器核的存储资源进行扩展建模，将内存受限软件流水的调度表示为一个统一的整数二次规划问题ROMC（Rate-OptimAlwith Memory Constraints）。通过设计阶段差估计算法将上述二次规划问题转化为整数线性规划问题，从而将ROMC 问题分解为一系列的子问题，通过有效地求解每一个子问题，最终得到ROMC 问题的有效解。同时，设计阶段赋值调整算法来实现处理器核间的存储开销平衡。实验结果表明，ROMC 调度方法与现有的方法能取得更优的调度结果。
　　 为了生成高效的软件流水代码，提出一种面向多核处理器的软件流水代码生成方法和运行时系统设计。代码生成器在模块化的软件流水代码生成框架的基础上，采用单流水核（kernel-only）代码模型来减小代码开销。同时基于Cell 处理器给出了运行时系统的设计方法，详细讨论了地址转换和同步支持等问题，实现了软件流水代码和普通代码的生成。
　　 面向多核处理器的数据流程序软件流水编译需要研究的问题还很多。在语言的设计上，需要进一步完善对数据并行的支持、带状态核函数的定义和动态计算速率的支持；在调度模型上，如何实现对带有循环嵌套的数据流程序的软件流水调度是进一步需要研究的问题；在编译时间上，如何简化规划模型，提高求解速度，特别是减小大数据量程序的编译时间，是另一个需要进一步研究的问题。

目录

文摘

英文文摘

声明

1 绪论

2 DFBrook 数据流语言与编译

3 数据流程序的低通信软件流水调度

4 面向内存受限结构的软件流水调度

5 数据流程序的软件流水代码生成

6 总结与展望

致 谢

参考文献

附录