Abstract: Partitioning and Dynamic Load Balancing for the Numerical Solution of Partial Differential Equations

Partitioning and Dynamic Load Balancing for the Numerical Solution of Partial Differential Equations


James D. Teresco, Karen D. Devine, and Joseph E. Flaherty.
Chapter in Numerical Solution of Partial Differential Equations on Parallel Computers, Are Magnus Bruaset, Petter Bjørstad, Aslak Tveito, editors. © Springer-Verlag, 2005. Also available as Williams College Department of Computer Science Technical Report CS-04-11.

Abstract

In parallel simulations, partitioning and load-balancing algorithms compute the distribution of application data and work to processors. The effectiveness of this distribution greatly influences the performance of a parallel simulation. Decompositions that balance processor loads while keeping the application's communication costs low are preferred. Although a wide variety of partitioning and load-balancing algorithms have been developed, their effectiveness depends on the characteristics of the application using them. In this chapter, we review several partitioning algorithms, along with their strengths and weaknesses for various PDE applications. We also discuss current efforts toward improving partitioning algorithms for future applications and architectures.
Citation (BIBTEX) Entire Chapter (PDF, available on request)