變種之超立方體 : 一種新的大型多計算機之內連網路方式

Abstract

在此論文中，我們提出變種超立方體，它是一種適合大型多計算機之新型 內連網路方式。一個 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.