Partitioning and Dynamic Load Balancing for Petascale Applications Speaker: Karen Devine, Sandia National Laboratories Authors: Karen Devine, Erik Boman and Lee Ann Riesen, Sandia National Laboratories Umit Catalyurek and Doruk Bozdag, Ohio State University

Effective data partitioning and dynamic load balancing are critical components of petascale applications. Partitioning and load balancing assign data and work to processors in a manner that attempts to minimize both processor idle time and application communication costs and, thus, reduce applications' total execution time. For applications with changing data locality or work loads (e.g., particle-based or adaptive mesh refinement methods), dynamic load-balancing algorithms are needed to redistribute data to reflect current computational conditions. In addition to balancing work loads and controlling communication costs, dynamic algorithms must consider the cost of moving data from the old distribution to the new one. In this talk, we discuss several types of partitioning algorithms, including geometric, hypergraph-based, and graph-based methods.

We examine their effectiveness in both static and dynamic applications. And we demonstrate their scalability and performance on data from several SciDAC applications. This work is ongoing research through the SciDAC CSCAPES Institute and ITAPS Center.