1、隨著計算機廣泛應用于各行各業(yè)，計算機應用在國民經濟中扮演了越來越重要的角色。依賴于計算機應用的一些領域如國防、金融、氣象對計算機的性能要求越來越高，它要求具有更快的處理速度，更高的帶寬以及更大的存儲容量。具有多處理器的并行計算機為實現高性能計算提供了可行的解決方案?；诙嗵幚聿⑿杏嬎愕南嚓P技術也隨之發(fā)展起來，如拓撲結構、交換技術、內部路由算法。Torus交換結構由于具有靈活的可擴展性，良好的對稱性已成為構建大規(guī)模并行處理系統的常用選擇。

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

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

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

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