994 International Conference on Parallel Processing a Comparative Study of Star Graphs and Rotator Graphs*
994 International Conference on Parallel Processing a Comparative Study of Star Graphs and Rotator Graphs*
复制标题
994国际并行处理会议星图和旋转图的比较研究*
DOI：
10.1109/icpp.2004
复制
发表时间：
--
期刊：
影响因子：
--
通讯作者：
M. Sampels
中科院分区：
文献类型：
--
作者：
M. Sampels
星星图是一种被广泛研究的Cayley图，被认为是流行的二进制立方体的一个有吸引力的替代。旋转图是最近引入的一组有向Cayley图。在本文中，我们比较的结构和算法方面的星星图与旋转图。在这个过程中，我们提出了一些新的结果星星图和旋转图。给出了星星图中距离单位置换任意距离的节点数的计算公式。得到了星星图和旋转图的最小平分宽度。分析了星星图和转子图的划分和容错参数。给出了旋转图的节点不交平行路和故障直径的上界。我们比较了最小路径路由在星星和旋转图使用模拟结果。引言任何多处理器系统的性能主要取决于底层互连拓扑的通信效率。在文献中已经介绍了许多用于通用和专用应用的互连网络。对多进程处理器的通信高效对称互连结构的持续搜索已经导致凯莱图作为可能的互连网络结构[11]。Cayley图的一些例子包括星星图[1，2]，旋转图[4]，圈前缀有向图[8]，二元n-立方体和立方体连通圈。由于它们的简单性和真实的世界通信链路（例如光链路）通常由有向通信链路实现的事实，一些无向网络的有向对应物也出现在文献中，例如，单向超立方体[3]和单向星星图[6]。通过定义给出了n-旋转图和圈前缀有向图。由于这些有向Cayley图与星星图相比具有易路由、低直径和平均直径等有趣的性质，因此对这些图进行比较分析是值得研究的。本文给出了星星图和旋转图的一些新结果。利用星星图的循环结构，我们给出了一个计算距离单位置换任意距离的节点数的公式。最小二分法宽度，在VLSI模型中的一个重要措施，得到了星星和旋转图。我们证明了大小为n的旋转图！具有n-1个节点不相交的平行路径，其长度至多为n + 1，其中n > 2。另一个错误...
Star graph is an extensively studied Cayley graph, considered to be an attractive alternative to the popular binary cube. The rotator graphs are a set of directed Cayley graphs introduced recently. In this paper we compare the structural and algorithmic aspects of star graphs with that of rotator graphs. In the process we present some new results for star graphs and rotator graphs. We present a formula for the number of nodes at any distance from the identity permutation in star graphs. The minimum bisection width of star and rotator graphs is obtained. Partitioning and fault tolerant parameters for both star and ro tator graphs are analyzed. The node disjoint parallel paths and hence the upper bound on the fault diameter of rotator graphs are presented. We compare the minimal path routing in star and rotator graphs using simulation results. INTRODUCTION The performance of any multiprocessor system depends main ly on the communication efficiency of the underlying intercon nection topology. Numerous interconnection networks for both general purpose and special purpose applications have been in troduced in the literature. Continuing search for communication efficient symmetric interconnection structures for multiproces sors has led to Cayley graphs as possible interconnection net works [11]. Some examples of Cayley graphs include star graph [1, 2], rotator graph [4], and cycle prefix digraphs [8], binary n-cube and the cube connected cycles. Due to their simplicity' and the fact that the real world communication links (e.g. optical links) are often realized by directed communication links, the directed counterparts of some of the undirected networks have also appeared in the literature, e.g., uni-directional hypercube [3], and uni-directional star graphs [6]. The n-rotator graph and the cycle prefix digraphs are directed by definition. Since these directed Cayley graphs have some interesting properties like easy routing, low diameter and average diameter compared to the star graph, a comparative analysis of these graphs is worthy of study. In this paper, we present some new results for star and rotator graphs. We present a formula for calculating the number of nodes at any distance from the identity permutation, using the cyclic structure of the star graph. The minimum bisection width, an important measure in VLSI models, is obtained for both star and rotator graphs. We show that the rotator graphs of size n! have n-1 node disjoint parallel paths of length at most n + 1 for n > 2. Other fault …