標題: 變種之超立方體 : 一種新的大型多計算機之內連網路方式
Varital Hypercube - A New Interconnection Network Topology for Large Scale Multicomputer
作者: 鄭守益
Shou-Yi Cheng
莊仁輝
Dr. Jen-Hui Chuang
資訊科學與工程研究所
關鍵字: 直徑;崁入;超立方體;內連網路;多計算機;Diameter;Embedding;Hypercube;Interconnection network; Multicomputer
公開日期: 1993
摘要: 在此論文中,我們提出變種超立方體,它是一種適合大型多計算機之新型
內連網路方式。一個 n 維的變種超立方體可由兩個(n-1) 維者所建構成
,除了某些線的連接方式不同之外,基本上它和超立方體相似:節點數和
連接線跟超立方體相同,且在結構上有遞迴、可分割性、強連接性和能崁
入其它結構如環和網。而且,它的直徑大約是超立方體直徑的三分之二、
平均傳輸所需距離亦比超立方體小。這顯示它處理訊息交流的能力將會比
超立方體來的有效率。此外,能在 2n/3 步驟內完成傳輸、廣播訊息的演
算法亦被發展出來。
This thesis proposes a new interconnection network topology,
called varietal hypercube, for large scale multicomputer
systems. An n-dimensional varietal hypercube is constructed by
two (n-1)-dimensional varietal hypercubes in a way similar to
that for the hypercube except for some minor modifications. The
resulting network has the same number of nodes and links as the
hypercube, and has most of the desirable properties of the
hypercube including recursive structure, partionability,
strong connectivity, and the ability to embed other
architectures such as ring and mesh. The diameter of the n-
dimensional varietal hypercube is 2n/3, i.e., about two two
third of the diameter of the hypercube. The average distance of
the varietal hypercube is also smaller than that of the
hypercube. This implies the interprocessor communication will
be more efficient than that in hypercube. Optimal routing and
broadcasting algorithms which guarantee the shortest path
communication in steps are also developed. Comparisons withr
other variations of the hypercube, such as twisted cube, folded
hypercube, and crossed cube, are also included.
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT820394020
http://hdl.handle.net/11536/57917
Appears in Collections:Thesis