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

合并与分割

作　者: 曾丽芳
导　师: 杨学军
学　校: 国防科学技术大学
专　业: 计算机科学与技术
关键词: 编译优化访存数据流优化数据布局优化层次存储分布共享存储伪共享流处理器
分类号: TP338.6
类　型: 博士论文
年　份: 2006年
下　载: 149次
引　用: 0次
阅　读: 论文下载

内容摘要

并行是提高计算机性能的有效途径之一,并行技术可分为单处理器内的并行以及将多个处理器互连构成的并行两个层次。本文将单处理器内的并行称为结点内并行,将利用多个处理器互连构成的并行称为结点间并行。结点内并行的一种发展趋势是同时支持指令级并行和数据级并行,Stanford大学研制的Imagine流处理器是同时支持指令级并行和数据级并行的典型代表。结点问广泛应用的一种并行体系结构是分布共享存储(DSM)多处理机,其主要优势是可扩展性好并且并行编程模型简便。两个层次的并行性能的充分发挥都受到存储访问延迟和带宽的约束(所谓的“存储墙”问题)。对结点间并行,除了“存储墙”问题外,伪共享是严重影响并行性能的另一个问题。为了解决“存储墙”问题,当前的计算机大都采用层次存储结构。支持结点内并行的层次存储结构有Cache层次存储和流式层次存储(本文中统称为结点内层次存储),其中,Cache层次存储强调降低存储延迟,流式层次存储则强调提高存储带宽。支持结点间并行的层次存储(简称为结点间层次存储)在结点内层次存储的基础上增加远地内存,本文将由本地内存和远地内存构成的层次称为分布存储。层次存储结构的有效利用依赖于访存数据流的优化,有两种方法可以优化访存数据流:改变程序对内存单元的访问顺序和改变数据在内存中的布局。前一种优化方法起步早,相对较成熟,数据布局优化则是近年来研究较多的一种优化方法。本文面向结点内层次存储和分布存储,着重研究了通过优化数据的布局来有效利用各级存储器、优化访存数据流性能的编译优化方法。对强调提高存储带宽的流式层次存储,除了研究数据布局优化外,还研究了通过计算核心(kernel)合并来优化访存数据流的方法。本文的创新工作主要体现在如下几个方面:1)面向分布存储的访存数据流优化结合在软件分布共享存储(SDSM)系统上实现OpenMP并行编译器的过程中遇到的性能问题,研究了如何通过共享数组的合理布局来优化访存数据流的问题,提出了如下两种优化方法:①针对SDSM系统上大粒度共享单元(共享页)导致小共享数组的伪共享问题,以及大步长数组访问模式导致的共享页利用率低的问题,提出了共享数组交叉合并优化方法,此方法将程序中总是同时出现的多个共享数组按照一定的规则进行合并。测试结果表明,此方法能有效减少分布共享存储多处理机上小共享数组应用的伪共享、提高大步长数组访问应用的本地局部性。②针对某些SDSM系统上共享单元粒度较小(例如Cache块)以及OpenMP程序中共享数组分布的对准问题,分析了共享数组交叉合并优化方法的不足,提出了基于数据访问轨迹对准的数组融合方法。此方法能在数组合并的同时对准数组的访问轨迹,使得融合后的数组能提高Cache块等小粒度共享单元的利用率。对于大粒度共享页,此方法能对准共享数组的分布,减少处理机之间的通信。测试结果表明,基于数据访问轨迹对准的数组融合方法能够获得比共享数组交叉合并方法更高的性能提升。2)面向结点内层次存储的访存数据流优化面向结点内的Cache层次存储和流式层次存储,提出了如下访存数据流优化方法:①面向结点内的Cache层次存储,结合Fortran语言中并行语法成分的优化实现问题,提出了利用临时数据空间合并来提高编译器目标代码性能的优化方法,并在G95开放源码编译器中实现了这种优化。G95和Intel EFC编译器的对比测试结果表明,对Fortran语言中典型的并行语法成分——包含数组赋值语句的FORALL结构,临时数据空间合并优化能有效提高编译器产生的目标代码的性能。测试结果还表明,循环排序优化和临时数据空间合并优化的综合运用,进一步提高了目标代码的性能。②面向结点内支持数据并行的流式层次存储,分析了典型的流体系结构及其编程模型,提出了流分割和线性kernel合并两种优化方法,并使用Imagine软件模拟平台,测试了两种方法的优化效果。测试结果表明:流分割优化能显著提高带宽层次存储的利用率,改善流处理器内的并行;线性kernel合并优化能有效减少kernel的调用次数和流在各级存储器中切换所花费的时间,从而提高流应用在流处理器上的性能。

全文目录

摘要  9-11
ABSTRACT  11-13
第一章绪论  13-31
  1.1 研究背景  13-20
    1.1.1 并行处理层次及其瓶颈问题  13-17
    1.1.2 面向并行处理的编程模型和编程语言  17-20
  1.2 基本术语  20-21
  1.3 相关研究及存在的问题  21-28
    1.3.1 面向结点内层次存储的相关研究  21-26
    1.3.2 面向分布存储的相关研究  26-28
  1.4 本文的主要工作及创新  28-30
  1.5 文章的组织结构  30-31
第二章共享数组交叉合并优化方法  31-55
  2.1 引言  31-32
  2.2 分布共享存储体系结构对共享编程的支持  32-36
    2.2.1 硬件支持全局编址DSM系统  33-35
    2.2.2 软件支持全局编址DSM系统  35-36
  2.3 基于SDSM的OpenMP编译器  36-38
    2.3.1 OpenMP编程规范  36-37
    2.3.2 典型的OpenMP/SDSM编译器  37-38
  2.4 共享数组交叉合并优化方法及其实现考虑  38-54
    2.4.1 共享数组交叉合并优化思想的产生背景  38-42
    2.4.2 共享数组交叉合并基本优化思想  42-45
    2.4.3 实现共享数组交叉合并优化必须解决的问题  45-49
    2.4.4 共享数组交叉合并优化方法的实现  49-51
    2.4.5 性能测试及结果分析  51-54
  2.5 小结  54-55
第三章基于数据访问轨迹对准的数组融合优化方法  55-73
  3.1 引言  55-57
  3.2 数组空间和数据访问轨迹  57-60
  3.3 数组访问距离向量(ADV)及相关概念  60-61
  3.4 基于ADV的数组融合方法  61-66
  3.5 扩展的访问亲密关系及性能代价模型  66-69
    3.5.1 基于profile信息的编译分析方法  66-68
    3.5.2 性能代价判别规则  68-69
    3.5.3 允许在各计算段改变数组布局  69
  3.6 性能测试和比较  69-72
  3.7 小结  72-73
第四章临时数据空间合并优化方法  73-89
  4.1 临时数据空间合并优化的基本思想  73-74
  4.2 循环排序优化的基本思想  74-76
    4.2.1 数据重用理论  74-76
    4.2.2 循环变换优化原理  76
  4.3 Fortran语言中的并行语法成分  76-79
    4.3.1 Fortran语言的发展  76-77
    4.3.2 数组赋值语句与数组标量化  77-78
    4.3.3 FORALL结构的特点  78-79
  4.4 两种优化方法在FORALL实现过程中的综合运用  79-82
    4.4.1 FORALL结构的实现  79-80
    4.4.2 临时数据空间合并  80-81
    4.4.3 嵌套循环排序  81-82
  4.5 性能测试  82-88
    4.5.1 编译器相关情况  82-84
    4.5.2 性能分析工具PAPI简介  84-85
    4.5.3 测试用例和测试平台  85-86
    4.5.4 测试结果  86-88
  4.6 小结  88-89
第五章流分割和线性kernel合并优化方法  89-111
  5.1 流处理器的研究现状  89-92
  5.2 Imagine流处理器的体系结构和编程模型  92-97
    5.2.1 Imagine流处理器的体系结构  92-94
    5.2.2 Imagine流处理器的编程模型  94-95
    5.2.3 Imagine模拟器ISim  95-97
  5.3 流分割和线性kernel合并优化  97-107
    5.3.1 流分割优化  97-99
    5.3.2 线性kernel合并优化  99-102
    5.3.3 性能测试  102-107
  5.4 流编译和流应用关键问题分析  107-110
    5.4.1 优化机会  107-108
    5.4.2 关键问题  108-110
  5.5 小结  110-111
第六章结束语  111-114
  6.1 工作总结  111-112
  6.2 研究展望  112-114
攻读博士学位期间发表的论文  114-115
攻读博士学位期间参加的科研工作  115-116
致谢  116-117
参考文献  117-126

合并与分割

内容摘要

全文目录

相似论文