分布式主存系统上自动数据和计算分解和相关研究

摘要

数据和计算分解是并行化的基础，对应的数据分布和计算划分是并行化编译的重要组成部分。 自动数据分布需要同时考虑程序的并行性、局部性、目标机器特性、后端编译器优化等一系列问题。这大大增加了自动数据分布的复杂性和难度。采用整数线性规划方法的自动数据分布框架可以拥有更好的目标程序适应性，不过前人的方案存在复杂度高，性能模型不够精确的缺点。针对这些问题，我们提出了一种新的高实用性的自动数据分布框架。该框架提供了对多维分布、多分割分布方式、多层流水并行的发掘以及动态重分布的支持，具有高性能，可扩展性和低开销等特点，因而有比较高的实用性 部分重复计算划分是计算划分阶段进行的重要优化，可以有效的减少节点间通信和同步，从而提高程序的性能和可扩展性。前人的研究工作局限于一个循环套的范围，并且没有性能模型的支持。我们扩展了原有部分重复计算划分的优化范围，给出了显式的性能模型和求解方法。 本文主要贡献如下： 1．提出基于并行性和数据依赖关系的树形程序分解方法，提高了大范围统一数 据分布情况下的性能估计精度，在候选产生算法中，对每一个程序片断只产生一 个局部最优的数据分布方式，从而大大降低了算法的复杂性。利用附属阶段等方 法，适应实际应用中常见的一些特色，降低了问题复杂度。 2．提出自动进行基于拉丁方格的多分割数据分布方式，对多维的流水并行性提 供了更好的支持，能够自动搜索优化的处理器空间配置。 3．给出具有以上特色的求解全局自动数据分布的整数线性规划求解框架。 4．给出广义的部分重复计算的概念，扩展了部分重复计算划分的优化范围。从 全局范围的部分重复计算划分、利用可用数组区域的部分重复计算划分、多层次 部分重复计算划分等方面，说明新定义所提供的优化机会。 5．提出了相应的线性性能模型，采用基于定义点的冗余通信检测方法来估计通信优化的作用。此方法在自动数据分布和部分重复计算划分中都有所应用。 6．给出了一种解决此问题的启发式框架，能够比较有效的解决一大类应用程序的部分重复计算划分问题。 7．给出一种基于整数线性规划方法解决全局部分重复计算划分问题的框架。简化了问题的求解过程，并且降低了多维分布情况下的复杂度。实验结果表明新的全局部分重复计算划分，在过去的部分重复计算划分基础上，对性能和扩展性有显著提高。

目录

文摘

英文文摘

论文说明：图目录、表目录

声明及论文版权使用授权书

第1章引言

第2章背景知识

第3章自动数据分布

第4章一种高实用性的自动数据分布方法

第5章部分重复计算划分

第6章全局的自动部分重复计算划分优化

第7章结论和未来的工作

参考文献

致谢

作者简历