面向多核系统的程序并行化方法

论文摘要

由于集成电路工艺技术的缩微化和应用需求,高性能微处理器将多个处理器单元集成到单芯片上来实现处理器性能的提升和功耗的减少。但要充分利用多核系统所提供的硬件资源,必须解决应用程序的并行化编程问题。然而,应用程序的并行化编程问题非常复杂。1)长期以来大多数程序员都采用串行的编程模型和编程语言；2)大量现存的应用程序和算法描述均是采用串行语言编写；3)面对不同的应用程序和多处理器系统结构,寻求通用的并行编程模型十分困难。因此,到目前为止研究人员还没有较好的方法来解决应用程序的并行化编程。我们针对上述并行化编程的困难,提出一种面向C程序的编程并行化方法,由程序员指导,工具辅助,实现半自动化的开发源程序的并行性。该方法结合流应用程序的特点,通过关注多层循环结构来开发应用程序中隐藏的并行性,提出了既适用于任务并行模式,又适用于流水并行模式的并行策略。本文提出的并行编程方法包括四个步骤。1)对源代码进行程序分析,结合典型数据运行驱动剖析和依赖分析,获取应用程序的执行开销、条件分支选择、函数调用关系、存储占用、函数访问的变量以及依赖关系等信息,建立任务依赖图模型。2)对任务依赖图模型进行变换,消除其中的控制依赖和冗余迭代间数据依赖,聚合环状依赖,以生成适于调度的有向无环图。3)进行任务调度,为任务设置两级优先级,任务映射过程中充分考虑分支任务的互斥性。采用启发式方法,通过反馈优化,逐步求精,获取并行化方案。4)封装任务,生成可执行代码,在多核平台上进行性能的评估。我们选用T264解码程序和AES加密程序为实验对象,分别在2核、4核和8核的硬件平台上进行评估。本文提出的并行化方法在8核平台上,AES和T264相对于单核处理器分别有5.12和5.62的加速比。实验结果证明了本方法的有效性和良好的可扩展性。本文所提出的并行化方法继承了以往的并行化研究的经验,采用启发式框架,同时兼具自己的特色：1)定义了任务依赖图(task dependence graph, TDG)模型。该模型适用于任何应用程序,能够有效表示程序中的控制依赖和数据依赖。2)针对存在错综复杂依赖关系的任务图模型提出一种有别于传统聚合消除法的变换规则。分别对分支、循环和迭代间依赖采用不同的技术,能够有效解除环状依赖。3)将动态优先级与静态优先级相结合。动态优先级保证了关键路径上的任务总能被优先处理,而静态优先级综合考虑了任务的计算开销和存储占用情况。任务到处理器的映射方法以尽量减少的执行时间为优化目标,还考虑了存在分支选择的情况。4)不仅仅对任务并行模式进行了研究,还针对多层循环结构探索了相关的流水并行技术。

论文目录

• 致谢
• 摘要
• Abatract
• 1 绪论
• 1.1 课题背景
• 1.2 研究意义及相关性工作
• 1.2.1 研究意义
• 1.2.2 相关性工作
• 1.3 并行化框架设计
• 1.4 论文贡献及内容
• 1.4.1 论文贡献
• 1.4.2 论文内容
• 2 程序分析
• 2.1 程序分析方法简介
• 2.2 典型数据运行剖析
• 2.3 依赖分析
• 2.3.1 任务模型
• 2.3.2 任务间依赖分析原理
• 2.3.3 VarAnalyzer
• 2.3.4 DepViz
• 2.4 实验
• 2.4.1 实验方法
• 2.4.2 DepAnalyzer实验举例
• 2.5 本章小结
• 3 并行化方案
• 3.1 并行化框架
• 3.1.1 基本概念
• 3.1.2 框架介绍
• 3.2 基于任务依赖图的依赖变换
• 3.2.1 对分支控制依赖的处理机制
• 3.2.2 对循环控制依赖的处理机制
• 3.2.3 对迭代间数据依赖的处理
• 3.3 并行调度算法
• 3.3.1 并行调度的限制条件
• 3.3.2 并行调度算法
• 3.4 针对循环结构的流水并行化开发
• 3.5 本章小结
• 4 代码生成与执行
• 4.1 多核运行软件系统
• 4.2 任务/对象的提取
• 4.2.1 任务/对象模型
• 4.2.2 任务/对象的生成
• 4.3 应用程序与操作系统之间的接口协议
• 4.4 通信与同步
• 4.4.1 通信
• 4.4.2 同步
• 4.5 代码执行
• 4.6 本章小结
• 5 实验方法及实例分析
• 5.1 实验方法
• 5.1.1 硬件平台
• 5.1.2 软件环境
• 5.2 实例分析
• 5.2.1 AES加密算法实验评测
• 5.2.2 T264解码程序实验评测
• 5.3 并行化方案验证
• 5.4 本章小结
• 总结和展望
• 参考文献
• 作者攻读硕士期间参加科研工作的情况