LOAD BALANCING, SELECTION AND SORTING ON THE STAR AND PANCAKE INTERCONNECTION NETWORKS 1
Authors:
K. Qiu a;
S. G. Akl a
| Affiliation: | a Department of Computing and Information Science, Queen's University Kingston, Ontario, Canada |
DOI:
10.1080/10637199408915405
Publication Frequency:
6 issues per year
Published in:
International Journal of Parallel, Emergent and Distributed Systems,
Volume
2,
Issue
1 &
2
1994
, pages 27
- 42
Subjects:
Algorithms & Complexity;
Computer Engineering;
Computer Science (General);
Distributed Network Systems;
Distributed Systems;
Internet & Multimedia;
Parallel Algorithms;
Parallel Systems;
Programming & Programming Languages;
Systems & Computer Architecture;
Formats available:
PDF
(English)
Previously published as:
Parallel Algorithms and Applications
(1063-7192)
until 2005
View Article:
View Article (PDF)
Abstract
We present load balancing, selection, and sorting algorithms for the star and pancake networks. Let Xn be an n-star or n-pancake with p = n! processors with N elements distributed evenly among (he processors such that each processor holds at most [N/p] elements, N ≥ n!. Our selection algorithm selects the κth smallest element on Xn in O((N/P))loglogp + (logN/p)n3logn) time. The sorting algorithm sorts the N elements on Xn in 0((N/p)nlogp + log(N/p)n4log2n) time. This new sorting algorithm is asymptotically faster than the previously fastest known algorithm when N = ω((n log2+δ n)p) = ω((log p)(loglog p)1+δp), i.e., when N = O(p1+ε), for any δ > 0 and ε > 0. A main component of the sorting algoriihm is a procedure for balancing the load among all the processors in each of the two networks. This procedure runs in O(nM + n3logn) lime, where M is the maximum load among all the processors in the network.
|
|
1
*This work is supported by the Natural Sciences and Engineering Research Council of Canada.
|
| Keywords: Interconnection network; star graph; pancake graph; load balancing; parallel algorithm; selection; sorting |
| C.R. CATEGORIES: C.1.2; F.1.2; F.2.2 |
| view references (11) |

Download Citation

CiteULike
Del.icio.us
BibSonomy
Connotea