Properties and Performance of Folded Hypercubes
Properties and Performance of Folded Hypercubes
复制标题
DOI：
10.1109/71.80187
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
A. El-Amawy;S. Latifi
中科院分区：
文献类型：
--
作者：
A. El-Amawy;S. Latifi
提出并分析了一种新的超立方体结构-折叠超立方体（FHC），它基本上是一个标准的超立方体，在其节点之间建立了一些额外的链接。硬件开销几乎是1/n，n是超立方体的维数，这是可以忽略不计的大n。对于这种新的设计，最佳路由算法的开发和证明是显着更有效的比传统的n-立方体。对于一对一通信，每个节点可以在最多（n/2）跳中到达网络中的任何其他节点（每个跳对应于单个链路的遍历），而不是标准超立方体中的n跳。一对所有的通信（广播）也可以只在（n/2）步中执行，与标准超立方体相比，广播时间提高了50%。所有的路由算法都很简单，易于实现。给出了算法的正确性证明。对于所提出的架构，通信参数，如平均距离，消息流量密度，和通信时间延迟。此外，一些容错能力的这种架构进行了量化和比较的标准立方体。结果表明，这种结构提供了显着的改善现有的超立方体型网络在上述网络参数。>
A new hypercube-type structure, the folded hypercube (FHC), which is basically a standard hypercube with some extra links established between its nodes, is proposed and analyzed. The hardware overhead is almost 1/n, n being the dimensionality of the hypercube, which is negligible for large n. For this new design, optimal routing algorithms are developed and proven to be remarkably more efficient than those of the conventional n-cube. For one-to-one communication, each node can reach any other node in the network in at most (n/2) hops (each hop corresponds to the traversal of a single link), as opposed to n hops in the standard hypercube. One-to-all communication (broadcasting) can also be performed in only (n/2) steps, yielding a 50% improvement in broadcasting time over that of the standard hypercube. All routing algorithms are simple and easy to implement. Correctness proofs for the algorithms are given. For the proposed architecture, communication parameters such as average distance, message traffic density, and communication time delay are derived. In addition, some fault tolerance capabilities of this architecture are quantified and compared to those of the standard cube. It is shown that this structure offers substantial improvement over existing hypercube-type networks in terms of the above-mentioned network parameters. >