互連網(wǎng)絡(luò)的容錯(cuò)性.pdf

1、隨著信息科學(xué)的迅猛發(fā)展,信息量和計(jì)算量日益增大,人們迫切需要速度更快、性能更高的計(jì)算機(jī)系統(tǒng),并行計(jì)算機(jī)系統(tǒng)應(yīng)運(yùn)而生.并行計(jì)算機(jī)系統(tǒng)的一個(gè)基本特征是元件之間通過(guò)物理連線按照某種互連網(wǎng)絡(luò)連接起來(lái),使得多個(gè)處理器通過(guò)信息傳輸,互相配合、并行處理,從而提高運(yùn)算能力.并行計(jì)算機(jī)系統(tǒng)功能的實(shí)現(xiàn)很大程度上依賴于系統(tǒng)互連網(wǎng)絡(luò)的性能.互連網(wǎng)絡(luò)的容錯(cuò)性是衡量互連網(wǎng)絡(luò)性能的關(guān)鍵指標(biāo),它主要考慮在網(wǎng)絡(luò)發(fā)生故障時(shí)網(wǎng)絡(luò)中某些特有性質(zhì)的保持能力.互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)可

2、以用圖作為其數(shù)學(xué)模型,圖中的點(diǎn)表示互連網(wǎng)絡(luò)中的各個(gè)元件,圖中的邊表示元件之間的物理連線.本文主要以圖論為工具研究了互連網(wǎng)絡(luò)對(duì)三種性質(zhì)的保持能力,即可匹配性、子網(wǎng)絡(luò)存在性和邊連通性.
　　本文共分為五章.第一章首先綜述了互連網(wǎng)絡(luò)的研究背景,然后介紹了本文所涉及到的一些基本概念和性質(zhì),最后概述了所研究問(wèn)題的相關(guān)背景、研究進(jìn)展以及獲得的主要結(jié)論.
　　k元n立方是并行計(jì)算機(jī)系統(tǒng)最常用的互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)之一,以k元n立方為基礎(chǔ)拓?fù)湟?/p>

3、經(jīng)構(gòu)建了許多并行計(jì)算機(jī)系統(tǒng).因此,研究k元n立方的容錯(cuò)性有著十分重要的現(xiàn)實(shí)意義.第二章首先考慮在發(fā)生故障時(shí)k元n立方對(duì)其可匹配性的保持能力,給出了使得k元n立方中不存在完美匹配或幾乎完美匹配所需要的最小故障數(shù),并且對(duì)k元n立方中對(duì)應(yīng)的所有的最小故障集合進(jìn)行了刻畫(huà).其次,考慮了在邊故障模型下忍元n立方對(duì)其子網(wǎng)絡(luò)的保持能力,對(duì)使得k元n立方中每個(gè)k元(n-m)立方都遭到破壞所需要的最小邊數(shù)厶.。進(jìn)行了研究.對(duì)于一些特殊的情形,給出了。fn,

4、m確切的值;對(duì)于一般的情形,給出了fn,m的一個(gè)較好的上界.
　　環(huán)面網(wǎng)絡(luò)是k元n立方網(wǎng)絡(luò)的一種擴(kuò)展拓?fù)浣Y(jié)構(gòu),得到了諸多網(wǎng)絡(luò)設(shè)計(jì)者的追捧.研究環(huán)面網(wǎng)絡(luò)的容錯(cuò)性可以為新一代并行計(jì)算機(jī)系統(tǒng)的互連網(wǎng)絡(luò)選擇提供有益的參考.第三章主要考慮在發(fā)生故障時(shí)環(huán)面網(wǎng)絡(luò)對(duì)其可匹配性的保持能力.首先確定了使得二部環(huán)面網(wǎng)絡(luò)中不存在完美匹配或幾乎完美匹配所需要的最小故障數(shù),并且對(duì)二部環(huán)面網(wǎng)絡(luò)中對(duì)應(yīng)的所有的最小故障集合進(jìn)行了刻畫(huà).其次確定了使得非二部的2維環(huán)面

5、網(wǎng)絡(luò)中不存在完美匹配或幾乎完美匹配所需要的最小故障數(shù),并且除了一類特殊的情形外對(duì)非二部的2維環(huán)面網(wǎng)絡(luò)中對(duì)應(yīng)的所有的最小故障集合進(jìn)行了刻四.
　　片上網(wǎng)絡(luò)作為多核技術(shù)的主要組成部分得到了越來(lái)越多的關(guān)注,星圖網(wǎng)絡(luò)基于自身優(yōu)良的特性已經(jīng)被用于片上系統(tǒng)的構(gòu)建.(n,k)一排列圖網(wǎng)絡(luò)是星圖網(wǎng)絡(luò)的一種擴(kuò)展拓?fù)浣Y(jié)構(gòu),研究(n,k)一排列圖的容錯(cuò)性可以為構(gòu)建性能優(yōu)良的新型片上系統(tǒng)提供有益的參考.第四章首先考慮(n,憊)一排列圖對(duì)其子網(wǎng)絡(luò)的保持能力

6、,分別對(duì)使得(n,k)一排列圖中每個(gè)(n-m,k-m)一排列圖都遭到破壞所需要的最小點(diǎn)數(shù)Fm(n,k)和最小邊數(shù)。fm(n,k)進(jìn)行了研究.對(duì)于一些特殊的情形,給出了這兩個(gè)參數(shù)確切的值;對(duì)于一般的情形,分別給出了Fm(n,k)和.fm(n,k)的較好的上界.其次,考慮了在發(fā)生故障時(shí)(n,k)一排列圖對(duì)其可匹配性的保持能力,給出了使得(n,k)一排列圖中不存在完美匹配或幾乎完美匹配所需要的最小故障數(shù).
　　人們希望構(gòu)建系統(tǒng)所選用的互

7、連網(wǎng)絡(luò)有較高的可靠性,即在一定數(shù)目的故障發(fā)生時(shí)網(wǎng)絡(luò)仍然能夠保持連通.邊連通度是衡量網(wǎng)絡(luò)可靠性的一個(gè)重要指標(biāo).k等周邊連通度是邊連通度的一種推廣,網(wǎng)絡(luò)G的k等周邊連通度被定義為γk(G)=min{|[X, X]|:XV(G),|X|≥k,|X|≥k}.一般地,βk(G)=min{l[x,x]|=xV(G),lxI=k}是γk(G)的一個(gè)上界.若γk(G)=βk(G),則稱G是極大k等周邊連通的.稱G中的邊割S=[x,x]為一個(gè)γk割,如果