M_bius立方體互連網(wǎng)絡(luò)條件連通度研究.pdf

1、并行處理系統(tǒng)是當(dāng)今計(jì)算機(jī)科學(xué)研究的主要方向之一。多處理機(jī)互連網(wǎng)絡(luò)（Interconnection Networks），簡稱互連網(wǎng)絡(luò)，是指由若干個處理機(jī)按一定方式相互連接而構(gòu)成的網(wǎng)絡(luò)，它是并行處理系統(tǒng)的核心。對互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及其性質(zhì)的研究是并行處理系統(tǒng)的一個重要課題。M(o)bius立方體具有很多優(yōu)越的性質(zhì)，已經(jīng)被用作多種并行機(jī)中處理機(jī)連接的拓?fù)浣Y(jié)構(gòu)并引起了國際上許多研究者的研究興趣。
　　互連網(wǎng)絡(luò)中的許多處理機(jī)在同時高速運(yùn)行著，

2、處理機(jī)之間經(jīng)常要進(jìn)行信息傳送。隨著多處理機(jī)系統(tǒng)中的處理機(jī)數(shù)目的增多和系統(tǒng)規(guī)模的增大，處理機(jī)發(fā)生故障是難以避免的。然而，實(shí)際上，一個互連網(wǎng)絡(luò)的容錯度相對于互連網(wǎng)絡(luò)的規(guī)模（頂點(diǎn)數(shù)）一般是很小的。為了提高系統(tǒng)的容錯度，研究者考慮了互連網(wǎng)絡(luò)處理機(jī)故障發(fā)生的或然率，即假定每個處理機(jī)的所有鄰接頂點(diǎn)同時發(fā)生故障的情形是不可能的，也就是說每個頂點(diǎn)至少有一個鄰接頂點(diǎn)是無故障的，在此條件下，本文將以M(o)bius立方體作為網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圍繞其條件連通度及其

3、相關(guān)問題進(jìn)行研究。
　　本文首先以0-M(o)bius立方體為例證明了M(o)bius立方體在其任一頂點(diǎn)至少有一個鄰接頂點(diǎn)是無故障的情況下，M(o)bius立方體的條件連通度為2n-2，即1-safe條件下M(o)bius立方體的條件連通度為2n-2，其容錯度為2n-3。
　　然后，本文給出M(o)bius立方體互連網(wǎng)絡(luò)上基于條件連通度的一個容錯路由選擇算法，分析該算法的時間復(fù)雜度為O(n)，并且證明在1-safe條件下的M