LOAD BALANCING, SELECTION AND SORTING ON THE STAR AND PANCAKE INTERCONNECTION NETWORKS
Titel:
LOAD BALANCING, SELECTION AND SORTING ON THE STAR AND PANCAKE INTERCONNECTION NETWORKS
Auteur:
Qiu, K. Akl, S. G.
Verschenen in:
International journal of parallel, emergent and distributed systems
Paginering:
Jaargang 2 (1994) nr. 1-2 pagina's 27-42
Jaar:
1994
Inhoud:
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.
Tijdschrift beschrijving