Torus交換結(jié)構(gòu)流量均衡和容錯路由算法研究.pdf

1、隨著計算機(jī)廣泛應(yīng)用于各行各業(yè)，計算機(jī)應(yīng)用在國民經(jīng)濟(jì)中扮演了越來越重要的角色。依賴于計算機(jī)應(yīng)用的一些領(lǐng)域如國防、金融、氣象對計算機(jī)的性能要求越來越高，它要求具有更快的處理速度，更高的帶寬以及更大的存儲容量。具有多處理器的并行計算機(jī)為實現(xiàn)高性能計算提供了可行的解決方案。基于多處理并行計算的相關(guān)技術(shù)也隨之發(fā)展起來，如拓?fù)浣Y(jié)構(gòu)、交換技術(shù)、內(nèi)部路由算法。Torus交換結(jié)構(gòu)由于具有靈活的可擴(kuò)展性，良好的對稱性已成為構(gòu)建大規(guī)模并行處理系統(tǒng)的常用選擇。

2、
　　 在給定網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)情況下，影響并行計算系統(tǒng)性能的因素很多：如路由算法的自適應(yīng)性、流量分布的均衡性。同時隨著交換節(jié)點和服務(wù)類型的增多，路由算法具有容錯性能以及支持QOS功能也不斷得到重視。本文主要集中于在Torus交換結(jié)構(gòu)下自適應(yīng)均衡路由算法和容錯路由算法的研究。
　　 針對以上問題，本研究的主要工作和貢獻(xiàn)在于：提出了一種基于奇偶轉(zhuǎn)彎模型的自適應(yīng)均衡路由算法，該路由算法在兩層虛網(wǎng)絡(luò)中引入對偶的奇偶轉(zhuǎn)彎模型，且數(shù)據(jù)包

3、在虛網(wǎng)絡(luò)中可以相互切換，對于所有的數(shù)據(jù)包而言都具有相同的路由自適應(yīng)性，因此可以很好地引導(dǎo)數(shù)據(jù)流均衡地分布于系統(tǒng)，且受流量模型的影響較少，最大程度地提高了虛通道的利用率，能夠較好地提高系統(tǒng)吞吐量，并在一定程度上減少了系統(tǒng)延時。進(jìn)一步地，我們提出了基于正向優(yōu)先負(fù)向優(yōu)先(positive-first-negative-first)的容錯路由算法，該算法充分利用了正向優(yōu)先負(fù)向優(yōu)先路由算法良好的自適應(yīng)性，按照一定規(guī)則在雙層虛通道上合理地分配數(shù)據(jù)包

4、來避免死鎖，該算法操作實施簡單、計算復(fù)雜度低、響應(yīng)速度快，可以適用于不同的故障模型的路由。
　　 本文的結(jié)構(gòu)如下：
　　 第一章介紹了多維交換結(jié)構(gòu)的拓?fù)浣Y(jié)構(gòu)，以及相應(yīng)的基本交換技術(shù)和流控技術(shù)，對路由算法的基本要求如死鎖、活鎖以及餓死的情況進(jìn)行了分析。
　　 第二章主要闡述了Torus交換結(jié)構(gòu)中不同機(jī)制的路由算法，比較了各自的優(yōu)缺點，然后介紹了本文的研究角度和相關(guān)工作。
　　 第三章主要研究了基于奇偶轉(zhuǎn)彎模

5、型的自適應(yīng)路由算法，分析了雙層奇偶轉(zhuǎn)彎模型的路由自適應(yīng)性以及流量的均衡性，闡述了算法的整體流程圖，并進(jìn)行無死鎖的證明，然后根據(jù)不同的業(yè)務(wù)流模型，與其它路由算法進(jìn)行了性能比較。
　　 第四章首先分析了正向優(yōu)先負(fù)向優(yōu)先自適應(yīng)均衡路由算法的特性，對它具有的容錯特性進(jìn)行了研究，針對特定的故障模型情況加一些限制進(jìn)行繞道路由。然后闡述了算法在容錯路由的過程中正確繞道路由的機(jī)制，最后對算法的性能進(jìn)行了評估，分析了性能下降的原因及可采用的應(yīng)對措