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

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

1 引言

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

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

使用系統(tǒng)級(jí)故障診斷進(jìn)行故障診斷的前提是要得到互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的各種診斷度性能指標(biāo)。當(dāng)前，規(guī)則互連網(wǎng)絡(luò)僅有超立方網(wǎng)絡(luò)在得到較為完整的診斷度研究之后被成功地應(yīng)用到INTEL和NCUBE計(jì)算機(jī)[1]。而以超立方網(wǎng)絡(luò)變種為代表的其他互連網(wǎng)絡(luò)的故障診斷研究尚不系統(tǒng)，普遍缺乏完整的診斷度參數(shù)，這種情況勢(shì)必影響到互連網(wǎng)絡(luò)在多處理器并行計(jì)算機(jī)中的應(yīng)用和推廣?；诖?，本文以超立方網(wǎng)絡(luò)及其變種為代表的互連網(wǎng)絡(luò)為研究對(duì)象，通過拓?fù)浣Y(jié)構(gòu)研究對(duì)以超立方網(wǎng)絡(luò)及其變種為代表的互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的繼承關(guān)系、拓?fù)湫再|(zhì)、成本、連通度進(jìn)行了系統(tǒng)分析。在此基礎(chǔ)上，系統(tǒng)闡述了互連網(wǎng)絡(luò)的故障診斷度研究現(xiàn)狀，包括精確故障診斷度、非精確故障診斷度、條件故障診斷度、順序故障診斷。并闡明了在互連網(wǎng)絡(luò)上執(zhí)行非精確故障診斷和順序故障診斷是進(jìn)一步提高系統(tǒng)診斷能力，保障運(yùn)行可靠性的有效手段，以及相關(guān)研究鮮見報(bào)道的研究現(xiàn)狀。最后指出包括互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)研究、互連網(wǎng)絡(luò)的非精確故障診斷研究和互連網(wǎng)絡(luò)的順序故障診斷研究在內(nèi)的3個(gè)主要研究方向。本文的綜述為互連網(wǎng)絡(luò)的可靠性研究提供了較為完整的數(shù)據(jù)參數(shù)和關(guān)聯(lián)體系，從而促進(jìn)互連網(wǎng)絡(luò)在多處理器并行計(jì)算機(jī)的應(yīng)用和推廣。

2 互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)研究

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

2.1 線性陣列和樹形結(jié)構(gòu)

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

2.2 超立方網(wǎng)絡(luò)

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

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

2.3 扭立方網(wǎng)絡(luò)

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

Fig.1 Topology ofQ3圖1 Q3拓?fù)浣Y(jié)構(gòu)圖

Fig.2 Topology ofTQ3圖2 TQ3拓?fù)浣Y(jié)構(gòu)圖

2.4 折疊超立方網(wǎng)絡(luò)

為了減低網(wǎng)絡(luò)直徑，同時(shí)維系一定的對(duì)稱性，1991年，El-Amawy和Latifi提出了折疊超立方網(wǎng)絡(luò)（folded hypercube，F(xiàn)Hn）[19]。折疊超立方網(wǎng)絡(luò)是在超立方網(wǎng)絡(luò)的基礎(chǔ)上，通過增加一些額外邊來降低系統(tǒng)的網(wǎng)絡(luò)直徑。FHn(n=3)的拓?fù)浣Y(jié)構(gòu)如圖3所示。折疊超立方網(wǎng)絡(luò)結(jié)點(diǎn)數(shù)與超立方網(wǎng)絡(luò)一樣，其網(wǎng)絡(luò)直徑卻幾乎只有超立方網(wǎng)絡(luò)的一半，而邊數(shù)更是比超立方網(wǎng)絡(luò)多出2n-1條。折疊超立方網(wǎng)絡(luò)保持了超立方網(wǎng)絡(luò)的部分對(duì)稱性，但是額外增加的2n-1條邊將較大程度增加系統(tǒng)的構(gòu)造成本，嚴(yán)重影響到系統(tǒng)的性價(jià)比。

Fig.3 Topology ofFH3圖3 FH3拓?fù)浣Y(jié)構(gòu)圖

2.5 交叉立方網(wǎng)絡(luò)

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

Fig.4 Topology ofCQ3圖4 CQ3拓?fù)浣Y(jié)構(gòu)圖

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

2.6 莫比烏斯立方網(wǎng)絡(luò)

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

Fig.5 Topology ofMQ3圖5 MQ3拓?fù)浣Y(jié)構(gòu)圖

2.7 平衡立方網(wǎng)絡(luò)

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

Fig.6 Topology ofBH3圖6 BH3拓?fù)浣Y(jié)構(gòu)圖

2.8 增廣立方網(wǎng)絡(luò)

扭立方網(wǎng)絡(luò)、折疊超立方網(wǎng)絡(luò)和交叉立方網(wǎng)絡(luò)都以犧牲超立方網(wǎng)絡(luò)的超高對(duì)稱性為代價(jià)來減低網(wǎng)絡(luò)直徑，其實(shí)用性頗有爭議[28]。為了保持較高對(duì)稱性，2002年，Choudum和Sunitha提出了增廣立方網(wǎng)絡(luò)（augmented cubes，AQn)[28]，AQn(n=3)的拓?fù)浣Y(jié)構(gòu)如圖7所示。增廣立方網(wǎng)絡(luò)是超立方網(wǎng)絡(luò)的一個(gè)加強(qiáng)網(wǎng)絡(luò)，它不僅保持了超立方網(wǎng)絡(luò)的良好拓?fù)湫再|(zhì)，并且在網(wǎng)絡(luò)直徑、嵌入性等方面擁有更好的屬性。但是在硬件成本和連通度上卻付出了較大的代價(jià)，其邊數(shù)和連通度都幾乎是超立方網(wǎng)絡(luò)的2倍。

Fig.7 Topology ofAQ3圖7 AQ3拓?fù)浣Y(jié)構(gòu)圖

2.9 交換超立方網(wǎng)絡(luò)

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

Fig.8 Topology ofEH(1,2)圖8 EH(1,2)拓?fù)浣Y(jié)構(gòu)圖

2.10 超立方網(wǎng)絡(luò)二次變種拓?fù)浣Y(jié)構(gòu)

近年來，互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)研究進(jìn)入了新的階段，出現(xiàn)了一些超立方網(wǎng)絡(luò)的二次變種，包括：2002年Zhang提出的折疊交叉超立方網(wǎng)絡(luò)（folded-crossed hypercube，F(xiàn)CHn）[30]，2005年Yang等人提出的局部扭立方網(wǎng)絡(luò)（locally twisted cubes，LTQn）[31]，2013年Li等人提出的交換交叉立方網(wǎng)絡(luò)（exchanged crossed cube，ECQ(s,t)）[32]以及Peng等人提出的折疊局部扭立方網(wǎng)絡(luò)（folded locally twisted cubes，F(xiàn)LTQn）[33]。

3 互連網(wǎng)絡(luò)的故障診斷與診斷度研究

互連網(wǎng)絡(luò)定義了并行計(jì)算機(jī)中各處理器之間的互連關(guān)系，而互連關(guān)系又影響到并行計(jì)算機(jī)的協(xié)同性能和構(gòu)建成本。幾種主要互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的拓?fù)鋮?shù)如表1所示。迄今為止，超立方網(wǎng)絡(luò)及其變種的實(shí)際應(yīng)用還很少，影響超立方網(wǎng)絡(luò)及其變種應(yīng)用和推廣的主要原因之一是其可靠性研究尚不系統(tǒng)，其中又以故障診斷度研究最為突出?；ミB網(wǎng)絡(luò)的故障診斷是支撐互連網(wǎng)絡(luò)運(yùn)行可靠性的主要指標(biāo)之一，需要展開系統(tǒng)研究。

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

Table 1 Topological parameters of several main interconnection networks表1 幾種主要互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的拓?fù)鋮?shù)

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

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

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

接下來，就超立方網(wǎng)絡(luò)及其變種為代表的互連網(wǎng)絡(luò)故障診斷研究現(xiàn)狀進(jìn)行詳細(xì)說明。

3.1 互連網(wǎng)絡(luò)的精確故障診斷與診斷度研究

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

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

Table 3 Precise diagnosabilities of several main interconnection networks表3 主要互連網(wǎng)絡(luò)的精確故障診斷度

3.2 互連網(wǎng)絡(luò)的非精確故障診斷與非精確診斷度研究

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

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

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

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

3.3 互連網(wǎng)絡(luò)的條件故障診斷與條件診斷度研究

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

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

Table 4 Inaccurate diagnosabilities of several main interconnection networks表4 主要互連網(wǎng)絡(luò)的非精確故障診斷度

3.4 互連網(wǎng)絡(luò)的順序故障診斷與順序診斷度研究

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

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

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

Table 5 Conditional diagnosabilities of several main interconnection networks表5 主要互連網(wǎng)絡(luò)的條件診斷度

如表6和表7所示，迄今為止，互連網(wǎng)絡(luò)的順序故障診斷度多數(shù)未被求出。

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

4 互連網(wǎng)絡(luò)的故障診斷研究展望

根據(jù)互連網(wǎng)絡(luò)故障診斷的研究現(xiàn)狀，接下來對(duì)未來的研究方向進(jìn)行展望，具體包括互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)研究、互連網(wǎng)絡(luò)的非精確故障診斷研究和互連網(wǎng)絡(luò)的順序故障診斷研究三方面。

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

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

4.1 互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)研究

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

4.2 互連網(wǎng)絡(luò)的非精確故障診斷研究

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

4.3 互連網(wǎng)絡(luò)的順序故障診斷研究

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

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

因此，互連網(wǎng)絡(luò)順序故障診斷研究也是一個(gè)頗具潛力的研究方向。

5 總結(jié)

本文以提高多處理器并行計(jì)算機(jī)的運(yùn)行可靠性為目標(biāo)，系統(tǒng)梳理了互連網(wǎng)絡(luò)的拓?fù)湫再|(zhì)、互連網(wǎng)絡(luò)的精確故障診斷度、互連網(wǎng)絡(luò)的非精確故障診斷度、互連網(wǎng)絡(luò)的條件故障診斷度和互連網(wǎng)絡(luò)的順序故障診斷度等研究成果。進(jìn)而在比較分析的基礎(chǔ)上，提出互連網(wǎng)絡(luò)故障診斷研究的3個(gè)重要發(fā)展方向。本文的研究有助于促進(jìn)互連網(wǎng)絡(luò)在多處理器并行計(jì)算機(jī)系統(tǒng)的應(yīng)用和推廣。