6. Partitioning and Load Balancing for Emerging Parallel Applications and Architectures
Karen Devine, Erik G. Boman, George Karypis · Society for Industrial and Applied Mathematics eBooks · 2006
An important component of parallel scientific computing is partitioning—the assignment of work to processors. This assignment occurs at the start of a computation (static partitioning). Often, reassignment also is done during a computation (dynamic partitioning) to redistribute work as the computation changes. The goal of partitioning is to assign work to processors in a way that minimizes total solution time. In general, this goal is pursued by equally distributing work to processors (i.e., load balancing) while attempting to minimize interprocessor communication within the simulation. While distinctions can be made between partitioning and load balancing, in this chapter, we use the terms interchangeably. A wealth of partitioning research exists for mesh-based PDE solvers (e.g., finite volume and FEMs) and their sparse linear solvers. Here, graph-based partitioners have become the tools of choice, due to their excellent results for these applications, and also due to the availability of graph-partitioning software [42, 51, 53, 75, 82, 102]. Conceptually simpler geometric methods have proved to be highly effective for particle simulations while providing reasonably good decompositions for mesh-based solvers. Software toolkits containing several different algorithms enable developers to easily compare methods to determine their effectiveness in applications [25, 27, 60]. Prior efforts have focused primarily on partitioning for homogeneous computing systems, where computing power and communication costs are roughly uniform. Wider acceptance of parallel computing has lead to an explosion of new parallel applications. Electronic circuit simulations, linear programming, materials modeling, crash simulations, and data mining are all adopting parallel computing to solve larger problems in less time. Also, the parallel architectures they use have evolved far from uniform arrays of multiprocessors. While homogeneous, dedicated parallel computers can offer the highest performance, their cost often is prohibitive. Instead, parallel computing is done on everything from networks of workstations to clusters of shared-memory processors to grid computers.