LOAD BALANCING, SELECTION AND SORTING ON THE STAR AND PANCAKE INTERCONNECTION NETWORKS∗

∗This work is supported by the Natural Sciences and Engineering Research Council of Canada.

Abstract

We present load balancing, selection, and sorting algorithms for the star and pancake networks. Let X_n 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 X_n in O((N/P))loglogp + (logN/p)n³logn) time. The sorting algorithm sorts the N elements on X_n in 0((N/p)nlogp + log(N/p)n₄log₂n) time. This new sorting algorithm is asymptotically faster than the previously fastest known algorithm when N = ω((n log^2+δ n)p) = ω((log p)(loglog p)^1+δp), i.e., when N = O(p^1+∊), 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 + n³logn) lime, where M is the maximum load among all the processors in the network.

KEY WORDS:

• Interconnection network
• star graph
• pancake graph
• load balancing
• parallel algorithm
• selection
• sorting

C.R. CATEGORIES:

• C.1.2
• F.1.2
• F.2.2

Notes

∗This work is supported by the Natural Sciences and Engineering Research Council of Canada.