蜂窩網(wǎng)格上的路由算法研究.pdf

1、并行計算機系統(tǒng)的性能和可靠性是與架構(gòu)并行計算機系統(tǒng)網(wǎng)絡結(jié)構(gòu)的性質(zhì)密切相關(guān)的。根據(jù)圖論的知識，直接網(wǎng)絡的結(jié)構(gòu)可以用圖來表示。至今，已經(jīng)有數(shù)十種直接網(wǎng)絡被提出并應用在并行多處理機系統(tǒng)當中，同時直接網(wǎng)絡也成為并行系統(tǒng)通信的研究熱點。 在一個理想的直接網(wǎng)絡中，每個節(jié)點是應該有固定的節(jié)點度的，蜂窩網(wǎng)格就是這樣的一類網(wǎng)絡。和二維網(wǎng)格相比較，蜂窩網(wǎng)格的節(jié)點度比二維網(wǎng)格少1，網(wǎng)絡成本更少。由此可見，蜂窩網(wǎng)格是很適合作為并行系統(tǒng)的候選網(wǎng)絡。

2、 在直接網(wǎng)絡中，節(jié)點間的通信效率是依賴于該網(wǎng)絡所采用的路由策略的效率。網(wǎng)絡性能的好壞是可以用網(wǎng)絡所采用的路由策略性能的好壞來衡量。本文的主要工作是在蜂窩網(wǎng)格上設計高效的路由算法。這些算法包含了單播路由算法、容錯路由算法和多播路由算法三類。理論和仿真實驗表明，這些算法都是無死鎖的，并且具有較高的效率。 首先，基于蜂窩網(wǎng)格的單播路由算法，提出了兩個單播蟲孔路由算法。第一個算法是沒有采用虛擬通道技術(shù)的單播路由算法。第二個算法是采用了

3、虛擬通道技術(shù)的最短路徑單播路由算法，簡稱Double-XY Route。仿真實驗表明，第二個算法的性能是優(yōu)于沒有采用虛通道技術(shù)的第一個算法的。 其次，提出了蜂窩網(wǎng)格的一個容錯蟲孔路由算法，簡稱為HFT-Route。該算法的容錯策略是基于凸故障模型的，算法的設計采用了四個虛擬通道和維序路由兩種技術(shù)。理論分析表明，該算法是無死鎖的，采用該算法報文可以在有多個凸故障的情況下路由至目的節(jié)點。 最后，提出了一個多播路由算法。該算法