January 2007
Return to this issue’s stories

Load Balancing Work Receives Best Paper Award

Researchers from Sandia and Ohio State University were awarded the Best Paper award in the Algorithms track of the 2007 International Parallel and Distributed Processing Symposium (IPDPS). The paper, Dynamic Load Balancing for Adaptive Scientific Computations via Hypergraph Repartitioning, presents a novel algorithm for redistributing data in adaptive parallel simulations. Authors are Erik Boman, Karen Devine, Robert Heaphy, and Lee Ann Fisk Riesen of Sandia, and Umit Catalyurek and Doruk Bozdag of Ohio State University.

As an adaptive simulation’s computational requirements change, the algorithm rebalances processor workloads while keeping interprocessor communication costs and data redistribution costs low. The new method exploits the robust and accurate hypergraph partitioning model to reduce average total communication costs by roughly 20% compared to traditional graph repartitioning methods. The algorithm will be released this winter in the Zoltan Parallel Data Management Toolkit, open-source software available at http://www.cs.sandia.gov/Zoltan

IPDS is a highly competitive international conference (sponsored by IEEE) covering all aspects of parallel computation, including algorithms, applications, architectures, and system software. The award-winning paper was judged best of the 419 submissions to the Algorithms track. The award will be presented March 28, 2007, in Long Beach, CA.