loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Papers
An Algorithm for Geometric Load Balancing with Two Constraints
Santa Fe, New Mexico
April 26-April 30
ISBN: 0-7695-2132-0
Jiyoun Kim, University of Michigan
Marios Papaefthymiou, University of Michigan
Athar Tayyab, IBM Microelectronics
This paper describes an algorithm for partitioning 2-weighted geometric graphs, so that each of the two weights is evenly distributed among all partitions and cutsize is minimal. This algorithm is applicable to load balancing problems in parallel computing, including scientific computation or circuit optimization, in which computational load depends on multiple factors, and geometric proximity needs to be preserved. We first show that for two continuous weight distributions, there always exists an L-shape separator that divides the two weights exactly. Based on this fact, we then give a practical and efficient heuristic for 2p-way partitioning. Our heuristic relies on recursive bipartitioning and runs in O(nlgn+m2p) time, where n is the number of vertices and m is the number of rows in the graph. In experiments with geometric graphs obtained from placed benchmark VLSI circuits, our heuristic generates balanced partitions with imbalance no greater than 2%, very short runtimes, and good cutsizes. For example, given a geometric graph with n > 100,000, our heuristic computes a 32-way partitioning with 0.46% maximum imbalance within 0.5 second.
Citation:
Jiyoun Kim, Marios Papaefthymiou, Athar Tayyab, "An Algorithm for Geometric Load Balancing with Two Constraints," ipdps, vol. 1, pp.40b, 18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Papers, 2004
Usage of this product signifies your acceptance of the Terms of Use.