Gamma 容錯網路的分析與設計

Abstract

本論文研究Gamma容錯網路的問題，因為容錯的問題對於高可靠度多處理機系統是一個重要的議題。在先前容錯網路的研究中大多是以提供互斥路徑（disjoint paths）的方式來提高可靠度，但是以動態繞路的方式來避免遇到未知的錯誤的能力很是很重要卻很少被提及。Gamma 網路的架構在提供互斥網路或是動態繞路的行為都可以容易被做到。在本論文中，我們討論幾個重要的議題：(1)找尋互斥路徑。(2)使用動態繞路的方式來容忍錯誤。(3)以動態的方式將訊息從一條互斥路徑換到另一條互斥路徑。 大部分的Gamma 容錯網路都是修改重複連結來提供互斥網路，但是這樣的方式，會使的重複連結的特性消失。重複連結的特性是在訊息遇到錯誤時將是很有用的。沒有重複連結的互斥路徑上面的訊息遇到錯誤時，訊息要沿著原路回溯至出發點，然後選擇另一條互斥的路徑來到達目的地。因為這樣，我們希望能夠找到：(1)互斥路徑的Gamma網路並且保留重複連結。 不同於回溯的方式，當一個訊息遇到錯誤時，動態繞路的方法是改變原來的路徑來容忍不明的錯誤。所以我們第二個研究的主題為找到(2)最小花費的動態繞路的Gamma 網路來容忍錯誤。 而且，當一個訊息經由一條互斥路徑被繞到終點且遇到一個錯誤時，動態地把訊息繞到另一條互斥路徑而不是使用回溯的方式都沒有被討論到。所以我們要找一個能夠動態的在互斥路徑中交換訊息的網路。 我們的研究一開始先以熟悉已經存在的Gamma 網路為主。從這些先前的研究中，在某些的來源與目的節點中，我們發現了一些可以提供互斥路徑與動態網路的特性。 為了讓這些特性可以被適用於所有的情況，我們提供了一些修改Gamma 網路的方法，這些方法將使的Gamma 擁有兩條以上的互斥路徑或是擁有動態繞路的能力。在提供互斥路徑方面，Partial Chained GIN (PCGIN)與NBGIN，這兩個網路提供了至少兩條的互斥路徑，而且保留的重複連結的特性與目標標籤的繞路法。除此之外，這兩個網路遇到錯誤時將不用回溯到源頭，只有回溯到一條非直線的連結即可。3DGIN也是修改重複連結的方法來提供互斥路徑，但是在硬體沒有增加下，3DGIN提供了三條互斥網路。但是3DGIN遇到錯誤時，必須回溯到源頭然後選擇另一條互斥道路。 雖然這些新的設計中提供兩條以上的互斥路徑，但是訊息遇到錯誤時，並不能馬上走另一條互斥路徑。為了解決這個問題，我們研究我們所提供的互斥道路，並且發現了一個特性。透過這個特性，我們修改Gamma 讓它能夠從一條互斥道路馬上換到另外一條互斥道路而不用透過回溯的方式。CSGIN-0 與 CSGIN-2就是提供了訊息可以在兩條互斥網路中跳來跳去的網路。 對於動態繞路的方式來說，FCGIN 把重複連結修改成直線連結(chained links)，這個直線連結提供了訊息遇到錯誤時的替代道路。但是由於直線連結是連結同一階(stage)的交換器(switches)，所以FCGIN需要一個連結的花費。跟直線連結需要一個連結的額外花費不同的，我們發現了一條路，這條路都是由非直的連結所構成，但是這條路只有在某些來源目的節點才存在。 為了讓所有的來源與目的節點都可以有這條路（所有都以非直線的連結所構成的路），我們也提供了修改的法則來產生可以動態繞路的Gamma 網路。 NBGIN 與 Bi-directional Chained GIN 不僅僅可以容忍一個錯誤，而且在找替代道路時的花費也是最小的。 本論文中，我們發現一些Gamma 網路的一些特質，這些特質可以讓讀者瞭解容錯網路的一些現象，包含網路架構，繞徑法，重繞等等。再者利用這些發現的性質，我們也提供了一些修改的法則讓網路不管任何的來源與目的節點，都可以有兩條以上的互斥路徑或是動態繞路的方法。我們相信這些法則不僅可以用在Gamma 網路，如果其他的MIN有類似的問題，也可以用我們所提供的法則來修改。

The problems associated with fault-tolerant Gamma networks are concerned in this dissertation because fault-tolerance issue is a significant task for high reliability in multiprocessor. In previous research in fault-tolerant designs, the work has been based on providing disjoint paths to improve the reliability, but the dynamic rerouting capability to tolerate unknown switch or link fault is also important. Gamma networks are well architected for designing disjoint paths and dynamic rerouting. In this dissertation, three significant issues are explored. These are (1) finding disjoint paths in Gamma related networks, (2) using dynamic routing to tolerate faults, and (3) dynamic disjoint paths switching. Most existing fault-tolerant Gamma networks modify the redundant links to have disjoint paths but they loose the redundant links property in Gamma network. The redundant links property is useful when packets meet faults. Without redundant links property, packets must be backtracked by the traversed path to source and take another disjoint path. With redundant links, packets can be backtracked to a non-straight link rather than the source. Due to these facts, we want to find (1) disjoint paths Gamma derived networks with redundant links property. Rather than backtracking when packets meet a fault, dynamic routing is to change the routing path to tolerate unknown faults. The second research topic is to find (2) minimal cost dynamic routing Gamma networks to tolerate an unknown fault. Moreover, when a packet is being routed to the destination via one of the disjoint paths and encounters a faulty element, dynamically routing the packet to another disjoint path without backtracking is not discussed. We want to find (3) dynamic disjont paths switching derived Gamma networks. We begin this research with familiarization of existing of Gamma networks. From previous research in Gamma networks, we exploit some properties to provide disjoint paths and dynamic routing methods in Gamma networks under certain constraints. In order to make the properties useful for any source and target pair, we propose some methods to make the derived Gamma networks have disjoint paths or dynamic routability. The results are Partial Chaining Gamma Interconnection Network (PCGIN) and NBGIN, which provide two disjoint paths, redundant links property and destination tag routing. Besides two disjoint paths, PCGIN and NBGIN can backtrack packets to a non-straight link than the source. In contract, we also modify redundant links to have 3 disjoint paths but no more hardware cost added. 3DGIN that has three disjoint paths and no more hardware cost but the redundant links property is lost. Although the new design can provide disjoint paths, the packet cannot go to the other disjoint path right away when it is taking one of the disjoint paths and meets a faulty element. In order to solve this problem, we explore the property of our designed disjoint paths. By the property, some derived Gamma networks can help a packet traverse to the other disjoint path without backtracking when a packet meets a faulty element. CSGIN-0 and CSGIN-2 make the packet to switch between disjoint paths. For dynamic routing, the FCGIN modify the redundant links to chained links as alternative links to provide alternative paths, so FCGIN need one more extra link penalty to find an alternative path to next stage. Rather than having extra links traversed to find an alternative path, we also find an all non-straight links path in Gamma networks under certain constraints. In order to make all source-target pairs have the all non-straight links path, the modify schemes mentioned in designing disjoint paths are also applied to generate derived dynamic routing Gamma networks. The derived Gamma networks of combing switches or bi-directional chained at stage 0 not only have dynamic routability to tolerate one fault, but also minimize the number of extra links traversed to find an alternative path. In this dissertation, we find some properties of GIN and these properties can help reader understand the fault-tolerant natures including topology, routing and rerouting. In addition to the findings of the properties, we present some schemes to generate new derived networks to have disjoint paths or dynamic routability. We believe that these schemes can be applied not only in Gamma but also in other MINs.