標題: 設計與分析超立方體與星狀圖架構之連結網路
Design and Analysis of Cube-Based and Star-Based Interconnection Networks
作者: 江為國
Chiang, Wei-Kuo
陳榮傑
Rong-Jaye Chen
資訊科學與工程研究所
關鍵字: 超立方體;星狀圖;路由演算法;嵌置;容錯能力;平行演算法;hypercubes;star graphs;routing algorithms;embeddings;fault tolerance;parallel algorithms
公開日期: 1995
摘要: 『超立方體』(Hypercubes) 與『星狀圖』(Star graphs) 是 目前最受矚目的兩個連結網路 (Interconnection networks) 架構。為了 提昇效能或針對特定的需求,它們的一些變形相繼被提出與探討。在這篇 論文當中,我們將更深入分析兩個已被提出的網路架構:分別是『層次超 立方體狀網路』(Hierarchical Cubic Networks) 與『編排圖』( Arrangement graphs) 。此外,我們將提出兩個『超立方體』狀的連結網 路: 分別是 『多層次超立方體』(Multilevel hypercubes) 與 『金字 塔化超立方體』(Pyramided hypercubes) 。前者是『層次超立方體狀網 路』的一般化架構;而後者是一個具有最佳容錯能力的網路架構,在結點 間互連程度固定下,其系統可作彈性延伸,此架構可視為用來取代『延伸 性超立方體』(Extended hypercubes) 的一種選擇。另外,我們也將提出 一個『星狀圖』架構的變形,稱之為『(n,k)-星狀圖』((n,k)-Star graphs) ,是『星狀圖』網路的一般化架構,也可視為用來取代『編排圖 』網路架構的另一種選擇。論文最後,我們將『超立方體』與『星狀圖』 的優點加以結合,設計出一個新的網路連結策略,稱之為『區段互調式網 路』 (Block-swapped networks) 架構。 The hypercube and the star graph have been two of the most popular interconnection networks. Several variations of them have been proposed and investigated to overcome their shortcomings. In this dissertation, we will further analyze the topological properties of two already proposed network topologies: the hierarchical cubic network and thearrangement graph. In addition, we will propose two cube-based interconnection networks: the multilevel hypercube and the pyramided hypercube; the former can be considered as a generalization of the hierarchical cubic network, the latter is an optimal fault tolerant network for extendability with fixed degree as an alternative to the extended hypercube. We will also propose a star-based interconnection network called the (n, k)-star graph; it is a generalization of the star graph as an alternative to the arrangement graph. Finally, we will propose a new interconnection scheme, called the block-swapped network, combining positive features of both the hypercube and the star graph.
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT840392087
http://hdl.handle.net/11536/60436
顯示於類別:畢業論文