星型網(wǎng)絡(luò)的故障診斷度與額外連通度研究.pdf

1、在研究超級計(jì)算機(jī)方面所取得的成就，已經(jīng)成為了體現(xiàn)一個國家科技實(shí)力的重要指標(biāo)。為了使超級計(jì)算機(jī)得到更高的處理能力，采用成千上萬的處理單元來構(gòu)建超級計(jì)算機(jī)，越來越多的處理單元使得超級計(jì)算機(jī)系統(tǒng)變得越來越復(fù)雜，規(guī)模也在不斷擴(kuò)大。面對日益復(fù)雜的超級計(jì)算機(jī)系統(tǒng)，如何有效地識別和定位故障結(jié)點(diǎn)和故障鏈路，成為了保障系統(tǒng)可靠性的重要工作。故障診斷度是網(wǎng)絡(luò)故障診斷理論研究中一個非常重要的問題;而額外連通度則是衡量網(wǎng)絡(luò)可靠性的一個重要參數(shù)。星型網(wǎng)絡(luò)是一個非

2、常有吸引力的規(guī)則互連網(wǎng)絡(luò)。
　　本文主要研究星型互連網(wǎng)絡(luò)在PMC故障模式下的三種診斷度和2-額外連通度。對于一個n維星型網(wǎng)絡(luò)Sn（n≥3），證明該網(wǎng)絡(luò)的一步故障診斷度、t1/t1-診斷度和局部故障診斷度分別為n-1，2n-4和n-1。這些診斷度的提出，對星型互連網(wǎng)絡(luò)的可靠性和容錯性的研究具有重要的意義。對于星型互連網(wǎng)絡(luò)Sn，本文證明了當(dāng)n≥6時，κ2(Sn)=λ2(Sn)=3n-7，即星型網(wǎng)絡(luò)的2-額外點(diǎn)連通度和2-額外邊連通度均