第1章绪论
1.1研究背景和意义
高性能计算（high performance computing，HPC）作为计算机科学的一个分支，主要是指从软件开发、并行算法和体系结构等方面研究开发高性能计算系统的技术。作为信息领域的前沿高技术，高性能计算已然成为衡量一个国家的综合国力和科技发展水平的重要标志。在一些新兴的学科，如核研究、生物技术、航空航天及新材料技术等领域，高性能计算已成为科学研究的**工具之一。另外，随着高性能计算性能的提高、成本的降低，高性能计算也逐渐走向更广泛的行业应用，如石油勘探、机械设计、天气和灾害预报、生物制药、金融分析、决策支持系统等大数据处理方面以及政府机构、教育、搜索引擎、信息中心等网格计算和协同工作等。它在各领域发挥了巨大的应用价值。这不仅节约了研发成本，更减少了大量时间消耗，提高了研发进度和效率。高性能计算已然成为科学研究和科技创新的主要工具，能够促成研究理论或实验方法不能取得的科学发现和技术创新。
TOP500排行榜通常被认为是世界上评估高性能计算发展现状的指标。在国家对高性能计算的大力支持下，我国的高性能计算技术呈现快速发展的良好势头。2017年，中国拥有的超高性能计算机数量居全球*位，并且仍在保持。在2019年国内高性能计算机TOPIOO排行榜中，无锡国家超算中心的神威-太湖之光蝉联**，其每秒峰值速度达9.3亿亿次[1]。同时，它也是世界TOP500超算中的第三名，此前曾蝉联过四次TOP500冠军。在国内，六个国家超级计算中心（无锡中心、天津中心、济南中心、深圳中心、长沙中心、广州中心）及一些地方、高校、科研院所的高性能计算中心纷纷建成并投入使用。如今，它们已经成为我国科学研究、信息处理、技术开发和大数据处理的关键计算平台并在社会各领域发挥着巨大的作用。
随着髙性能计算的应用领域和规模进一步拓宽增大，各领域对高性能计算的依赖程度越来越高。进而，在一些关系到国计民生安全等的重要领域，也对高性能计算的可靠性提出了特殊要求。如果系统不能稳定可靠地工作，那么将会造成巨大的损失，甚至导致不可估计的灾难性后果。例如，12306火车售票网络，天气预报系统，机械设计系统，金融分析系统，银行出纳系统，航空航天的设计系统，卫星
发射太空计划等。若运行它们的系统出现故障，其损失是巨大可怕的。然而，系统发生故障是客观不可避免的，绝对无故障的系统是不存在的。但是人们期望系统在部分处理器或链路发生故障时，仍然可以正常或基本正常地工作，不至于产生严重的后果。故而，在设计高性能计算系统时，除了高速度和高性能外，高可靠性应放在设计的*位。
由于处理器频率等性能的提升幅度越来越小且摩尔定律也渐进极限，通过大规模多处理器互联组网是提升高性能计算能力的发展趋势之一。当前主流的高性能计算系统多是采用Cluster（集群）和MMP（大规模并行处理），将多个处理器按专门的互联网络组织在一起实现节点间的通信。特别是在超大规模集成电路技术的驱动下，系统可以集成上万个处理器，它们之间依靠互联网络实现通信。系统中处理器规模的扩大势必造成它们之间通信开销的增大，成为制约系统总体性能的主要因素。研究表明高性能计算不仅依赖于处理器的浮点运算速度（理论峰值），还依赖于数据在系统中的存取和传输速度等[11。因此，高性能计算系统的性能取决于其互联网络性能。
随着系统中处理器数量不断扩大，系统内部的结构也越来越复杂。这使得处理器出现故障的概率也随之增加，从而导致系统在信息处理、存储及传递过程中出现错误的可能性增大。在高性能计算系统中处理器发生故障的概率占整个系统组件故障概率的50%以上[2]。为了保证系统的可靠性，就必须要有一定的容错性。如果在超大规模多处理器系统发生故障时仍具备功能，Esfahanian称系统为容错的[3]。系统的容错性研究成为系统可靠性的研究热点。
同时，为了保证系统的可靠性，系统在发生故障时要能够及时识别出故障处理器并用非故障处理器来替换。系统的故障诊断是目前较为有效的能够保证系统可靠性的一类诊断方式，它的目标是按照一定的规则识别出系统中的故障处理器。如果系统中故障处理器数目不超过t且不经替换可一次识别出来，系统是t可诊断的。系统的故障诊断研究成为系统可靠性的另一研究热点。
系统互联网络的可靠性研究通常也称网络的容错性研究。因此，互联网络的容错性成为评价系统可靠性的关键指标之一。注意到互联网络的拓扑结构可以用一个图来刻画，其点集和边集分别由节点和节点间的连线构成。进而，互联网络的容错性研究也就转化成对图的容错性研究。连通度和诊断度通常被用来衡量互联网络的可靠性和故障诊断能力。经过国内外学者多年的研究，采用图论的方法研究互联网络的容错性已经取得了丰硕的成果，并取得了一系列有价值的研究成果，尤其是在诊断度方面，许多类型的互联网络的诊断度得到了研究证明。
由于本书的主要工作集中在对互联网络系统可靠性和故障诊断的研究，研究的思路，一是分析并选取具有高容错性的互联网络，以保证系统发生一定的故障而性能不降低；二是对给定的互联网络研究它的故障诊断度，以便发生故障后能够及时诊断出从而保证系统的可靠性。
1.2图的基本定义及符号
本书所研究的图均是有限无向简单图。图是一个有序的三元组，简记，其中和如分别表示图的顶点集、边集和关联函数。下面介绍本书中用到的一些基本概念和符号。书中其他未定义而直接使用的一些符号和术语参考文献。
定义1.2.1
定义1.2.2
定义1.2.3
定义1.2.4
定义1.2.5
定义1.2.6
定义1.2.7
定义1.2.8
定义1.2.9
定义1.2.10
定义1.2.11
定义1.2.12
定义1.2.13
定义1.2.14
是的一条路，其中仅相邻。若将路的起点和终点相连，则称是的一个圈。为方便描述，通常把从起点％到终点的路记为（如，办）路。路（或圈）经过的点称为内部点，所经过边的条数称为该条路（或圈）的长。长为的路（或圈）称为k-路（fc-圈）。由于研究的图为简单图，故*小的圈为3-圈。仅包含一个圈的连通图称为单圈图。
定义1.2.15图G中*短的圈的长称为围长，记为g（G）。
定义1.2.16
定义1.2.17图G的自同构是指G到其自身的一个同构。对于简单图G来说，它的一个自同构可以认为是在V上保持相邻性的一个置换，这种置换的集在通常的合成运算下构成一个群/XG），称其为G的自同构群。
定义1.2.18图G称为点可迁的，若对任意两点u和％存在r（G）中的一个元素使得
定义1.2.19
定义1.2.20
1.3互联网络的概述及容错
互联网络（interconnection network）通常是若干处理器按照一定的拓扑结构，通过元器件以一定的控制方式实现处理器间相互连接和数据传输的网络。在一个互联网络中，每个处理器有本地内存和资源，它通过通信链路与其相邻处理器连接。它对于保证各处理器无等待计算起着极为重要的作用。从某种意义上说，高性能计算系统性能的关键取决于该系统各处理器间数据传输的能力而不是处理器的性能。因此，互联网络是高性能计算系统性能的重要组成部分，它对系统的运行有着极大的影响[5]。而互联网络的可靠性是衡量一个互联网络性能优劣的重要参数。如何选择或设计一个可靠的互联网络拓扑结构，已成为学者研究的热点。
1.3.1设计规则及方法
高性能计算系统的互联网络设计时通常要遵循两大基本原则，即高性能和低成本。但其性能和成本受众多因素影响。在实际设计时，二者也通常需要找到一个平衡点。单从其拓扑结构上来说应遵循以下基本原则。
（1）固定或小的度。受限于处理器单元的端口数目，节点的度应该较小或固定。同时，较小的节点度意味着布线简单，从而使得成本降低。
（2）高对称性。节点以相同的连接方式接入网络，使得网络中各元器件负载保持平衡。
（3）低延迟性。互联网络的直径应较短且平均距离也应较小。这不仅会使得节点间通信延迟减小，也能降低建造和维护费用，同时提高互联网络的有效性。
（4）简易的路由算法。互联网络的通信开销增大，使得通信必须要经过路由选择。路由算法的优劣决定着互联网络的效率和性能。
（5）高容错性。互联网络中任意两点之间存在多条内点不交的路径。一旦某些元器件发生故障，系统可以有多种路由选择从而保证正常的通信及运行。
（6）可扩展性。在原有基础上扩大网络规模，同时保持原有互联网络的性质不变。可扩展性有利于系统的升级扩大，是衡量网络好坏的一个重要因素。
（7）可嵌入性。新的互联网络应能包含已有的简单网络。这样有利于移植和嵌入针对简单网络的结构和性质以及相关的算法，进而降低开发的软成本。
（8）有效的布图算法。有效的布图算法能够解决大规模集成电路板线路的交叉问题，使得互联网络能在多个或一个平面图内简易实现。
为了设计出高性能低成本的互联网络，常用的拓扑结构设计方法有线图法、笛卡儿乘积法和凯莱法[8]。
（1）线图法是从一个现有的图获得另一个与之相关图的重要构图方法，也是互联网络设计的一个重要方法。其思想实际上就是点边变换。deBruijn图和Kautz图是两大类著名的线图。它们被认为是未来实现并行计算替代超立方体一类互联网络。
（2）笛卡儿乘积法是从若干特定的小网络构造大网络的*有效的方法之一。由这种方法构造出来的新网络不仅包含了其原有的小网络作为它的子网络，也保留了小网络原有的性质。因而，它也成为大规模互联网络设计的一个重要的方法。超
立方体就是通过该方法构造得到的一类著名的网络。超立方体作为高性能计算系统互联网络的*选拓扑结构，具有正则性、对称性、点可迀性及递归性等许多优良的网络特性，然而它的直径较大。为了弥补它的不足，通过对超立方体进行不同的变形又派生出了许多的变形互联网络。
（3）凯莱法是构造高对称性网络的一种设计方法。由于该方法基于有限群，因此称其为群论法或代数法。由该方法构造的图称为凯莱图且都是点可迀的。故而该类型的网络中任何一个节点对于网络都是等同的，即使某个节点出现故障也不影响其余网络的结构性能。因此，该方法构造的网络非常有利于算法的设计和模拟。凯莱图有很多种，如泡型图、星图和交错群图等。因为凯莱图都具有高对称性，所以它们也被认为是下一代高性能计算互联网络替代超立方体的选项。
1.3.2常见的类型
按拓扑结构的不同，互联网络可以分为静态互联网络和动态互联网络。在动态互联网络中，节点间通过交换元件的设置建立不同的网络连接。这种连接方式是按需建立的，也被称为间接互联网络。然而随着网络节点数目的增多，交换开关反而会成为系统的通信瓶颈。在静态互联网络中，节点间有固定的直接连线，也被称为直接互联网络。因此，常采用图论模型来描述互联网络的性能并用图的某些参数来衡量。在多处理器系统中，互联网络的拓扑结构可以用图来表示，其中顶点表示处理器（节点），边表示处理器间的通信链路（节点间的连线）。
在互联网络研究初始阶段，常见的互联网络拓扑结构有线性网（lineararray）、总线（bus）、环网（torus）、树网（tree）、星型网（star）、网格（mesh）、立方连接环（CCC）、全互联网等。全互联网丨完全图）虽是具有*高效率的网络拓扑结构，但建设成本巨大，也受元器件引脚限制。而随着系统规模的增大，系统对互联网络的要求也越来越髙。许多学者对互联网络的拓扑结构展开了研究，各种髙性能互联网络也相继被提出。于是，超立方（hypercube）[9]、交叉立方体（crossed cube）[10]、莫比斯立方
展开
