返回Google圖書搜尋

The Star and Pancake Interconnection Networks

其他書名	Properties and Algorithms
出版	Queen's University of Kingston. Department of Computing and Information Science, 1991
URL	http://books.google.com.hk/books?id=9LqFtgAACAAJ&hl=&source=gbs_api

註釋Abstract: "The star and pancake networks were proposed in 1986 as attractive alternatives to the popular n-cube for interconnecting processors on a parallel computer. In this paper, we present the following results concerning these two interconnection networks: (1) several topological and embedding properties of both networks, in particular a decomposition that partitions a star network of n! nodes into (n-2)! vertex disjoint cycles of length (n-1)n each, and a decomposition that partitions a star or pancake network of n! nodes into (n-1)! vertex disjoint paths of length n each; (2) a number of schemes for routing data on both networks; (3) new broadcasting and prefix sum algorithms, applicable to both networks; and (4) an algorithm for sorting K elements on a pancake interconnection network with n! nodes, where K[> or =]n!, and each node holds at most [formula] elements; the algorithm runs in O(NlogN(nlogn) + Nn3logn) time, which is O(n3logn) when K = n!."