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

1、Mesh網(wǎng)絡(luò)作為一個(gè)嚴(yán)格正交的拓?fù)浣Y(jié)構(gòu)，具有結(jié)構(gòu)簡(jiǎn)單的特點(diǎn)，在當(dāng)前流行的多核計(jì)算機(jī)體系結(jié)構(gòu)與片上網(wǎng)絡(luò)系統(tǒng)中得到了廣泛使用。網(wǎng)絡(luò)之間的信息交流需要有一個(gè)良好的路由算法來(lái)保障，一個(gè)好的路由算法可以提高互連網(wǎng)絡(luò)的網(wǎng)絡(luò)吞吐率，降低網(wǎng)絡(luò)中消息的傳輸延時(shí)。之前的路由算法都需要使用多條虛擬通道來(lái)保證算法的無(wú)死鎖，但增加虛擬通道的數(shù)目會(huì)降低消息的傳輸速度，增大消息的總延遲，并且會(huì)增大路由器的成本和功耗。
　　自適應(yīng)路由算法是在網(wǎng)絡(luò)中進(jìn)行消息傳輸時(shí)

2、，如果遇到通道繁忙等情況時(shí)可以根據(jù)網(wǎng)絡(luò)當(dāng)前的狀態(tài)自主選擇路徑進(jìn)行路由。提出了ePAR自適應(yīng)路由算法，保證無(wú)死鎖的同時(shí)降低了虛擬通道的使用數(shù)目，均勻模式下，ePAR算法性能與其他算法相類(lèi)似;非均勻模式下，之前的自適應(yīng)路由算法的平均延遲在標(biāo)準(zhǔn)化實(shí)用負(fù)載是22％時(shí)急速上升，而ePAR算法在31％時(shí)才急速上升。ePAR具有更好的性能，延遲比以前的算法好并且該算法不僅可以適用于3D-Mesh網(wǎng)絡(luò)，同樣是應(yīng)用于nD-Mesh網(wǎng)絡(luò)。
　　隨機(jī)O

3、blivious路由算法路由時(shí)不需要考慮網(wǎng)絡(luò)狀態(tài)，通過(guò)隨機(jī)地選擇在源節(jié)點(diǎn)到目的節(jié)點(diǎn)之間存在的多條路徑進(jìn)行路由，具有較高的路由靈活性，能達(dá)到更好的性能。本文在奇偶轉(zhuǎn)彎的基礎(chǔ)上提出了一個(gè)新的Oblivious路由算法OETURN，與不使用虛擬通道的DOR算法相比不同通訊模式下的網(wǎng)絡(luò)吞吐率都要好，與使用多條虛擬通道的算法相比雖然在其他通訊模式下的網(wǎng)絡(luò)吞吐率并不是很理想，但在平均情況下的網(wǎng)絡(luò)吞吐和其他算法相差不大，且之前的算法用到的虛擬通道數(shù)目