互连网络的连通性和诊断度

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