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

大规模并行计算机光互连网络研究

作　者: 刘兴长
导　师: 杨小帆
学　校: 重庆大学
专　业: 计算机应用技术
关键词: 大规模并行计算机光互连网络系统级故障诊断最优重构 DNA计算
分类号: TP338.6
类　型: 博士论文
年　份: 2008年
下　载: 285次
引　用: 0次
阅　读: 论文下载

内容摘要

目前,以高性能计算机为基础的计算科学已经成为继理论科学和实验科学之后人类科学研究的第三大支柱,高性能计算机的影响也已经拓展到经济、公共安全和国家安全。在高性能计算机的发展中,超大规模并行处理已成为必然趋势。在大规模并行计算机中,随着处理器规模的不断增大,以及单个处理器性能的不断提升,多处理器之间经过互连网络进行通信的开销也随之大大增加。但是,传统电互连由于自身固有缺陷,包括带宽限制、阻抗不连续、时钟歪斜、电磁干扰(EMI)现象严重、功耗高、互连密度受限等,无法满足大规模并行计算机对互连网络的需求,成为阻碍系统总体性能提高的瓶颈之一。光互连因其自身特点,包括极高的传输带宽、极低的传输时延、极高的并行性、极低的功耗、通道等程、优良的网络拓扑特性等,成为大规模并行计算机互连网络研究中的热点。本文对大规模并行计算机系统中的光互连网络技术,主要是光互连网络模型,包括模型的构造理论、故障诊断方法、最优重构问题等,进行了研究。本文的主要贡献如下:①分析了传统图论在光互连网络研究中的局限性,得出了结论:由于每条边只能关联到两个结点,传统的图无法准确反映光互连网络的本质特性,基于传统图论的研究方法不能充分发掘光互连技术的潜在优势。基于以上原因,给出了一种光互连网络建模方法──基于超图理论的方法,并分析了超图理论应用在光互连网络模型研究中的优越性。②目前,光互连器件的研究已经取得了大量的成果,但与之对应的是,光互连网络模型的研究还较少,并且大多数集中在新网络模型的构造及分析,尚未涉及光互连背景下的故障诊断问题。因此,本文对光互连并行系统的故障诊断问题进行了探索性的研究,给出了超图模型下系统级故障诊断问题的相关规范及定义,从而使光互连并行系统的故障诊断可以直接借鉴传统图模型下系统级故障诊断的研究成果。③对一类典型的光互连系统─—Hypermesh的故障诊断问题进行了研究。证明了HMn,k光互连系统的一步诊断度为n(k?1)。通过将HMn,k分解为kn?cn个互不相交的、同构于HMcn,k的导出子图,{HMn,k [Vx]: x∈{k?1,···,0} n?cn},得到了HMn,k的一个圈分解CD(HC),其中cn = ?l og k (nk?k+1)?。基于这种圈分解技术,给出了一个时间复杂度为O(knn(k?1))的一步t-故障诊断算法,证明了该算法的正确性,分析了该算法的复杂度。④对一类通道可再分的智能光背板的重构问题进行了分析。通过特定条件的限定,将其中一个最优重构问题归结为经典的NP难问题──最优线性排列(OLA)问题。DNA计算有望被用于求解这类NP-难问题。基于一种DNA计算模型: Adleman-Lipton-sticker模型,给出了一个用于解OLA问题的DNA算法。对于n个结点、m条边的无向简单图G,该算法的初始解空间大小为2nK,存储链由nK + n + m + L + 1个位区组成,需要2n个试管,并通过O(n3log2 n)次试管操作完成,其中,K = ?l og 2n?, L = ?l og 2(n m)? + 1。当分子生物技术的进步足以保证DNA计算可行时,该算法就能有效地用于解决中等规模OLA问题,那时就可以通过预先编程的方式,将该算法得到的解用于控制智能光背板的重构,使互连网络资源的配置达到最优化。许多研究已经证明,光互连具有电互连无法比拟的优越性。但是,光互连要实际应用到大规模并行计算机中,还需要解决许多问题。本文只是在这方面进行了一些初步尝试,对于一些值得进一步研究的光互连网络模型问题,作者也在论文中进行了说明。可以预见,随着光电子和集成光学器件的发展,以及光互连网络的理论和技术的深入研究,光互连的总体性能优势将会逐渐体现出来,基于光互连的并行高带宽传输必将使大规模并行计算机系统的性能有相当显著的提高。“处理由电来做,传输由光来做”,将是未来高性能并行计算系统结构的主要途径之一。

全文目录

摘要  5-7
ABSTRACT  7-12
1 绪论  12-21
  1.1 高性能计算发展概况  12-14
  1.2 并行计算机发展趋势  14-17
  1.3 光互连研究的意义及概况  17-18
  1.4 本文研究内容及主要贡献  18-19
  1.5 论文组织  19-21
2 并行计算机中的光互连网络技术  21-44
  2.1 并行计算机体系结构  21-23
  2.2 互连网络类型及性能指标分析  23-33
    2.2.1 互连网络类型  23-29
    2.2.2 互连网络性能指标  29-32
    2.2.3 动态互连网络性能分析  32-33
    2.2.4 静态互连网络性能分析  33
  2.3 光互连的优点分析  33-37
  2.4 光互连技术研究现状  37-43
    2.4.1 光互连技术的发展历史  37-38
    2.4.2 光互连技术的研究现状  38-41
    2.4.3 新型光互连网络结构介绍  41-43
  2.5 小结  43-44
3 基于超图的光互连网络模型  44-54
  3.1 图论及其在电互连网络中的应用  44-45
  3.2 传统图论应用在光互连网络中的局限  45-48
  3.3 超图理论及其在光互连网络中的应用  48-50
  3.4 一类典型的光互连网络：Hypermesh  50-53
    3.4.1 Hypermesh 定义  50-52
    3.4.2 Hypermesh 网络性能分析  52-53
    3.4.3 Hypermesh 光互连网络实现  53
  3.5 小结  53-54
4 光互连并行计算机的系统级故障诊断  54-79
  4.1 系统级故障诊断概述  54-65
    4.1.1 系统级故障诊断的基本思想  54-56
    4.1.2 系统级故障诊断的基本概念  56-61
    4.1.3 系统级故障诊断的研究内容  61-62
    4.1.4 系统级故障诊断类型及研究现状  62-65
  4.2 PMC 模型  65-66
    4.2.1 PMC 模型概述  65-66
    4.2.2 PMC 模型下的诊断圈  66
  4.3 一步 t-故障诊断  66-68
    4.3.1 一步t-故障诊断定义  66-67
    4.3.2 一步t-故障诊断研究现状  67
    4.3.3 PMC 模型下的一步t-可诊断系统  67-68
  4.4 光互连并行计算机系统的故障诊断  68-69
  4.5 Hypermesh 的诊断度  69-71
  4.6 Hypermesh 的一个故障诊断算法  71-78
    4.6.1 Hypermesh 的圈分解特性  71-74
    4.6.2 算法框架  74-76
    4.6.3 算法正确性证明  76-77
    4.6.4 算法复杂性分析  77-78
  4.7 小结及下一步工作  78-79
5 基于DNA 计算的光互连网络重构算法  79-101
  5.1 DNA 计算的基本原理及研究现状  79-83
    5.1.1 DNA 分子结构  79-80
    5.1.2 DNA 计算的基本原理  80-81
    5.1.3 DNA 计算的研究现状  81-82
    5.1.4 DNA 计算面临的技术难点  82-83
  5.2 一种 DNA 计算模型：Adleman-Lipton-sticker 模型  83-85
    5.2.1 信息表示  83-84
    5.2.2 DNA 操作  84-85
  5.3 最优线性排列问题（OLA）  85-90
  5.4 一个基于DNA 计算的OLA 算法  90-100
    5.4.1 基本思想  90
    5.4.2 DNA 分子链设计  90-91
    5.4.3 DNA 计算子程序  91-97
    5.4.4 基于DNA 计算的OLA 算法  97-98
    5.4.5 OLA 算法的复杂度分析  98-100
  5.5 小结及下一步工作  100-101
6 总结及下一步工作  101-104
  6.1 本文完成的工作  101-102
  6.2 下一步研究展望  102-104
致谢  104-105
参考文献  105-118
附录  118-120

大规模并行计算机光互连网络研究

内容摘要

全文目录

相似论文