论文部分内容阅读
高性能计算机是一个可以处理海量数据和大型应用的计算机系统,它在教育、科研、石油、气象等多个领域发挥着日益重要的作用。近年来,随着高性能计算机技术应用的不断加深,系统内的处理器变得越来越多,由此引起的用于连接处理器的互连网络的规模也随之相应扩大。高性能计算机系统的性能在很大程度上取决于互连网络的性质。 衡量一个互连网络性质优劣的重要标准是图的嵌入能力。作为常用的网络拓扑结构,圈和路径具有结构简单、度数小、通信代价小等优良特性,它们在并行计算等领域被大量应用。因此,互连网络中的圈和路径嵌入问题也是并行处理的一个重要课题。然而,将任意长度的圈和路径嵌入到一般互连网络中的求解问题是NP难的。互连网络的哈密顿性质可以被看作是在互连网络中圈和路径嵌入的一个特例。它在数据通信中具有重要的应用,如果在互连网络的多播路由算法中使用哈密顿圈或哈密顿路径,则能够有效地减少或避免死锁和拥塞。此外,哈密顿性质在互连网络的故障诊断中也有重要应用。因此,研究互连网络的哈密顿性质具有重要意义。 随着并行计算机系统规模的不断扩大,系统中处理器或处理器间通信链路不可避免地会出现故障,这就带来了系统在可靠性和可使用性方面的问题。解决这一问题的方法就是容错技术,而故障诊断是进行容错处理的关键步骤。故障诊断就是识别出发生故障的处理器或通信链路,它可以在不增加系统额外硬件成本和维护开销的情况下,达到提高系统可靠性和可用性的目的。因此,研究互连网络的故障诊断是一个具有重要意义的课题。 交换交叉立方体网络(Exchanged Crossed Cube,简称为ECQ网络)是一种性能优良的互连网络,如具有较好的路由性能(低直径)、较少网络链路数、高扩展性等,并能够支持超大规模的互连网络。研究ECQ网络的可嵌入性、容错性和可诊断性,可以为其应用于高性能计算等领域提供理论依据。因此,该研究具有重要的理论与应用价值。本文研究内容分为以下三个部分: 1.我们证明了ECQ网络具有很好的哈密顿性质,主要结论如下: (1)证明了当s≥2和t≥3时,ECQ(s,t)中任意两个不同顶点之间不仅存在哈密顿路径,而且存在比哈密顿路径长度少1的路径。 (2)给出了ECQ(s,t)上任意两个不同顶点之间一条哈密顿路径的构造算法,并分析了算法的时间复杂度。 (3)在(2)的基础上,我们还给出了ECQ(s,t)上哈密顿圈的构造算法,并分析了算法的时间复杂度。 (4)我们证明了对于任意的整数s≥2,t≥3和s≤t,ECQ(s,t)是(s-2)-哈密顿连通的和(s-1)-哈密顿的。 2.我们研究了ECQ网络的可嵌入性问题,给出了如下研究结果: (1)对于任意的整数s≥2和t≥3,证明了在ECQ(s,t)中包含长度从4到2s+t+1的圈(除ECQ(2,3)和ECQ(3,3)中不包含长度为9的圈外)。 (2)证明了对于任意的整数3≤s≤t,ECQ(s,t)中任两个不同顶点之间都存在长度为l的路径,其中「s+1/2」+「t+1/2」+5≤l≤2s+t+1?1。注意:ECQ(s,t)的直径是「s+1/2」+「t+1/2」+2。 (3)证明了对于任意的整数s≥3和t≥4,ECQ(s,t)中任两个不同顶点之间都存在长度为l的路径,其中「s+1/2」+「t+1/2」+4≤l≤2s+t+1-1。 3.我们研究了ECQ网络的可诊断性,得出了如下结论: 对于任意的整数1≤s≤t,证明了ECQ(s,t)在悲观策略下基于PMC模型和MM*模型的诊断度都为2s。 综上所述,在相同维度下,尽管ECQ网络仅有交叉立方体网络中约一半的边数,但它依然很好地保持了交叉立方体网络所拥有的哈密顿性质、圈嵌入能力和路径嵌入能力;ECQ网络除了比交换超立方体网络拥有较小的通信传输延迟外,其诊断能力依然与相同条件下交换超立方体网络的诊断能力一样。