学位论文 > 优秀研究生学位论文题录展示

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

作　者: 王轶然
导　师: 张兆庆
学　校: 中国科学院研究生院（计算技术研究所）
专　业: 计算机系统结构
关键词: 分布式并行系统并行化编译自动数据分布计算划分
分类号: TP316.4
类　型: 博士论文
年　份: 2006年
下　载: 132次
引　用: 1次
阅　读: 论文下载

内容摘要

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

全文目录

摘要  4-10
图目录  10-13
表目录  13-14
第1章引言  14-18
  1.1 背景知识  14-15
  1.2 本文的贡献  15-16
  1.3 论文的组织  16-18
第2章背景知识  18-24
  2.1 高性能并行体系结构  18
  2.2 程序设计模型  18-20
  2.3 并行化编译  20-21
  2.4 自动数据和计算分解  21-22
  2.5 整数线性规划  22-24
第3章自动数据分布  24-38
  3.1 对准和分布模型  25
  3.2 HPF的数据映射支持  25-26
  3.3 相关工作  26-38
    3.3.1. M.G upta  26-27
    3.3.2. Anderson and Lam  27-28
    3.3.3. Palermo and Bannerjee  28-29
    3.3.4. Ulrich Kremer and Ken Kennedy  29-32
    3.3.5. Garcia, Ayguadéand Labarta  32-34
    3.3.6. A.N avaro, E. Zapata and D. Padua  34-35
    3.3.7. Pei-Zong Li  35-36
    3.3.8. A utopar  36-38
第4章一种高实用性的自动数据分布方法  38-74
  4.1 基本概念  39-47
    4.1.1 流水并行性  39-42
    4.1.2 多分割(Multi-partitioning)  42-44
    4.1.3 数据重分布  44-46
    4.1.4 编译器的单节点局部性优化  46-47
  4.2 整体框架概述  47
  4.3 树形程序分解  47-55
    4.3.1 并行性表示  48-51
    4.3.2 程序分解图的构造  51-54
    4.3.3 实例说明  54-55
  4.4 候选方案产生  55-59
    4.4.1 初步数据分布候选产生  56-58
    4.4.2 数据分布参数的统一化  58-59
    4.4.3 数据分布候选的剪裁  59
  4.5 数据分布图的产生  59-62
  4.6 性能评估  62-63
  4.7 问题的线性规划描述的和求解  63-64
    4.7.1 数据分布顶点变量和相关约束  63
    4.7.2 通信相关变量和约束  63-64
    4.7.3 问题的目标函数  64
  4.8 系统实现  64-65
    4.8.1 具体实现中若干问题  65
  4.9 实验结果  65-72
    4.9.1 复杂度结果  67-68
    4.9.2 论据性能结果  68-72
  4.10 将来的研究工作和展望  72-74
第5章部分重复计算划分  74-80
  5.1 部分重复计算划分  74
  5.2 无通信冗余计算分割  74-77
  5.3 dHPF的部分重复计算划分方法  77-79
  5.4 本章小结  79-80
第6章全局的自动部分重复计算划分优化  80-102
  6.1 研究动机  80-84
  6.2 层次式求解方法  84-85
  6.3 相对部分重复计算划分问题的形式化描述  85-86
  6.4 线性性能模型  86-87
  6.5 启发式方法  87-90
    6.5.1 局部算法  88-89
    6.5.2 全局算法  89-90
  6.6 一个说明实例  90-93
  6.7 整数线性规划求解  93-95
    6.7.1 局部算法(整数线性规划方法)  93-95
    6.7.2 全局算法  95
  6.8 实验结果和评估  95-100
  6.9 总结和展望  100-102
第7章结论和未来的工作  102-104
  7.1 本文工作总结  102-103
  7.2 下一步研究方向  103-104
参考文献  104-109
致谢  109-110
作者简历  110

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

内容摘要

全文目录

相似论文