幾類互連網(wǎng)絡(luò)性能的組合分析.pdf

1、網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是設(shè)計(jì)和制造機(jī)群計(jì)算機(jī)或超大規(guī)模并行計(jì)算機(jī)系統(tǒng)的第一步，也是實(shí)現(xiàn)各種協(xié)議的基礎(chǔ)，它對網(wǎng)絡(luò)的性能、系統(tǒng)可靠性和費(fèi)用都有重大影響。人們通常把互連網(wǎng)絡(luò)中的處理器抽象成一個點(diǎn)，把處理器之間的信道抽象成兩點(diǎn)之間的連線，那么該網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)就被抽象成一個圖。研究網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)問題就歸結(jié)為研究圖的結(jié)構(gòu)問題。網(wǎng)絡(luò)的容錯性研究可以轉(zhuǎn)化成對圖的參數(shù)研究?；ミB網(wǎng)絡(luò)主要有以下的評價(jià)指標(biāo)： (1)硬件復(fù)雜度，可以用拓?fù)鋱D的頂點(diǎn)度來衡量。

2、 (2)通信開銷：可以用網(wǎng)絡(luò)拓?fù)鋱D的直徑來、平均距離來衡量。 (3)可擴(kuò)展性。就是一個小網(wǎng)絡(luò)要擴(kuò)充為一個大網(wǎng)絡(luò)，并保留小網(wǎng)絡(luò)的結(jié)構(gòu)性質(zhì)的可能性，它可以歸結(jié)為圖的可嵌入性問題。 (4)容錯能力?？梢杂脠D的連通度以及邊連通度、網(wǎng)絡(luò)的容錯直徑和寬直徑衡量。 目前討論比較多的網(wǎng)絡(luò)主要有網(wǎng)狀網(wǎng)、樹狀網(wǎng)、超方體狀網(wǎng)和星狀網(wǎng)類型網(wǎng)絡(luò)。本文主要考慮這些網(wǎng)絡(luò)的容錯性質(zhì)，我們的工作如下： 首先，我們對這些主要的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

3、的容錯性指標(biāo)，例如通信延遲、容錯直徑與寬直徑、連通性質(zhì)進(jìn)行了系統(tǒng)的總結(jié)。在此基礎(chǔ)上，提出了互連網(wǎng)絡(luò)拓?fù)淙蒎e性方面一些值得進(jìn)一步研究的問題。 然后，本文對超立方體的一種變形——變種超立方體進(jìn)行進(jìn)一步研究。對變種超立方體的研究已有很多，包括連通度、遞歸性，可嵌入環(huán)和格、直徑、路由算法和廣播算法。本文研究變種超立方體的容錯直徑和寬直徑，證明了容錯直徑和寬直徑等于它的直徑加1或2。 最后，利用提升圖的技巧，我們提供一種構(gòu)造更大規(guī)