基于TORUS網(wǎng)絡(luò)的高效路由算法研究.pdf

1、最小的傳輸延時和最大的吞吐率是設(shè)計一個好的路由算法最重要的性能指標(biāo)。理想情況下，我們希望一個好的路由算法同時滿足:(1)最小的路由跳數(shù)以減小傳輸延時，保持通訊的局域性;(2)最大的平均情況和最壞情況吞吐率;(3)簡單的路由器結(jié)構(gòu)。隨機(jī)Oblivious路由算法路由時不需要考慮網(wǎng)絡(luò)狀態(tài)，通過隨機(jī)地選擇在源節(jié)點到目的節(jié)點之間存在的多條路徑進(jìn)行路由，具有較高的路由靈活性，在低功耗并行計算機(jī)互連網(wǎng)絡(luò)以及片上網(wǎng)絡(luò)中得到廣泛應(yīng)用。
　　目前已

2、提出的Oblivious路由算法普遍使用了多條虛擬通道，使用增加虛擬通道的數(shù)目可以避免死鎖的產(chǎn)生，但是虛擬通道的數(shù)目并不是越多越好，增加虛擬通道的數(shù)目會影響網(wǎng)絡(luò)的性能以及增大成本與功耗。所以研究如何在確保性能不會下降，甚至在某些通訊模式下有所提升的前提下，進(jìn)一步提出低虛擬通道數(shù)量、低傳輸延時的新的Oblivious路由算法具有重要意義。
　　本文運(yùn)用RLB算法與O1TURN算法的核心思想，提出了一個2D-Torus網(wǎng)絡(luò)上隨機(jī)Obl

3、ivious路由算法——WRD路由算法，該算法與使用兩條虛擬通道的O1TURN路由算法相比，WRD路由算法在所有通訊模式下的網(wǎng)絡(luò)吞吐率均有所提升。與使用四條虛擬通道的RLB算法相比，新提出的WRD路由算法性能接近于RLB算法，甚至在多個通訊模式下的網(wǎng)絡(luò)吞吐率要好于RLB算法，而且WRD路由算法僅使用兩條虛擬通道，降低了網(wǎng)絡(luò)系統(tǒng)成本和功耗。
　　WRD路由算法雖然只使用兩條虛擬通道，這是它的優(yōu)勢，但對網(wǎng)絡(luò)吞吐率的提高并不是很大。而好

4、的吞吐率是我們設(shè)計一個好的路由算法追求的目標(biāo)。通過對RLB算法存在的缺點進(jìn)行分析與改進(jìn)，進(jìn)一步提出了一個2D-Torus網(wǎng)絡(luò)上高性能隨機(jī)Oblivious路由算法——M2TURNS路由算法。該算法與O1TURN路由算法相比，M2TURNS路由算法在絕大多數(shù)通訊模式下的吞吐率都遠(yuǎn)高于O1TURN。特別是在平均情況下，M2TURNS路由算法的表現(xiàn)非常好，并且隨著網(wǎng)絡(luò)規(guī)模的增大，吞吐率優(yōu)勢越來越大。與使用四條虛擬通道的RLB算法相比，M2TU