Load Balancing for Parallel Computations

Load balancing is an important enabling technology for parallel computing. Its goal is to distribute work evenly to processors (to avoid idle time) while creating decompositions that have low communication costs for applications. This distribution must be done statically as a first step of most parallel computations. For adaptive computations, where processor workloads change as computations proceed, dynamic load balancing may also be needed. Sandia is a leader in load-balancing research. Its pioneering graph-partitioning tool, Chaco, is widely used for static partitioning. Sandia's Zoltan toolkit provides easy-to-use parallel, dynamic load balancing for adaptive applications.

The Zoltan toolkit is used for dynamic load balancing in SIERRA, a finite element framework with adaptive mesh refinement. In this simulation, the finite element mesh is refined around an electron beam scanning a silicon wafer. Zoltan's dynamic load balancing tools generate incremental partitions (indicated by the colored regions) that equally distribute elements to processors while accounting for movement of the refined region. (Picture and movie courtesy of Carter Edwards and Jonathan Rath.) View Video (AVI, Size: 41.9MB, Total Time: 0:06)

Areas of Research:

• Chaco: Graph Partitioning and Static Load Balancing
  (Contact: Bruce A. Hendrickson)
• The NEOS-SRN Optimization Server
  (Contact: Willliam E. Hart)
• Zoltan: Dynamic Load Balancing and Support for Parallel Applications
  (Contact: Karen D. Devine)

Program Contact: Suzanne L. K. Rountree


Newsnotes | Info and Events (internal - SNL only) | Open-Source Software Downloads | Privacy and Security
Sandia National Laboratories Home Page - External or Internal (SNL only)

Maintained by: Bernadette M. Watts
Modified on: May 6, 2008