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

1、多處理器系統(tǒng)是超級(jí)計(jì)算機(jī)的主要實(shí)現(xiàn)形式。由于現(xiàn)在的超級(jí)計(jì)算機(jī)中處理器的數(shù)目越來(lái)越多，系統(tǒng)運(yùn)行時(shí)某些處理器出故障的可能性越來(lái)越大。因此多處理器系統(tǒng)的可靠性分析和故障診斷研究是高性能計(jì)算的一個(gè)重要研究領(lǐng)域。
　　互連網(wǎng)絡(luò)是多處理器系統(tǒng)的圖論模型?；ミB網(wǎng)絡(luò)的可靠性的傳統(tǒng)度量參數(shù)是連通度和邊連通度。但是這兩種參數(shù)卻存在著明顯的缺陷。因?yàn)閷?duì)一些連通網(wǎng)絡(luò)來(lái)說(shuō)，一個(gè)頂點(diǎn)的所有鄰點(diǎn)同時(shí)出故障的概率是極小的。為了更好的度量互連網(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ì)。因此本文的主要工作是研究這兩個(gè)網(wǎng)絡(luò)的可靠性和可診斷性。
　　我們首先通過(guò)與等周問(wèn)題相結(jié)合，研究了故障超立方體的結(jié)構(gòu)，然后給出了當(dāng)1≤h≤3n-6時(shí)，超立方體網(wǎng)絡(luò)的(h-1)額外