互連網絡的故障診斷研究綜述*

郭 晨，彭 碩，王 博，肖志芳，劉 華

井岡山大學 電子與信息工程學院，江西 吉安 343009

1 引言

超大規(guī)模集成電路和晶片規(guī)模集成電路的飛速發(fā)展，推動著并行計算技術的不斷進步。當前，幾乎所有的自然科學都轉向了精確化和計算化的道路，從而產生了一系列諸如計算物理學、計算化學、計算生物學、計算地質學、計算氣象學和計算材料學等計算科學。并行計算技術的發(fā)展極大地增強了人們從事科學研究的能力，加速了科技轉化為生產力的過程，深刻地改變著人類認識世界和改造世界的方法與途徑。

并行計算技術是將復雜的計算任務交由一組處理器來協同完成。因此，并行計算需要一個支撐通信和數據交換的運行策略[1]。互連網絡（interconnection network）就是這么一個專門服務于處理器和內存模塊的通信機制[2]?，F行互連網絡的一個典型事例就是擁有成千上萬個處理器的超級計算機系統。以2017年蟬聯世界最強超級計算機TOP10第一名的神威?太湖之光為例，它使用了40960塊國產的申威26010眾核處理器。在一個規(guī)模如此巨大的計算機系統的運行過程中，出現處理器故障的風險很高，而處理器故障若不能被及時診斷出并得到正確處理，將可能帶來極其嚴重的災難性后果。而如果超級計算機系統是按照具備一定規(guī)則的互連網絡拓撲結構進行連接，通過對互連網絡拓撲結構的可靠性研究，可以得出其在各種條件下的診斷度（診斷能力）。當故障處理器數目低于診斷度時，就可以根據簡單的診斷算法在帶電狀態(tài)下進行快速的診斷，找出故障處理器的所在位置，進而進行及時的修復和更換處理。由此，引發(fā)了學界對互連網絡診斷度為代表的可靠性問題的研究，其中又以系統的運行可靠性最為典型。維持系統運行可靠性的主要手段之一就是系統的故障診斷。當前，仍有部分系統還在沿用傳統的故障診斷方式，通過一個所謂的“中心處理器”來測試每一個處理器的運行狀態(tài)，從而給出故障評價。這種診斷方式工作量巨大并且多數情況都需要斷電乃至拆解系統，既不準確又缺乏實際的操作性。因此，Preparata等人提出了一種基于圖論的“系統級故障診斷”（system level diagnosis）理論[3]。系統級故障診斷充分利用了每一個處理器的處理能力，讓處理器之間進行相互測試，通過綜合分析來識別故障。通常情況下系統級故障診斷可以帶電進行。因此，系統級故障診斷既經濟又便捷，是多處理器并行計算機故障診斷的主要發(fā)展方向之一。

使用系統級故障診斷進行故障診斷的前提是要得到互連網絡拓撲結構的各種診斷度性能指標。當前，規(guī)則互連網絡僅有超立方網絡在得到較為完整的診斷度研究之后被成功地應用到INTEL和NCUBE計算機[1]。而以超立方網絡變種為代表的其他互連網絡的故障診斷研究尚不系統，普遍缺乏完整的診斷度參數，這種情況勢必影響到互連網絡在多處理器并行計算機中的應用和推廣。基于此，本文以超立方網絡及其變種為代表的互連網絡為研究對象，通過拓撲結構研究對以超立方網絡及其變種為代表的互連網絡拓撲結構的繼承關系、拓撲性質、成本、連通度進行了系統分析。在此基礎上，系統闡述了互連網絡的故障診斷度研究現狀，包括精確故障診斷度、非精確故障診斷度、條件故障診斷度、順序故障診斷。并闡明了在互連網絡上執(zhí)行非精確故障診斷和順序故障診斷是進一步提高系統診斷能力，保障運行可靠性的有效手段，以及相關研究鮮見報道的研究現狀。最后指出包括互連網絡拓撲結構研究、互連網絡的非精確故障診斷研究和互連網絡的順序故障診斷研究在內的3個主要研究方向。本文的綜述為互連網絡的可靠性研究提供了較為完整的數據參數和關聯體系，從而促進互連網絡在多處理器并行計算機的應用和推廣。

2 互連網絡拓撲結構研究

互連網絡幾乎出現在所有涉及通信的計算機系統中。在設計一個系統的通信網絡時，需要考慮從連接的物理屬性到通信協議等諸多因素，而其中的首要問題是要確定連接的方式，也就是互連網絡的拓撲結構[4]?；ミB網絡的拓撲結構研究是互連網絡研究的核心問題之一，它直接決定了系統的協同處理能力[1]?；ミB網絡的拓撲結構通常采用圖論表示，其中結點表示處理器，邊表示處理器之間的通信連接。在選擇互連網絡的拓撲結構時，需要著重考量網絡直徑、構造成本（連接邊數）和可靠性等因素。其中，網絡直徑是評價互連網絡靜態(tài)性能的主要參數之一，也是衡量并行計算速度的主要指標[5]，而構建成本通常以連接邊數的形式出現，可靠性則以連通度與診斷度為主要指標，體現出系統的容錯能力與診斷能力。

2.1 線性陣列和樹形結構

線性陣列和樹形結構被認為是最簡單的并行計算機互連網絡拓撲結構[6]。對于n個結點組成的線性陣列而言，它只需要n-1條邊就可以連通整個網絡，構造成本超低。但是，任何位置的故障就會使得線性陣列陷入癱瘓。樹型結構則是一個易擴展的無環(huán)圖，其中每一條邊都是一條割邊，任意兩個結點都只有唯一的一條路徑連通。因此，任何位置的故障也會使得樹型結構不連通。與線性陣列類似，樹型結構的構造成本也很低。由于結構都無環(huán)，線性陣列和樹形結構的網絡直徑都等于最長路徑的長度，具體數值與總結點數在同一級別，這顯然過大。

2.2 超立方網絡

為了降低網絡直徑，學者們充分利用維數空間的優(yōu)點，相繼提出了 Cosmic cube[7]、N-cube[8]、Binaryn-cube[9]、Booleann-cube[10]等多種類似拓撲結構。Saad等人把這類高度并發(fā)并且松散耦合的互連網絡拓撲結構統稱為超立方網絡（hypercube，Qn）[11]。超立方網絡具有規(guī)則性、對稱性、網絡直徑小、連通性強、遞歸結構、可劃分性和相對較小的連接復雜性等優(yōu)點。基于超立方網絡的并行計算機由于具有高能力的互連性和更加優(yōu)秀的連通度，被認為是較為理想的并行計算機互連網絡拓撲結構之一[11]。然而，超立方網絡并沒有充分利用好其硬件條件來有效減低網絡直徑[4]，從而影響到整體的并行計算速度。

同時，超立方網絡的連接邊會隨著維數的增加成幾何對數增長，這種增長對于低維超立方網絡而言影響不大，但是對于高維超立方網絡而言影響巨大。同時，超立方網絡的結點數目被限定為2的n次方，因此超立方網絡的結點規(guī)模并不能隨需要進行任意的擴展[12]。基于此，后續(xù)又提出了新一代的超立方網絡拓撲結構，包括廣義超立方網絡（generalized hypercube）[13]、不完全超立方網絡（incomplete hypercube）[14]、超級立方網絡（supercubes）[15]和增量可擴展超立方網絡（incrementally extensible hypercube）[16]。但是這些拓撲結構不規(guī)則、不對稱、結點的度也差異較大，難以取代超立方網絡的地位。

2.3 扭立方網絡

為了使系統具有較好的實用性，通?；ミB網絡必須具有一定的規(guī)則性和可擴展性。一般的做法是通過讓互連網絡具有笛卡爾積構造性來實現[17]。其中最為極端的一個例子就是超立方網絡。雖然構建簡單和規(guī)則可以簡化對網絡直徑和路由的分析，但是這將會產生太多的對稱性（包括結點對稱和邊對稱），如圖1所示。通過笛卡爾積生成的超立方網絡包含有太多類似的通路，由此必然造成一個不必要的較大網絡直徑[17]。為了減低超立方網絡的網絡直徑，1987年，Hilbers等人根據特定規(guī)則對超立方網絡的邊實施“扭曲”（Twist）操作，提出了扭立方網絡（twisted cube，TQn）[17]。TQn保持了超立方網絡Qn原有的n正則性，整體連通度為n。如圖2所示，TQ3中任意兩個結點之間的最大距離是2，而圖1所示的超立方網絡Q3是3。因此，扭立方網絡幾乎降低了一半的網絡直徑，并且具有更好的漢密爾頓性質和嵌入性[18]。但是，扭曲操作勢必破壞超立方網絡的超高對稱性，使得扭立方網絡無法通過笛卡爾積生成[17]，從而失去結構的可劃分性，并且加大了連接復雜性。

Fig.1 Topology ofQ3圖1 Q3拓撲結構圖

Fig.2 Topology ofTQ3圖2 TQ3拓撲結構圖

2.4 折疊超立方網絡

為了減低網絡直徑，同時維系一定的對稱性，1991年，El-Amawy和Latifi提出了折疊超立方網絡（folded hypercube，FHn）[19]。折疊超立方網絡是在超立方網絡的基礎上，通過增加一些額外邊來降低系統的網絡直徑。FHn(n=3)的拓撲結構如圖3所示。折疊超立方網絡結點數與超立方網絡一樣，其網絡直徑卻幾乎只有超立方網絡的一半，而邊數更是比超立方網絡多出2n-1條。折疊超立方網絡保持了超立方網絡的部分對稱性，但是額外增加的2n-1條邊將較大程度增加系統的構造成本，嚴重影響到系統的性價比。

Fig.3 Topology ofFH3圖3 FH3拓撲結構圖

2.5 交叉立方網絡

為了減低網絡直徑，同時保持相對合理的對稱性和性價比，1991年，Efe提出了交叉立方網絡（crossed cube，CQn）[20-21]。交叉立方網絡是在超立方網絡的基礎上，通過關聯對[20]的對應關系“交叉”部分邊而形成的一種互連網絡拓撲結構。交叉立方網絡繼承了超立方網絡的規(guī)則性、遞歸結構、可劃分性、強連通性的特點，擁有和超立方網絡一樣的結點數、邊數和連通度[20,22-23]。如圖4所示，CQ3中結點之間的最大距離為2，同樣低于超立方網絡Q3的3。因此，交叉立方網絡以犧牲超立方網絡的超高對稱性為代價，縮小了幾乎一半的網絡直徑，并且表現出很強的嵌入性。

Fig.4 Topology ofCQ3圖4 CQ3拓撲結構圖

交叉立方網絡CQn與扭立方網絡TQn相比，在結點數、邊數、網絡直徑和連通度等多方面都具有相同的取值。但CQn具有在故障結點存在的條件下的哈密爾頓特性，該性質TQn不具備。同時TQn的扭曲操作具有雙向性，而CQn的關聯對交叉操作僅僅會使得最左邊的不同取值地址位和偶數地址位發(fā)生變化，這就會影響到特定結點間的連通，從而帶來了一定程度的不確定性，影響到系統的穩(wěn)定性[24]。

2.6 莫比烏斯立方網絡

“扭曲”和“交叉”等操作勢必降低互連網絡的動態(tài)性能，從而影響系統的信息交互能力。為了平衡互連網絡拓撲結構的靜態(tài)性能和動態(tài)性能，1995年，Cull等人提出了莫比烏斯立方網絡（M?bius cube，MQn)[1]。MQn(n=3)的拓撲結構如圖5所示。莫比烏斯立方網絡與超立方網絡一樣，具有相同的結點數、邊數和結點的度。莫比烏斯立方網絡的網絡直徑也幾乎只有超立方網絡的一半，結點間的平均步數只有超立方網絡的2/3，表現出優(yōu)于超立方網絡的動態(tài)性能[1]。此外，莫比烏斯立方網絡還具有超立方網絡不具有的漢密爾頓性質和嵌入性[25]。但是，莫比烏斯立方網絡不具有超立方網絡的超高對稱性。各種算法都是基于特定結點或邊，復雜度也相對較高。

Fig.5 Topology ofMQ3圖5 MQ3拓撲結構圖

2.7 平衡立方網絡

超立方網絡及其前期的大多數變種都普遍關注于縮小網絡直徑和信息交換兩方面[26]。而隨著處理器規(guī)模的不斷擴大，系統發(fā)生故障的可能性也成倍乃至成幾何倍數增加，因此互連網絡的設計需要充分考慮拓撲結構的容錯能力?；诖耍?992年，Wu和Huang提出了平衡立方網絡（balanced hypercube，BHn）[27]，BHn(n=3)的拓撲結構如圖6所示。平衡立方網絡在繼承超立方網絡的強連通性、規(guī)則性和對稱性的同時，還具有特殊的負載均衡能力，使得它具備即時容錯能力。具體表示為當故障處理器發(fā)生故障后，其任務可以及時地在備份處理器中即時恢復。因此，平衡立方網絡在不改變任務間鄰接關系的基礎上，支持有效的重構。此外，平衡立方網絡相比超立方網絡也有更低的網絡直徑。但是其結點數、邊數都遠大于超立方網絡，構建成本較高，性價比較低[27]。

Fig.6 Topology ofBH3圖6 BH3拓撲結構圖

2.8 增廣立方網絡

扭立方網絡、折疊超立方網絡和交叉立方網絡都以犧牲超立方網絡的超高對稱性為代價來減低網絡直徑，其實用性頗有爭議[28]。為了保持較高對稱性，2002年，Choudum和Sunitha提出了增廣立方網絡（augmented cubes，AQn)[28]，AQn(n=3)的拓撲結構如圖7所示。增廣立方網絡是超立方網絡的一個加強網絡，它不僅保持了超立方網絡的良好拓撲性質，并且在網絡直徑、嵌入性等方面擁有更好的屬性。但是在硬件成本和連通度上卻付出了較大的代價，其邊數和連通度都幾乎是超立方網絡的2倍。

Fig.7 Topology ofAQ3圖7 AQ3拓撲結構圖

2.9 交換超立方網絡

隨著維數的增加，超立方網絡及其多數變種，如扭立方網絡、交叉立方網絡、莫比烏斯立方網絡等，其連接邊的增加遠比結點的增加要快，而且這種差異會越拉越大。更為嚴重的是，連接邊數以及復雜度直接與硬件成本和集成電路的實現效果相關聯[29]。而單純的縮小連接復雜度會嚴重損害到系統的性能、應用支持、連通度、路由和可靠性等多個方面[29]。因此簡單地縮小連接復雜度難以有效地提高性價比，而在拓撲結構上新的創(chuàng)新才是研究的方向?；诖?，2005年，Loh等人通過移除超立方網絡的一些連接邊，提出了交換超立方網絡（exchanged hypercube，EH(s,t)）[29]，EH(s,t)(s=1,t=2)的拓撲結構如圖8所示。交換超立方網絡在連接邊幾乎只有超立方網絡一半的情況下保持了與超立方網絡相似的網絡直徑，同時還繼承了超立方網絡的偶泛圈性和強連通度等特點。交換超立方網絡包含有兩個參數，這也使得互連更加靈活。

Fig.8 Topology ofEH(1,2)圖8 EH(1,2)拓撲結構圖

2.10 超立方網絡二次變種拓撲結構

近年來，互連網絡拓撲結構研究進入了新的階段，出現了一些超立方網絡的二次變種，包括：2002年Zhang提出的折疊交叉超立方網絡（folded-crossed hypercube，FCHn）[30]，2005年Yang等人提出的局部扭立方網絡（locally twisted cubes，LTQn）[31]，2013年Li等人提出的交換交叉立方網絡（exchanged crossed cube，ECQ(s,t)）[32]以及Peng等人提出的折疊局部扭立方網絡（folded locally twisted cubes，FLTQn）[33]。

3 互連網絡的故障診斷與診斷度研究

互連網絡定義了并行計算機中各處理器之間的互連關系，而互連關系又影響到并行計算機的協同性能和構建成本。幾種主要互連網絡拓撲結構的拓撲參數如表1所示。迄今為止，超立方網絡及其變種的實際應用還很少，影響超立方網絡及其變種應用和推廣的主要原因之一是其可靠性研究尚不系統，其中又以故障診斷度研究最為突出?；ミB網絡的故障診斷是支撐互連網絡運行可靠性的主要指標之一，需要展開系統研究。

多處理器并行計算機系統的故障診斷分為邏輯電路級別和系統級[44]。由于包含了大量的互連單元，所以多處理器并行計算機的故障診斷解決方案應該傾向于系統級別，而不是邏輯電路級別。系統級故障診斷充分利用了多處理器并行計算機中每一個處理器的測試能力，讓處理器之間進行相互測試，通過診斷算法對測試結果進行綜合分析來識別出故障結點的所在。因此，系統級故障診斷理論實現了多處理器并行計算機故障診斷的自我診斷以及用戶透明重構與恢復[45]，是多處理器并行計算機故障診斷的主要研究方向之一。

Table 1 Topological parameters of several main interconnection networks表1 幾種主要互連網絡拓撲結構的拓撲參數

經歷了半個世紀的研究與發(fā)展，迄今為止，系統級故障診斷已經提出了一系列故障診斷理論，具體包括：t-可診斷[3]、t/s-可診斷[46]、t1/t1-可診斷[47]、t/k-可診斷[48]、條件t-可診斷[49]、g正確鄰結點條件t-可診斷[50]和條件(t,k)-可診斷[51]。根據診斷特征的不同可歸納為3種類型，分別為：精確故障診斷、非精確故障診斷和條件故障診斷，如表2所示。同時，t-可診斷和t/k-可診斷又可進一步分為一步故障診斷和順序故障診斷兩種具體形式。因此，故障診斷理論也可以根據診斷迭代次數的不同歸屬為一步故障診斷和順序故障診斷兩種范疇。

傳統的t-可診斷對故障結點沒有任何限制，診斷精確而全面，因此被稱為精確故障診斷。非精確故障診斷全面而不精確（允許小部分正常結點被誤診斷）。條件故障診斷限制一些低概率情況的發(fā)生。間歇性故障診斷面對的是間歇性故障。其中順序t-可診斷[3]、(t,k)-可診斷[52]、順序t/k-可診斷[53]和條件(t,k)-可診斷屬于順序故障診斷范疇。每一種故障診斷理論都具有各自不同的適用性和使用范圍，發(fā)展的過程體現出診斷能力和診斷效果的不斷進步，同時也會伴隨著一定的負面效果和診斷代價。

系統級故障診斷的執(zhí)行還依賴特定的診斷模型（diagnosis model）。當前主要的診斷模型有Preparata Metze Chien（PMC）模型[3]和Maeng Malek（MM）模型（包括MM*模型）[54]。PMC模型中，每一個處理器都可以測試它的鄰接處理器，并且對它們的狀態(tài)進行評價。但是研究發(fā)現，要直接評價處理器的故障與否有時候非常復雜，且容易出現一定程度的誤判斷，而通過比較的方式來界定測試結果相比直接評價要簡單很多[48]。基于這種考慮，MM模型通過一個比較器把測試任務發(fā)給與它相鄰的兩個處理器，然后比較它們的測試結果來進行診斷。MM模型也被稱為比較故障診斷模型[54]。1992年，Sengupta等人進一步提出一種特殊的MM模型——MM*模型[55]。MM*模型要求每一個處理器都必須對它的任意兩個鄰接處理器進行測試。PMC模型和MM模型是使用廣泛的兩種診斷模型，二者各具特色。

接下來，就超立方網絡及其變種為代表的互連網絡故障診斷研究現狀進行詳細說明。

3.1 互連網絡的精確故障診斷與診斷度研究

1967年，Preparata等人將圖論方法應用于多處理器計算機系統的故障診斷，創(chuàng)造性地提出了t-可診斷理論[3]。t-可診斷指的是當故障結點數目不超過t時，所有故障都可以被診斷出來。t-可診斷又可以進一步分為一步t-可診斷和順序t-可診斷兩種類型。其中順序t-可診斷將在后續(xù)順序故障診斷中詳細說明。一步t-可診斷指的是當系統的故障結點數不超過t時，可以一步找出所有的故障結點。一步t-可診斷的診斷能力（診斷度）與點連通度關系密切[56]。但是，如表3所示，一步t-可診斷的診斷能力很小，甚至可以忽略，而難以發(fā)揮出實際的診斷作用。以n維超立方網絡為例，它的診斷度為n[57-58]，與總結點數的占比僅為n/2n，當n≥10時n/2n<1%。

Table 2 Classification of fault diagnosis theory表2 故障診斷理論分類

Table 3 Precise diagnosabilities of several main interconnection networks表3 主要互連網絡的精確故障診斷度

3.2 互連網絡的非精確故障診斷與非精確診斷度研究

為了提高系統的診斷能力，1975年Friedman以犧牲診斷的部分精確性為代價提出了一種新的故障診斷理論——t/s-可診斷[46]，t/s-可診斷在確保故障被全部診斷的同時允許出現小部分的誤診斷（正常處理器被誤診斷為故障處理器），是一種非精確的故障診斷理論。t/s-可診斷表示當故障結點數目不超過t時，所有的故障結點可以被圈定在一個大小不超過s的結點集合中。t/s-可診斷有誤診斷略高的缺點，最壞情況下誤診斷數可達s-1。t/s-可診斷的性質也很難獲取，即使s=n-1研究難度依然巨大[59]。因此，嚴重制約了t/s-可診斷的研究和發(fā)展。而當t=s時，研究難度略微舒緩，此時的t/s-可診斷表現出諸多的性能優(yōu)勢，這就是t/s-可診斷的典型特例——t1/t1-可診斷[47]。

t1/t1-可診斷是1978年Kavianpour等人提出的一種故障診斷理論[47]。t1/t1-可診斷要求在故障結點數目不超過t1的情況下，所有的故障結點可以被圈定在一個大小不超過t1的結點集合中。t1/t1-可診斷也被稱為悲觀故障診斷。之后，Kavianpour等人進一步證明同等診斷能力的t1/t1-可診斷系統，相比t-可診斷系統而言，可節(jié)省一半的測試邊[47]。1981年Chwa等人給出了t1/t1-可診斷的充要條件，并且指出t1/t1-可診斷至多只有一個被誤診斷的結點[59]。t1/t1-可診斷是t/s-可診斷的一種特例，相比t/s-可診斷，t1/t1-可診斷可以有效降低誤診斷率。

由于t/s-可診斷中允許存在著較大比例的誤診斷結點，并且這種故障診斷理論難以控制被誤診斷的結點數，特別是當故障集合只是一個結點時，它的誤診斷比例顯然不可接受?；诖?，1996年Somani等人提出了t/k-可診斷[48]。t/k-可診斷認為當系統的故障集合F滿足|F|≤t時，根據癥候可將系統的所有故障結點圈定到結點集合F1中，F1至多有k個被誤診斷的結點，即|F1|≤|F|+k。t/k-可診斷也可分為一步t/k-可診斷和順序t/k-可診斷兩種類型，其中順序t/k-可診斷也將在后續(xù)順序故障診斷中說明。t/k-可診斷是非精確故障診斷中一種可以控制誤診斷數目并且有效提高診斷能力的故障診斷理論。

如表4所示，互連網絡的非精確故障診斷度大幅度提高了系統的診斷能力，但是由于研究難度較大，其中絕大多數診斷度未被求得。

3.3 互連網絡的條件故障診斷與條件診斷度研究

條件t-可診斷是2005年Lai等人提出的一種限定條件的故障診斷理論[49]。條件t-可診斷要求系統中的每一個結點至少有1個正確（未發(fā)生故障）的鄰結點。但是對于一個維數較大的互連網絡而言，只是要求每一個結點至少有1個正確鄰結點的設定條件相對保守?；诖?，2012年Peng等人提出另一種限定條件的故障診斷理論——g正確鄰結點條件t-可診斷[50]。g正確鄰結點條件t-可診斷要求每一個正確的結點至少有g個正確的鄰結點。通常情況下，g正確鄰結點條件t-可診斷的診斷度是條件t-可診斷的數倍[76]，但是g如何合理取值業(yè)內沒有定論，也缺乏依據。

條件故障診斷是以犧牲故障發(fā)生的小概率事件為代價，成倍提高系統診斷能力的一種故障診斷理論。但是，這種犧牲勢必造成故障診斷的局限性。同時，診斷能力的提升也較為有限。以n維超立方網絡為例，它在PMC模型下的條件診斷度為4n-7[36,49,77]，與總結點數的占比為(4n-7)/2n，當n≥10時(4n-7)/2n<3.3%，仍然很小。迄今為止，如表5所示，互連網絡的條件故障診斷度基本都已求出，而g正確鄰結點條件診斷度卻仍有大部分未被求出。

Table 4 Inaccurate diagnosabilities of several main interconnection networks表4 主要互連網絡的非精確故障診斷度

3.4 互連網絡的順序故障診斷與順序診斷度研究

順序故障診斷是一種采取多步迭代進行難度分散的故障診斷理論。其中順序t-可診斷是通過反復迭代的方式來診斷系統的故障集合，每一次迭代至少要有一個新的故障結點被確認，這個被確認的故障結點子集會在下一次迭代開始之前被維修和替換，迭代會一直持續(xù)下去，直到所有的故障結點被確認并被維修替換為止[3]。和順序t-可診斷類似，順序t/k-可診斷要求在故障結點數不超過t的情況下，允許迭代過程中出現誤診斷，要求總的誤診斷數不能超過k個[53]。根據順序t-可診斷的定義可知，最壞情況下，順序t-可診斷的每一次迭代都只能確定一個故障結點的所在，因此整體的迭代過程可能需要一定的時間，這就可能降低診斷的實時性。基于此，2003年，Araki等人提出了新一代的順序t-可診斷理論——(t,k)-可診斷[52]。(t,k)-可診斷要求在故障結點數不超過t時，每次迭代至少可以確定k個故障結點，其中k≤t。(t,k)-可診斷最壞情況下的最大迭代次數僅為ét/kù，比順序t-可診斷的最大迭代次數t要小很多。因此，(t,k)-可診斷改善了順序t-可診斷的過度延時，是順序故障診斷的發(fā)展方向。

事實上很多故障診斷理論都存在故障隨機分布和故障條件分布兩種情景[51]，(t,k)-可診斷也不例外。在故障隨機分布的情況下k=t時的(t,k)-可診斷就是傳統的一步t-可診斷，k=1時的(t,k)-可診斷就是順序t-可診斷。而當故障結點不是隨機分布，而是和條件t-可診斷一樣，要求所有的結點都遵循至少有一個正確的鄰結點。這種情況下的(t,k)-可診斷稱為條件(t,k)-可診斷[51]。條件(t,k)-可診斷充分融合了條件t-可診斷和(t,k)-可診斷的優(yōu)點，在有效利用測試資源的基礎上提高了系統的診斷能力。

（2）拓寬目的層頻帶，即特殊處理過程。將目的層地震資料做小波變換，在小波域進行信號重構，保障提高地震分辨率的同時，還保留了地震資料很好的保真度。

Table 5 Conditional diagnosabilities of several main interconnection networks表5 主要互連網絡的條件診斷度

如表6和表7所示，迄今為止，互連網絡的順序故障診斷度多數未被求出。

基于上述分析，互連網絡的精確故障診斷精確，但是診斷能力差?；ミB網絡的條件故障診斷能力有所提高，但是提高程度有限，且條件故障診斷忽略的小概率事件現實情況下時有發(fā)生。因此，在互連網絡上執(zhí)行非精確故障診斷和順序故障診斷是進一步提高系統診斷能力，保障運行可靠性的有效手段。然而，如表4、表6和表7所示，相關研究鮮見報道，研究成果也較為零星。

4 互連網絡的故障診斷研究展望

根據互連網絡故障診斷的研究現狀，接下來對未來的研究方向進行展望，具體包括互連網絡的拓撲結構研究、互連網絡的非精確故障診斷研究和互連網絡的順序故障診斷研究三方面。

Table 6 Sequential diagnosabilities of several main interconnection networks(1)表6 主要互連網絡的順序故障診斷度（1）

Table 7 Sequential diagnosabilities of several main interconnection networks(2)表7 主要互連網絡的順序故障診斷度（2）

4.1 互連網絡的拓撲結構研究

由互連網絡拓撲結構的研究現狀可知，要設計一個各個方面表現都最優(yōu)的互連網絡幾乎不可能。因此，實際應用中就需要根據具體的需求進行必要的妥協，特別是在性能和成本之間進行合理的權衡，選擇出一個符合當前實際需要的互連網絡拓撲結構。由于需求的多面性，客觀上經常要求使用的互連網絡需同時具有幾種現有互連網絡拓撲結構的優(yōu)點。因此，互連網絡的二次變種甚至多次變種將成為后續(xù)互連網絡拓撲結構研究的主要方向之一。通過二次或者多次變種，可以使得新生成的互連網絡拓撲結構同時繼承兩種或者多種互連網絡拓撲結構的優(yōu)點，進而最大程度地發(fā)揮出綜合的性能優(yōu)勢，以提供更為適用的互連網絡拓撲結構。

4.2 互連網絡的非精確故障診斷研究

如表4所示，互連網絡的非精確故障診斷度大幅度提高了系統的診斷能力。但是由于研究難度較大，其中絕大多數診斷度未被求得，主要原因在于缺乏非精確故障診斷的關鍵性特征。然而，Ye等人在研究超立方網絡、交叉立方網絡、莫比烏斯立方網絡等互連網絡時發(fā)現，這些互連網絡在滿足非精確故障診斷時，存在著一個結點規(guī)模超過總結點數一半的巨大連通分支[101-102]，這個連通分支富含眾多性質特征，比如：連通分支內的結點狀態(tài)值相同，連通分支和允許故障集合（allowable fault set）[3]以外的結點數不超過2個。如果以這個連通分支為抓手，借助“集團”的概念和性質定理[103]，可以進一步確定與這個連通分支所在的集團相鄰的集團都是故障集團，所包含的結點都是故障結點[104]。進而，在充分研究集團性質和各類連通度的基礎上，極有可能提煉出非精確故障診斷的關鍵性特征，進而展開互連網絡的非精確故障診斷度研究。因此，互連網絡的非精確故障診斷研究存在著重新展開的有利條件。利用可區(qū)分性的充要條件和允許故障集合的性質特征構建起非精確故障診斷的關鍵性特征。最后，結合具體的互連網絡拓撲結構，以相關拓撲性質和非精確故障診斷的關鍵性特征為基礎，求出互連網絡非精確故障診斷度的取值上限和下限，并通過仿真實驗驗證相關結論。因此，互連網絡的非精確故障診斷研究是一個值得廣泛關注的研究方向。

4.3 互連網絡的順序故障診斷研究

如表6和表7所示，互連網絡的順序故障診斷度可以有效地提高系統的診斷能力。但是，需要犧牲一定的時間復雜度，這對于診斷的及時性有一定影響，但是在當前的處理能力下這點影響并不明顯。同樣，互連網絡順序故障診斷度的研究也存在著較大難度。然而，在(t,k)-可診斷時發(fā)現，其診斷度與P(t)[92]、Q(t)[92]、Dˉ(σ)[92]、φ(x1)[97]、?(x1,x2)[97]和I(m)[97]等特定函數密切相關，而這些特定函數又與互連網絡的相關拓撲性質密切關聯。因此，在得到互連網絡相關拓撲性質的基礎上，結合順序故障診斷的關鍵性特征，再借助系列特定函數，極有可能求出互連網絡的順序故障診斷度。

同時，到目前為止，只有t-可診斷和t/k-可診斷進一步分成了一步故障診斷和順序故障診斷兩種類型。但是就定義而言，順序故障診斷的多步迭代也同樣適用于t/s-可診斷、t1/t1-可診斷、條件t-可診斷和g正確鄰結點條件t-可診斷。因此，順序故障診斷理論存在著進一步拓展的可能。

因此，互連網絡順序故障診斷研究也是一個頗具潛力的研究方向。

5 總結

本文以提高多處理器并行計算機的運行可靠性為目標，系統梳理了互連網絡的拓撲性質、互連網絡的精確故障診斷度、互連網絡的非精確故障診斷度、互連網絡的條件故障診斷度和互連網絡的順序故障診斷度等研究成果。進而在比較分析的基礎上，提出互連網絡故障診斷研究的3個重要發(fā)展方向。本文的研究有助于促進互連網絡在多處理器并行計算機系統的應用和推廣。