跳到主要內容

臺灣博碩士論文加值系統

(54.224.133.198) 您好!臺灣時間:2022/01/29 22:07
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:陳青文
研究生(外文):Chen Ching Wen
論文名稱:Gamma容錯網路的分析與設計
論文名稱(外文):Analysis and Design of Fault-tolerant Gamma Networks
指導教授:鍾崇斌
指導教授(外文):Chung Chung Ping
學位類別:博士
校院名稱:國立交通大學
系所名稱:資訊工程系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:108
中文關鍵詞:容錯網路內部連結網路Gamma 網路互斥道路動態繞路回溯繞路
外文關鍵詞:Fault-tolerantInterconnection networkGamma networkDisjont pathsDynamic reroutingBacktracking
相關次數:
  • 被引用被引用:0
  • 點閱點閱:163
  • 評分評分:
  • 下載下載:21
  • 收藏至我的研究室書目清單書目收藏:0
本論文研究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.

LIST OF FIGURES 6
1. INTRODUCTION 9
1.1 Motivation 9
1.2 Introduction to Gamma Networks 11
1.2.1 Topology 11
1.2.2 Routing Methods and Multiple Paths 12
1.2.3 Redundant Links 13
1.2.4 Problems 14
1.3 Research Topics 14
1.4 Overview of Main Results 16
2. REVIEW OF RELATED WORK 18
2.1 Previous Work on Disjoint Paths 18
2.1.1 The Problems of Previous Work on Disjoint Paths 22
2.2 Previous Work on Dynamic Routing 23
2.2.1 The Problems of Previous Work on Dynamic Routing 26
3. FINDINGS OF FAULT-TOLERANT PROPERTIES IN GIN 27
3.1 Disjoint paths in GIN 27
3.1.1 Two Disjoint Paths 28
3.2 Dynamic Routing 31
3.2.1 An All Non-straight Links Path 32
3.2.2 Dynamic Routing Tags 33
4. THE DESIGN OF DERIVED GINS FOR DISJOINT PATHS 37
4.1 Partial Chained Links at First Stage 37
4.1.1 Topology of PCGIN 37
4.1.2 Routing Methods in PCGIN 41
4.1.2.1 Distance tag routing 41
4.1.2.2 Destination Tag Routing in PCGIN 42
4.2 Combining Two Switches Into One Switch at First Stage 44
4.2.1 Topology of NBGIN 44
4.2.2 Routing Tags in NBGIN 46
4.3 Modifying The Non-straight Links at The Last Stage 47
4.3.1 Topology of 3DGIN 47
4.3.2 Routing Tags in 3DGIN 50
5. DESIGN DERIVED GAMMA NETWORKS FOR DYNAMIC ROUTING 55
5.1 Dynamic Routing along an Arbitrary Path 55
5.1.1 Using Bi-direction Chained Links (BCGIN) 56
5.1.1.1 The Topology of BCGIN 56
5.1.1.2 Routing in BCGIN 56
5.1.2 Combining Two Switches into One Switch at First Stage 59
5.1.2.1 The Topology of NBGIN 59
5.1.2.2 Distance Tag Routing 60
5.1.2.3 Destination Tag Routing in NBGIN 63
5.1.2.3.1 A New Destination Routing Function in GIN 63
5.1.2.3.2 A New Destination Tag Routing Function in NBGIN 65
5.1.3 Modifying Redundant Links to Chained Links 69
5.1.3.1 The Topology of FCGIN 69
5.1.3.2 Routing and Rerouting Methods in FCGIN 71
5.2 Dynamic Disjoint-Paths Switching 73
5.2.1 Conditions Analysis 74
5.2.2 Combining Switches GIN-2 75
5.2.2.1 The Topology of Combining Switches GIN-2 76
5.2.2.2 Dynamic Disjoint-Paths Switching Routing 78
5.2.3 CSGIN-0 81
5.2.3.1 The Topology of CSGIN-0 81
5.2.3.2 Dynamic Routing with a Faulty Element 84
5.2.4 Comparison 85
6. CONCLUSION 88
6.1 Concluding Remarks 88
6.2 Possible Future Work and Extended Research Topics 94
BIBLIOGRAPHY 96
PUBLICATION LIST OF CHEN CHING-WEN 100

[Adams, et al. 1987] Adams G. B. II, Agrawal D. P., and Siegel H. J., “A Survey and Comparison of fault-tolerant Multistage Interconnection Networks,” IEEE Transactions on Computer vol. 20, no. 6, pp. 14-27, June 1987.
[Chen, et al. 2000] Chen C. W., Lu N. P., Chen T. F., and Chung C. P., “Fault-tolerant Gamma Interconnection Networks by Chaining”, IEE Proceedings of Computers and Digital Techniques, vol. 147 no. 2 pp. 75-80, March 2000.
[Chuang 1996] Chuang P. J., “CGIN: A Fault Tolerant Modified Gamma Interconnection Network,” IEEE Transactions on Parallel and Distributed Systems, vol. 7, no. 12, pp. 1301-1306, December 1996.
[Goke and Lipovski 1973] Goke L. R. and Lipovski G. J., “Banyan networks for partitioning multiprocessing systems,” Proc. First Ann. Computer Architecture Conf., pp. 21-28, Dec. 1973.
[Gottlieb et. al. 1983] Gottlieb A., Grishman R., Kruskal C. P., McAuliffe K. P., Rudolph L. and Snir M., “The NYU Ultracomputer — Designing an MIMD Shared Memory Parallel Computer,” IEEE Transactions on Computers, C-32(2), pp. 175-189, February 1983.
[Kuck et. al. 1986] Kuck D. J., Davidson E. S., Lawrie D. H. and Sameh A. H., “Parallel Supercomputing Today — The Cedar Approach,” Science, 231(2), Feb. 1986.
[Lee and Yoon 1989] Lee K. Y. and Yoon H., “The PM22I Interconnection Network, IEEE Transaction on Computers,” vol. 38, no. 2, pp. 302-307, February 1989.
[Lee and Yoon 1990] Lee K. Y. and Yoon H., ”The B-network: A Multistage Interconnection Network with Backward Links,” IEEE Transactions on Computers vol. 39, no. 7, pp. 966-969, July 1990.
[Lau and Poon 1998] Lau F. C. M and Poon W. C., “Throughput Analysis of B-Networks,” IEEE Transaction on Computers, vol. 47 no. 47 pp. 482-485 April 1998.
[McMillen and Siegel 1982] McMillen R. J. and Siegel H. J., “Performance and fault tolerance improvements in the inverse augmented data manipulator network,” 9th Symp. Computer Architecture, 63-72 1982.
[McMillen and Siegel 1984] McMillen R. J. and Siegel H. J., ”Routing schemes for augmented data manipulator network in an MIMD system,” IEEE Transactions on Computers, vol. 33, pp. 367-373, April 1984.
[Parker and Raghavendra 1984] Parker D.S. and Raghavendra C.S., “The Gamma Network,” IEEE Transactions on Computers, vol. C-33, pp.367-373, April 1984.
[Pfister et. al. 1985] Pfister G. F., Brantley W. C., George D. A., Harvey S. L. Kleinfelder W. J., McAuliffe K. P., Melton E. A., Norlton V. A. and Weiss J., “The IBM Research Parallel Processor Prototype (RP3): Introduction and Architecture,” Proc. Int. Conf. Parallel Processing, pp. 764-771, August 1985
[Rau, et al. 1992] Rau D., Fortes J. A. B. and Siegel H. J., “Destination Tag Routing Techniques Based on a State Model for the IADM Network,” IEEE Transactions on Computers, vol. 41, no. 3, pp. 274-285, March 1992.
[Seo and Feng 1995] Seo S. W. and Feng T. Y., “The Composite Banyan Network,” IEEE Transactions on Parallel and Distributed Systems, vol. 6, no. 10, pp. 1043-1054, October 1995.
[Stunkel, et al. 1994] Stunkel C. B., Shea D. G., Grice D. G., Hochschid P. H. and Tsao M., “ The SP1 High-Performance Switch,” in Proceedings of the Scalable High Performance Computing Conference, Knoxville, TN, May 1994.
[Tzeng and Zhu 1988] Tzeng N. F., P. C., and Zhu C. Q., “Realizing Fault-tolerant Interconnection Networks via Chaining,” IEEE Transaction on Computers vol. C-37, no. 4, pp. 458-462 April 1988.
[Wu and Feng 1980] Wu C. L. and Feng T., “On a class of multistage interconnection networks,” IEEE Transactions on Computers, vol. 29, pp. 694-702, August 1980.
[Yoon and Hegazy 1988] Yoon K. and Hegazy W., “The Extra Stage Gamma Network,” IEEE Transactions on Computers, vol. 37, no. 11, pp. 1445-1450, November 1988.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top