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

高效并行计算系统中的计算模型与通信网络

作　者: 刘方爱
导　师: 刘志勇
学　校: 中国科学院研究生院（计算技术研究所）
专　业: 计算机系统结构
关键词: 互连网络路由算法并行计算模型 RP(k)网络网络嵌入波长指派
分类号: TP338.6
类　型: 博士论文
年　份: 2001年
下　载: 548次
引　用: 3次
阅　读: 论文下载

内容摘要

并行处理作为一个重要的研究领域，受到研究者越来越多的重视，而提高通信效率是一个重要的研究课题。本文针对程序中的通信效率问题，分析了产生通信拥挤的三个因素，即BSP程序引起的通信拥挤、网络拓扑结构引起的通信拥挤和网络嵌入算法不当引起的通信拥挤。在此基础上，选择这三个问题作为本文的主攻方向。经过三年的研究，在阅读大量文献的基础上，取得了理想的研究成果。针对并行程序的效率，本文提出了CSA-BSP模型，该模型能够引导程序设计者写出高效率的并行程序；针对互连网络，本文提出了RP（k）网络，该网络拓扑具有许多优良的性质，因而能够更好地提高通信效率；针对网络嵌入问题，本文设计了将环、Mesh和Hypercube通信模式嵌入RP（k）互连网络的高效算法，使得在这些网络上已开发的应用能够高效地移植到RP（K）网络上。经过三年深入的研究，达到了预期的目的，取得了理想的结果，本文的主要创新点如下： ① 提出了一类基于Petersen图的互连网络拓扑结构RP（k）。该网络的连接度为5，直径为[k／2]+2；该网络具有短的网络直径、简单的拓扑结构、方便的路由策略；该网络硬件复杂度低、实现简单；在环、Mesh和Hypercube上设计的算法能够高效地嵌入RP（k）。同时，针对不同的互连网络规模，本文对该网络进行了扩展，提出了RP（P，k₁，k₂）网络拓扑，并讨论了其性质。 ② 设计了RP（k）互连网络上的路由算法，主要设计了点点路由、置换路由、广播路由和All-to-all路由算法。这些算法的通信次数分别为[k／2]+2、k+5、[k／2]+2、k+5。这样，RP（k）网络和其上的路由算法为并行体系结构提供了一个实用的工具集。同时，在RP（P，k₁，k₂）网络上，本文也设计了以上四个通信模式的路由算法，它们的通信次数分别为[k₂／2]+[k₁／2]+2、4+m{k₂，k₁}+（k₂-1）^*（k₁-1）、[k₂／2]+[k₁／2]+2和10^*k₁*k₂-4。 ③ 提出了将Ring和Mesh嵌入RP（k）网络的算法，证明了RP（k）网络是一个Hamiltonian图。考虑到网络的容错情况，当RP（k）网络中每个片有一个节点出现故障时，去掉故障节点和相应的边，得到互连网络RP-1（k），我们证明了该网络也是Hamiltonian图。因此，可以分别将10*k和9*k个节点的环嵌入到RP（k）和RP-1（k）网络中去。同时，我们也设计了将2-D mesh嵌入RP（k）网络的方法，取得了良好的嵌入性能。 ④ 基于光RP（k）网络，本文设计了一个实现n维Hypercube通信模式的算法，该算法最多需要max{2，[（5／3）^*2^n-5]}条波长。同时，设计了一个将n维Hypercube嵌入环网络

全文目录

独创性声明  2
关于论文使用授权的说明  2-3
摘要  3-5
英文摘要  5-7
目录  7-10
第一章绪论  10-15
  1.1 研究背景  10
  1.2 并行计算模型  10-12
  1.3 互连网络  12-13
  1.4 论文的主要工作及创新  13-14
  1.5 论文的结构  14-15
第二章影响并行程序性能的因素分析  15-31
  2.1 引言  15
  2.2 影响存储性能的因素分析  15-22
    2.2.1 系统结构  15-16
    2.2.2 基本概念  16-18
    2.2.3 存储效率分析  18-22
  2.3 算法的CACHE分析模型  22-23
    2.3.1 算法的cache相关性分析  22-23
    2.3.2 程序存储效率  23
  2.4 影响SMP存储性能的因素  23-25
  2.5 影响通信性能的因素分析  25-30
    2.5.1 少量数据通信  25-26
    2.5.2 程序中通信特征  26-27
    2.5.3 大量数据通信示例  27-30
  2.6 结论  30-31
第三章一种异步BSP模型及其程序优化技术  31-44
  3.1 并行计算模型  31-34
    3.1.1 并计算模型概况  31
    3.1.2 PRAM与共享存储类模型  31-32
    3.1.3 消息传递模型  32-33
    3.1.4 层次模型  33-34
  3.2 BSP及A-BSP模型  34-38
    3.2.1 BSP模型  35-36
    3.2.2 A-BSP模型  36-38
  3.3 CSA-BSP模型  38-40
  3.4 基于CSA-BSP的性能分析  40-43
    3.4.1 程序的执行时间  41
    3.4.2 程序执行时间的和  41-42
    3.4.3 数据划分带来的影响  42-43
  3.5 结论  43-44
第四章一种实用的互连网络RP(k)及路由算法  44-60
  4.1 引言  44
  4.2 互连网络概况  44-48
    4.2.1 环、Torus网络  45
    4.2.2 Hypercube网络  45-46
    4.2.3 Butterfly网络  46
    4.2.4 一类由Caylay图生成的网络  46-47
    4.2.5 其它一些互连网络  47-48
  4.3 互连网络RP(k)  48-49
    4.3.1 Petersen图及其性质  48
    4.3.2 RP(k)的结构  48-49
  4.4 RP(k)的性质  49-51
  4.5 RP(k)上的路由算法  51-58
    4.5.1 基本符号和相关概念  51-52
    4.5.2 点点通信算法  52-53
    4.5.3 置换路由  53-56
    4.5.4 广播路由  56-57
    4.5.5 All-to-All  57-58
  4.6 结论  58-60
第五章环、MESH嵌入RP(k)网络  60-73
  5.1 引言  60-61
  5.2 网络嵌入的概念  61-62
  5.3 环嵌入RP(k)网络  62-65
  5.4 二维MESH嵌入RP(k)  65-72
    5.4.1 由Mesh到RP(k)的映射  65-67
    5.4.2 min{a,b}≤10时的嵌入算法  67-70
    5.4.3 当a,b＞10时,mesh嵌入RP(k)的算法  70-72
  5.5 结论  72-73
第六章一类层次环网络HRN的构造及路由算法  73-82
  6.1 引言  73-74
  6.2 层次环网络的构造及性质  74-75
    6.2.1 层次环网络的构造  74-75
    6.2.2 HRN(G,K_1,…,K_m)网络的性质  75
  6.3 层次环互连网络的路由  75-76
  6.4 RP(P,k_1,k_2)互连网络  76-77
  6.5 RP(P,k_1,k_2)互连网络的路由算法  77-81
  6.6 结论  81-82
第七章互连网络的性能参数  82-93
  7.1 引言  82
  7.2 互连网络性能的评价参数  82-83
  7.3 网络直径对通信性能的影响  83-84
  7.4 最优节点分组  84-86
  7.5 互连网络的最优分划  86-88
  7.6 网络的最优分划算法  88-92
    7.6.1 网络中心点  88-90
    7.6.2 求网络中心点的算法  90-91
    7.6.3 网络分划  91-92
  7.7 结论  92-93
第八章光RP(k)网络上HYPERCUBE通信模式的波长指派算法  93-106
  8.1 引言  93
  8.2 基本知识  93-94
  8.3 基于HYPERCUBE通信模式的波长指派  94-97
    8.3.1 Hypercube性质  94-95
    8.3.2 3维Hypercube嵌入Petersen图  95-96
    8.3.3 n维Hypercube嵌入RP(k)  96-97
  8.4 HYPERCUBE嵌入环的一种算法  97-102
  8.5 光RP(k)网络连接的建立策略  102-104
    8.5.1 节点(k,j)使用波长λ_(k*10+j)  102-103
    8.5.2 节点(k,j)使用波长λ_j  103
    8.5.3 一般情况  103-104
  8.6 结论  104-106
第九章结论及进一步的工作  106-110
  9.1 论文的主要创新  106-107
  9.2 进一步的工作  107-110
参考文献  110-117
致谢  117-118
作者简历  118-119

高效并行计算系统中的计算模型与通信网络

内容摘要

全文目录

相似论文