论文部分内容阅读
高性能计算机是一个可以处理大型应用和处理大数据的计算系统。为了充分发挥高性能计算机的特性,向用户提供满意的服务质量,这就要求计算系统必须是可靠的。随着高端计算机系统(特别是超级计算机)中计算结点、芯片等组件的快速增加,连接这些组件的互连网络规模也在相应扩大,互连网络中出现故障结点的可能性急剧增大。因此,互连网络的可靠性在很大程度上决定了整个计算机系统的可靠性。本文的主要任务有两个:(1)以连通度和诊断度作为互连网络的可靠性度量指标,研究结点故障对互连网络可靠性的影响;(2)设计典型互连网络的故障诊断算法。本文取得的具体研究成果如下:1.虽然光互连具有很高的带宽和很低的功耗,但是当传输距离达到毫米级式,电互连的性能却表现得更好,为了充分利用光、电互连各自的优点,前人提出了光电转换互连网络——OTIS——使之成为互连网络领域的研究热点。众所周知,具有n2个结点的OTIS,其连通度为n。本文进一步研究了具有n2个结点的OTIS的连通度,证明了(1)当n为偶数时,只需要添加少量边,就可以将OTIS网络的连通度提高;(2)在故障结点数不超过一个阈值时,OTIS网络中依然存在一个大型连通分支完成系统工作。2.互连网络中任意结点的邻居结点同时发生故障的概率相对较小,条件连通度就是忽略了这样的小概率事件后引入的容错性衡量标准。k n个结点的Hypermesh网络作为一种新型的光互连网络,具有很多优良的互连网络特性,其可靠性得到了人们的广泛关注。近年来,人们用公式化的最小点割集研究了互连网络的条件容错性,清晰的展示出任一结点的g-无故障邻居结点的存在,为此,本文研究了Hypermesh网络中g-无故障组件的邻居结点的规模,即最大条件连通子图的大小。3.相较于传统的精确诊断,悲观诊断以允许一个无故障结点被误诊断的代价,可以显著的提升系统的自诊断能力。光多网格超立方体集成了超立方体和mesh网络的优良拓扑性质,作为一种实用的新型光互连网络得到了关注。在PMC模型下光多网格超立方体的精确诊断度得到了验证,本文进一步证明了光多网格超立方体的悲观诊断度是精确诊断度的2倍,并利用圈分解技术设计了其在PMC模型下的快速故障诊断算法。4.折叠立方体网络是一类规则互连网络拓扑结构,它具有同维超立方体所没有的优良拓扑性能。近年来,人们研究了折叠立方体网络在PMC模型和比较模型的精确诊断度、条件诊断度和强诊断度等问题。本文在比较模型下,证明了折叠立方体网络的悲观诊断度是其精确诊断度的2倍,并设计了一个线性时间复杂度的故障诊断算法综上所述,本文的主要工作可以总结为:研究了两类互连网络的容错性能,并针对另外两类互连网络设计了高效率的故障诊断算法。这些研究成果为上述互连网络的推广应用奠定了一定的理论基础。