Parallel Routing and Sorting of the Pancake Network
Parallel Routing and Sorting of the Pancake Network
复制标题
Pancake网络的并行路由和排序
DOI：
10.1007/3-540-54029-6_184
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
S. Akl
中科院分区：
文献类型：
--
作者：
K. Qiu;H. Meijer;S. Akl
煎饼图和星形图于 1986 年提出[1]，作为超立方体拓扑的有吸引力的替代方案，用于互连并行计算机中的处理器。在本文中，我们研究了它们的一些拓扑特性。然后我们提出两个网络的并行路由方案。最后，我们提出了一种在煎饼互连网络上对 K 数字进行排序的有效算法！节点，其中K≥n!，每个节点最多保存N=[K/n!]个数；算法运行时间为O(NlogN(nlogn)+Nn3logn)，当K=n!时为O(n3logn)。
The pancake graph along with the star graph were proposed in 1986 [1] as attractive alternatives to the hypercube topology for interconnecting processors in a parallel computer. In this paper, we study some of their topological properties. We then present parallelrouting schemes for both networks. Finally, we present an efficient algorithm for sortingKnumbers on a pancake interconnection network withn! nodes, whereK≥n!, and each node holds at mostN=[K/n!] numbers;the algorithm runs inO(NlogN(nlogn)+Nn3logn) time, which isO(n3logn) whenK=n!.