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

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

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

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