多核处理器映射关键技术研究——基于细粒度融合的任务划分算法研究

摘要

随着多核处理器技术的不断发展，软件人工并行化的代价越来越高。如何在有限的硬件资源上实现高性能的程序是摆在面前的一大难题。为了缓解这一问题，我们采用了自动并行化的思路对程序的内在并行性进行挖掘，通过任务划分得到可执行的高性能程序。
　　多核任务划分是一个NP-Hard问题，而且随着自动并行化工具对原串行程序（例如C程序）进行深层次的并行性挖掘时，因此必然产生细粒度的任务依赖图。而且随着任务粒度的减小，对后续算法的要求越来越高。
　　聚类分析是一种常见的无监督学习算法，而任务划分本身也缺乏足够的先验信息，而目标都是将对象进行归类，因此两者有着天然的相似性。本文通过分析和设计，将聚类的思想应用到了任务划分中，并且在设计的过程中重新考虑了任务粒度的定义、任务距离函数、聚类的过程，量化了各个性能指标，将任务图进行特定的数据化表示，实现了对任务图的有效划分，并且能够输出聚类后的直观结果，各个性能指标。本论文将这些工作集成到一个软件工具中。试验表明:本论文工作能够获得较好的划分结果。

目录

摘要

第一章 绪论

1．1 并行技术的发展与挑战

1．2 国内外研究现状

1．3 本文的主要工作

1．4 本章小结

第二章 程序并行性分析

2．1 程序并行性含义

2．2 程序并行性表示

2．3 并行性开发的粒度

2．4 程序并行性检测

2．5 本章小结

第三章 聚类分析

3．1 聚类分析的起源

3．2 聚类分析的数学原理

3．3 本章小结

第四章 细粒度融合的任务划分算法

4．1 融合粒度与负载均衡

4．2 基于层次的融合算法

4．2．1 算法介绍

4．2．2 算法实现

4．2．3 算法的问题及改进

4．3 基于聚类的融合算法

4．3．1 硬件约束分析

4．3．2 算法关键参数考量

4．3．3 距离和聚合度定义

4．3．4 算法流程及复杂度分析

4．3．5 划分效果衡量指标

4．4 软件工具的实现

4．5 本章小结

第五章 实例验证

5．1 用于验证的图模型表示

5．2 任务图的特点分析

5．3 实例测试及分析

5．3．1 测试方法介绍

5．3．2 融合结果与分析

5．4 本章小结

第六章 总结与展望

6．1 工作总结

6．2 展望

参考文献

致谢

声明