【摘要】： 隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)與計(jì)算科學(xué)的發(fā)展,并行計(jì)算機(jī)及其互連網(wǎng)絡(luò)作為一個(gè)跨數(shù)學(xué)、計(jì)算科學(xué)與信息科學(xué)等多門學(xué)科的領(lǐng)域,逐漸成為計(jì)算機(jī)科學(xué)研究的熱點(diǎn)之一,各種拓?fù)浣Y(jié)構(gòu)的互連網(wǎng)絡(luò),如環(huán)、Mesh、超立方體、星型網(wǎng)絡(luò)等得到迅速發(fā)展。在一個(gè)多處理器互連網(wǎng)絡(luò)中,處理器之間的有效通信是衡量系統(tǒng)性能的一個(gè)重要標(biāo)準(zhǔn)。當(dāng)處理器數(shù)目逐漸增多時(shí),其發(fā)生故障的可能性也隨之增加,不同處理器之間信息傳遞過(guò)程中的容錯(cuò)性便成為一個(gè)非常關(guān)鍵的問(wèn)題。因此,如何找出一種新的網(wǎng)絡(luò)容錯(cuò)模型以便容納更多的錯(cuò)誤節(jié)點(diǎn),以及如何設(shè)計(jì)高效的容錯(cuò)路由算法以便保證無(wú)故障處理器間正確可靠的信息傳遞是至關(guān)重要的。 超立方體網(wǎng)絡(luò)是多處理機(jī)系統(tǒng)中常見(jiàn)的一種互連網(wǎng)絡(luò),這種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)由于具有直徑小、可擴(kuò)展性強(qiáng)、結(jié)構(gòu)對(duì)稱、網(wǎng)絡(luò)尋路算法簡(jiǎn)單等優(yōu)點(diǎn),且多種拓?fù)浣Y(jié)構(gòu)的互連網(wǎng)絡(luò)都可以很容易的嵌入其中,因而成為最重要和最具吸引力的網(wǎng)絡(luò)模型之一。本文即是從上述兩個(gè)方面,對(duì)超立方體網(wǎng)絡(luò)的容錯(cuò)性和路由算法進(jìn)行研究,主要研究?jī)?nèi)容如下: 1.提出一種新的并行計(jì)算機(jī)網(wǎng)絡(luò)容錯(cuò)模型-LIP導(dǎo)出嵌入模型,包括與LIP相關(guān)的概念、性質(zhì)、優(yōu)點(diǎn),給出了超立方體網(wǎng)絡(luò)中求LIP的算法;針對(duì)此算法,文中給出了其C++實(shí)現(xiàn)程序,并求出了當(dāng)維數(shù)n=6,7時(shí)LIP長(zhǎng)度的精確值。 2.為了更好的分析超立方體網(wǎng)絡(luò)的容錯(cuò)性,提出更為優(yōu)越的容錯(cuò)路由算法,文章給出了超立方體網(wǎng)絡(luò)中LIP容錯(cuò)模型的上下界估計(jì),并給出一個(gè)非常有意義的猜想,而且結(jié)合程序結(jié)果對(duì)上下界及猜想進(jìn)行了驗(yàn)證。結(jié)果表明,LIP不僅具有較好的容錯(cuò)性,而且還能保證超立方體網(wǎng)絡(luò)的全局連通性,具有較好的實(shí)際意義。 3.基于文中提出的LIP容錯(cuò)模型,結(jié)合路由選擇能力的概念,提出一種超立方體網(wǎng)絡(luò)單播容錯(cuò)路由算法,該算法在“超立方體網(wǎng)絡(luò)中至少存在一條無(wú)故障節(jié)點(diǎn)的LIP”的條件下,所能容納的壞節(jié)點(diǎn)數(shù)多于2n-1,達(dá)到指數(shù)數(shù)量級(jí);此外,該算法的最少步數(shù)為H(s, d),極壞情況為ρ(Q n) +1,且算法達(dá)到極壞情況的可能性是非常小的,因此,算法在一定程度上是比較優(yōu)越的。 本文在超立方體網(wǎng)絡(luò)容錯(cuò)模型及路由算法方面作了一些探索工作,取得了一定的結(jié)果,但還有大量工作需要研究。特別是要進(jìn)一步研究超立方體網(wǎng)絡(luò)中的LIP容錯(cuò)模型,
【圖文】：

(...)0 1 1=nX xxx和 (...)0 1 1=nY yyy之間有邊當(dāng)且僅當(dāng) X 和Y 僅有一位分量不同即iix ≠ y，而jjx = y，{}j ∈ ( n) i，其中 0 ≤ i ≤n 1，{ }( n )= 0,1,...,n 1，并稱該邊為i邊。圖 3.3 便是 3 維超立方體的示例，圖中有32 ＝8 個(gè)節(jié)點(diǎn)和3132 ＝12 條邊還標(biāo)識(shí)出了節(jié)點(diǎn)的編號(hào)（從 000 到 111）。3.2 超立方體網(wǎng)絡(luò) LIP 導(dǎo)出嵌入模型上面我們給出了 LIP 導(dǎo)出嵌入的定義，接下來(lái)我們根據(jù)具體圖例來(lái)看一下在圖 3.3 所示的 3 維超立方體中，按照?qǐng)D 3.2 規(guī)定的維數(shù)順序（維數(shù)順序可任指定，它只影響節(jié)點(diǎn)的編號(hào)，并不影響問(wèn)題的實(shí)質(zhì)），000-> 001-> 011-> 111 000-> 100-> 110 均為導(dǎo)出路，而 000-> 001-> 011-> 111->110 和 000-> 100110-> 111-> 011 均為最長(zhǎng)導(dǎo)出路(LIP)。
【學(xué)位授予單位】：山東師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2006
【分類號(hào)】：TP338.6;TP393.02

【引證文獻(xiàn)】

相關(guān)碩士學(xué)位論文 前2條

1 韓超;計(jì)量管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D];北京郵電大學(xué);2011年

2 楊彥鑫;基于以太網(wǎng)的多DSP并行系統(tǒng)任務(wù)下載技術(shù)研究[D];云南大學(xué);2012年

，

本文編號(hào)：2610407