互連網(wǎng)絡(luò)的最小邊界和可診斷性研究.pdf

1、多處理器系統(tǒng)是超級計算機(jī)的主要實(shí)現(xiàn)形式。由于現(xiàn)在的超級計算機(jī)中處理器的數(shù)目越來越多，系統(tǒng)運(yùn)行時某些處理器出故障的可能性越來越大。因此多處理器系統(tǒng)的可靠性分析和故障診斷研究是高性能計算的一個重要研究領(lǐng)域。
　　互連網(wǎng)絡(luò)是多處理器系統(tǒng)的圖論模型?；ミB網(wǎng)絡(luò)的可靠性的傳統(tǒng)度量參數(shù)是連通度和邊連通度。但是這兩種參數(shù)卻存在著明顯的缺陷。因為對一些連通網(wǎng)絡(luò)來說，一個頂點(diǎn)的所有鄰點(diǎn)同時出故障的概率是極小的。為了更好的度量互連網(wǎng)絡(luò)的可靠性，人們陸續(xù)

2、提出了限制連通度、超連通度和額外連通度等新的度量參數(shù)。這些參數(shù)可以更加精確的度量某些互連網(wǎng)絡(luò)的可靠性。超立方體網(wǎng)絡(luò)是當(dāng)今最著名也是最通用的網(wǎng)絡(luò)之一，具有良好的性質(zhì)。M(o)bius立方體作為超立方體網(wǎng)絡(luò)的變形，保留了超立方體網(wǎng)絡(luò)的高連通性和遞歸性等優(yōu)良性質(zhì)。因此本文的主要工作是研究這兩個網(wǎng)絡(luò)的可靠性和可診斷性。
　　我們首先通過與等周問題相結(jié)合，研究了故障超立方體的結(jié)構(gòu)，然后給出了當(dāng)1≤h≤3n-6時，超立方體網(wǎng)絡(luò)的(h-1)額外