并行計算機網(wǎng)絡(luò)中的導出嵌入及其路由算法研究.pdf

1、隨著計算機網(wǎng)絡(luò)技術(shù)與計算科學的發(fā)展，并行計算機及其互連網(wǎng)絡(luò)作為一個跨數(shù)學、計算科學與信息科學等多門學科的領(lǐng)域，逐漸成為計算機科學研究的熱點之一，各種拓撲結(jié)構(gòu)的互連網(wǎng)絡(luò)，如環(huán)、Mesh、超立方體、星型網(wǎng)絡(luò)等得到迅速發(fā)展。在一個多處理器互連網(wǎng)絡(luò)中，處理器之間的有效通信是衡量系統(tǒng)性能的一個重要標準。當處理器數(shù)目逐漸增多時，其發(fā)生故障的可能性也隨之增加，不同處理器之間信息傳遞過程中的容錯性便成為一個非常關(guān)鍵的問題。因此，如何找出一種新的網(wǎng)絡(luò)容錯

2、模型以便容納更多的錯誤節(jié)點，以及如何設(shè)計高效的容錯路由算法以便保證無故障處理器間正確可靠的信息傳遞是至關(guān)重要的。 超立方體網(wǎng)絡(luò)是多處理機系統(tǒng)中常見的一種互連網(wǎng)絡(luò)，這種網(wǎng)絡(luò)拓撲結(jié)構(gòu)由于具有直徑小、可擴展性強、結(jié)構(gòu)對稱、網(wǎng)絡(luò)尋路算法簡單等優(yōu)點，且多種拓撲結(jié)構(gòu)的互連網(wǎng)絡(luò)都可以很容易的嵌入其中，因而成為最重要和最具吸引力的網(wǎng)絡(luò)模型之一。本文即是從上述兩個方面，對超立方體網(wǎng)絡(luò)的容錯性和路由算法進行研究，主要研究內(nèi)容如下： 1.提出

3、一種新的并行計算機網(wǎng)絡(luò)容錯模型-LIP導出嵌入模型，包括與LIP相關(guān)的概念、性質(zhì)、優(yōu)點，給出了超立方體網(wǎng)絡(luò)中求LIP的算法；針對此算法，文中給出了其C++實現(xiàn)程序，并求出了當維數(shù)n=6，7時LIP長度的精確值。 2.為了更好的分析超立方體網(wǎng)絡(luò)的容錯性，提出更為優(yōu)越的容錯路由算法，文章給出了超立方體網(wǎng)絡(luò)中LIP容錯模型的上下界估計，并給出一個非常有意義的猜想，而且結(jié)合程序結(jié)果對上下界及猜想進行了驗證。結(jié)果表明，LIP不僅具有較好的

4、容錯性，而且還能保證超立方體網(wǎng)絡(luò)的全局連通性，具有較好的實際意義。 3.基于文中提出的LIP容錯模型，結(jié)合路由選擇能力的概念，提出一種超立方體網(wǎng)絡(luò)單播容錯路由算法，該算法在“超立方體網(wǎng)絡(luò)中至少存在一條無故障節(jié)點的LIP”的條件下，所能容納的壞節(jié)點數(shù)多于2n-1，達到指數(shù)數(shù)量級；此外，該算法的最少步數(shù)為H(s，d)，極壞情況為ρ(Qn)+1，且算法達到極壞情況的可能性是非常小的，因此，算法在一定程度上是比較優(yōu)越的。 本文在