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

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

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

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