返回Google圖書搜尋

Load Balancing and Selection on the Star and Pancake Interconnection Networks

出版	Queen's University of Kingston. Department of Computing and Information Science, 1992
URL	http://books.google.com.hk/books?id=j5TktgAACAAJ&hl=&source=gbs_api

註釋Abstract: "The star and pancake interconnection networks are two attractive alternatives to the popular hypercube for interconnecting processors in a parallel computer. They possess many desirable properties such as small degree and diameter. In this paper, we present load balancing and selection algorithms on these two networks. For an n-star or n-pancake with p = n! processors, given N elements distributed evenly among the processors with each processor holding at most [formula] elements, N [> or =] n!, our selection algorithm selects the kth smallest element in O((N/p log N/p)n + (log N/p)n3log n) time, while the currently best-known sorting algorithms on the n-star and n-pancake require O((N/p log N/p)n log n + N/p n3log n) time. A main component of the selection algorithm is an algorithm that balances the load among all the processors on the two networks. This algorithm runs in O(nM + n3log n) time, where M is the maximum load among all the processors in the network. The problem of load balancing on the star and pancake networks is interesting and important in its own right, and is discussed in detail."