超立方体网络中路由生成算法的子立方分裂方法  

A Sub-Cube Splitting Method in Generating Routing Table in Hypercubes

作　　者：汪洋[1,2] 余少华[1,2] 

机构地区：[1]华中科技大学计算机科学与技术学院,武汉430074 [2]武汉邮电科学研究院,武汉430074

出　　处：《计算机科学》2005年第4期16-18,共3页Computer Science

基　　金：国家"863"项目新型城域网关键技术及实验系统和高性能以太网交换机核心芯片开发(项目编号分别为2003AA121110和2003AA1Z1180)资助

摘　　要：超立方网络拓扑是并行计算中最重要的多处理机互连结构之一,目前对它的研究热点主要集中在当超立方的网络互连结构中具有失效结点时,如何快速计算其上点到点的并行路由.本文提出利用子立方来分解整个空间,使得原来的超立方网络互连结构可以非常规整地分解成若干个子立方,因而若以子立方为路由目的,可以显著简化路由表,从而降低并行计算中的寻路开销.进一步,这种技术应用在具有局部失效结点的超立方网络时,同样能够压缩路由表,避免从整体上计算点到点的最佳路由,将这种计算分布在超立方中的多数正常结点独立完成.这种寻路方式为高度对称的网络互连拓扑中路由的生成提供了新的思路.Hypercube is an important type of interconnection topology in parallel computing. Recent researches focus on the computing of parallel routes of arbitrary end to end with the tolerance of faulty nodes in the hypercube. The description of this problem is: given the source and the destination, how to compute the many feasible routes between the ends? In this paper, we try to decompose the hypercube to its sub-cubes, and in this manner, the whole hypercube can be partitioned into sub-cubes with perfect regularity. Therefore, if the routing table of each single node in the hy- percube aggregates its routing entries with their destinations to individual nodes into entries with their destinations to sub-cubes, the routing table can be conspicuously shortened, thus the overall routing cost is reduced in hypercube for parallel computing. Furthermore, we employ this method in the scenario where there are locally distributed faulty nodes, and likewise the routing table is considerably simplified. By avoiding computing the optimal routes from end to end, the individual normal nodes have their routing tables computed distributively. At the final part of this paper, we discuss the scenario where the method presented in this paper does not cover, and the possible approach that could generalize our work to it. This routing method brings forth a fresh idea in highly symmetric interconnection network- s.

关 键 词：超立方体网络 分裂方法 生成算法 超立方网络 互连结构 并行计算 多处理机 网络拓扑 研究热点 快速计算 技术应用 网络互连 路由表 结点 计算点 失效 分解 

分 类 号：TP393[自动化与计算机技术—计算机应用技术] O242.23[自动化与计算机技术—计算机科学与技术]