loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
International Parallel and Distributed Processing Symposium (IPDPS'03)
Improved Methods for Divisible Load Distribution on κ-dimensional Meshes Using Pipelined Communications
Nice, France
April 22-April 26
ISBN: 0-7695-1926-1
Keqin Li, State University of New York at New Paltz
We give the closed form solutions to the parallel time and speedup of the classic method for processing divisible loads on linear arrays as functions of {\rm N}, the network size. We propose two methods which employ pipelined communications to distribute divisible loads on linear arrays. We derive the closed form solutions to the parallel time and speedup for both methods and show that the asymptotic speedup of both methods is \beta + 1, where \beta is the ratio of the time for computing a unit load to the time for communicating a unit load. Such performance is even better than that of the known methods on \kappa-dimensional meshes with \kappa gt; 1. The two new algorithms which use pipelined communications are generalized to distribute divisible loads on \kappa-dimensional meshes, and we show that the asymptotic speedup of both algorithms is \kappa \beta + 1, where \kappa \geqslant 1. We also prove that on \kappa-dimensional meshes where \kappa \geqslant 1, as the network size becomes large, the asymptotic speedup of 2\kappa \beta + 1 can be achieved for processing divisible loads by using interior initial processors.
Citation:
Keqin Li, "Improved Methods for Divisible Load Distribution on κ-dimensional Meshes Using Pipelined Communications," ipdps, pp.81b, International Parallel and Distributed Processing Symposium (IPDPS'03), 2003
Usage of this product signifies your acceptance of the Terms of Use.