超方體網路拓蹼一般化之研究

Abstract

在此論文中, 我們提出三種新的網路拓蹼。Super Generalized Hypercube以 Generalized Hypercube 和 Supercube 系統為基礎：給定 系統節點個 和希望之半徑 k, 我們可建構此一類網路, 其每一節點之節 點度數 於 k(\lfloor\sqrt[k]{N}\rfloor -1) 和 (2k-1)( \lceil\sqrt[k]{N}eil -1)-1 之間；而其節點連接性則至少為 k( \lfloor\sqrt[k]{N}\rfloor -1)。此外, 對於每一 Super Generalized Hypercube 中之任意兩個節點間, 至少存在 k( \lfloor\sqrt[k]{N}\rfloor -1) 條節點互斥 且路徑長度小於等於 k+1 之路徑。在節點個數為 N 及半徑為 k之情況下, 我們提出另一種建 構方式來建構一個 small node degree 之網路架構；此類網路 -- 以 D\sub{R}(k,N)來表示-- 主要是以規律性有向圖為基礎。由於光纖之單向 特性, 有向圖可以直接地應用於光纖網路；同樣地,由於 D\sub{R}(k,N) 網路之規律性及環狀對稱性,我們可以提出一個簡單的路由演算法則。此 外, 我們也提出一個最佳化廣播演算法則。D\sub{R}(k,N) 網路之節點度 數至多為 k(\lceil\sqrt[k]{N}\rceil -1), 若我們令 k= \lceil\log\sub{2}N \rciel, 則其節點度數(入度數及出度數)為 k；此 結果顯示出：當預期之網路半徑為 \lceil\log\sub{2}N\rceil 時, D\sub{R}(k,N)網路和相對應之 Hypercube 相似的節點及度數特性。 Supercube 是 Hypercube 架構的一般版之一, 它不像 Hypercube 一樣限 制系統大小, 並保存一些相對應的拓蹼特性如：半徑及節點連接性等。因 此我們提出了 Folded Supercube 架構來提昇 Supercube 的系統效能,此 架構之動機來自於 Folded Hypercube：在原來的系統架構上加上一些額 外的連結來降低系統的半徑。Folded Supercube 的半徑為 \lceil m/2 \rceil, 節點度數介於 m 和 2m 之間, 而節點連接性則至少為 m,此處 m=\lceil\log\sub{2}N\rceil。 In this dissertation, we propose three new classes of interconnection network topologies for parallel and distributed processing. The Super Generalized Hypercube is based on the Generalized Hypercube and the Supercube systems. Given the number of nodes N and the desired diameter k, a topology can be constructed. Another class of interconnection networks is to give the construction of a network with small node degree for a given number of nodes N and a given diameter k. The class of networks, denoted by D\sub{R}(k,N), is a new network topology based on regular digraphs (directed graphs). Digraphs can be easily fit into the fiber network because of the unidirectional nature of optical fiber. As well as it is easy to propose a simple routing on D\sub{R}(k,N) networks due to the regularity and cyclical symmetry of the proposed network topology. We also present an optimal broadcasting algorithm in D\sub{R}(k,N) networks. The primary emphasis of the D\sub{R}(k,N) network is on the construction of a regular directed network for arbitrary number of ndoes with a given diameter, while hypercubes are defined only for 2\sup{n}-node systems. Supercube is a generalization of Hypercube topology, which allows arbitrary sizes of systems and maintains some topological properties such as diameter and connectivity of the corresponding hypercube. Hence we consider the architecture on enhancing the system performance of the Supercube network topology. The Folded Supercube is motivated by the Folded Hypercube networks. Like Folded Hypercubes, some extra connections are added to reduce the diameter of a supercube.