ebooks logo journals logo reference works logo abstract databases logo
bullet  SIGN IN Register | Why Register? | Got a Voucher? alerts   marked lists   shopping cart 

informaworld

HOME   |   SEARCH   |   BROWSE
    Issues List       Latest Issue       Forthcoming Articles       Volume 2 Issue 1 & 2       Subscribe       Article       References       Related articles      
<< firstfirst   < prevprev   Table of contentstoc   next >next   last >>last
Publisher Logo Publication Cover
Search within this journal

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
Formats available: PDF (English)
Previously published as: Parallel Algorithms and Applications (1063-7192) until 2005
Article Requests: Order Reprints : Request Permissions
View Article: View Article (PDF) 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)
Bookmark with:
  • CiteULike
  • Del.icio.us
  • BibSonomy
  • Connotea
  • More bookmarks
Privacy Policy | Terms & Conditions | Accessibility | RSS
FAQs in: English . Français . Español . 中文(简体和繁體)
© 2009 Informa plc