Load-balancing algorithms for the parallel community climate model

Ian Foster, Brian Toonen1995 · DOI

TL;DR

This paper introduces a novel, programmable load-balancing library and specific algorithms designed to mitigate performance bottlenecks in parallel climate models like PCCM2. By dynamically adjusting computation distribution to processors, these techniques significantly reduce execution time, demonstrating a practical solution for a critical challenge in large-scale scientific computing.

What Problem Does This Paper Address?

Running complex climate models on modern supercomputers involves distributing computations across thousands of processors. A major hurdle is "load imbalance," where some processors are overloaded with work while others are idle. This imbalance often arises from variations in computational demands, particularly in climate models due to factors like solar radiation patterns (which change throughout the day and year) and atmospheric physics calculations. These variations can lead to significant performance degradation, even when the underlying hardware is powerful. The paper specifically targets these imbalances in the Parallel Community Climate Model (PCCM2), aiming to ensure that computational work is evenly distributed across processors to maximize efficiency.

Methods

The core contribution is a general-purpose, programmable load-balancing library. This library allows programmers to define how computation is mapped to processors using a series of "schemas" and "schedules." The library then automatically handles the complex data movement required to transition between these mappings, freeing the programmer from this burden.

The paper details several load-balancing algorithms developed for PCCM2, primarily focusing on addressing the diurnal cycle's impact on solar radiation calculations. Key techniques include:

  • Swapping Algorithms: These algorithms involve exchanging data columns between processors to redistribute computational load. The paper presents two variations, with the second ("swapping2") proving most effective.
  • Movement Algorithm: This approach moves data columns between processors based on estimated computation costs, aiming for a finer-grained adjustment than simple swapping.
  • Recursive Bisection Algorithm: Included for comparison, this is a more traditional load-balancing technique.

The library itself is built around a generic data movement algorithm that efficiently packs data into single messages to minimize communication overhead, crucial for systems with high message startup costs. It handles data reorganization for "input," "output," "input/output," and "state" variables, categorizing them based on their interaction with the physics and dynamics components of the climate model.

Datasets

The primary "dataset" used for evaluation is the Parallel Community Climate Model (PCCM2), a scalable parallel implementation of the Community Climate Model. The experiments were conducted on the Intel Touchstone DELTA supercomputer. The paper does not introduce new benchmark datasets but rather uses the PCCM2 model itself as the testbed for evaluating the load-balancing algorithms.

Key Insights and Ideas

  • Dynamic Load Balancing is Crucial for Climate Models: The paper strongly emphasizes that static load-balancing approaches are insufficient for climate models due to the inherently dynamic nature of atmospheric processes and solar radiation. Dynamic, per-time-step adjustments are necessary.
  • A Programmable Library Simplifies Implementation: The development of a general-purpose, programmable load-balancing library is a significant contribution. It abstracts away the complexities of data movement, making it easier to apply load-balancing techniques to PCCM2 and potentially other climate models.
  • The Diurnal Cycle is a Major Load Imbalance Source: The paper clearly identifies the diurnal cycle, driven by solar radiation, as the most significant source of load imbalance in PCCM2, leading to spatial disparities in computation.
  • Swapping Algorithms Offer a Sweet Spot: While the movement algorithm is theoretically appealing for fine-grained control, the empirical results show that the simpler swapping algorithms (particularly "swapping2") achieve better performance by effectively mitigating the diurnal cycle imbalance with manageable overhead.
  • Overhead vs. Performance Trade-off: The load-balancing algorithms introduce overhead, but the performance gains from reduced imbalance significantly outweigh this cost, leading to net improvements in overall execution time.

Key Results

  • The "swapping2" algorithm was the most effective, reducing the load imbalance caused by the diurnal cycle from 6.8% to 0.8%.
  • This led to a 22.8% reduction in physics execution time on 512 processors.
  • Overall execution time for an average time step was decreased by 4.3%, despite a 3.3% increase in overhead due to the load-balancing system.
  • The recursive bisection algorithm performed poorly, showing only a 1.0% improvement, largely due to higher communication overhead and an inability to handle spatial imbalances effectively.
  • When applied to a more optimized version of PCCM2, the first swapping algorithm showed an overall improvement of 5.9%.

Limitations and Future Work

  • Overhead is Still "Rather High": While performance improved, the authors acknowledge that the overhead associated with the load-balancing code is still a concern.
  • Future Work Directions:
    • Reducing Overhead: Investigating techniques like caching state data or performing load balancing only during radiation physics (less general but moves less data).
  • Integrating with Other Operations: Exploring how to combine data movement with other operations, such as the transposed-based FFT, to potentially integrate input/output data movement into existing transpose operations.
  • Load Balancing in Second Dimension: The current library is limited to one-dimensional load balancing (latitude/longitude). Removing this restriction for two-dimensional balancing is noted as a potential future enhancement.

Summary updated

Abstract

Implementations of climate models on scalable parallel computer systems can suffer from load imbalances resulting from temporal and spatial variations in the amount of computation required for physical parameterizations such as solar radiation and convective adjustment. We have developed specialized techniques for correcting such imbalances. These techniques are incorporated in a general-purpose, programmable load-balancing library that allows the mapping of computation to processors to be specified as a series of maps generated by a programmer-supplied load-balancing module. The communication required to move from one map to another is performed automatically by the library, without programmer intervention. In this paper, we describe the load-balancing problem and the techniques that we have developed to solve it. We also describe specific load-balancing algorithms that we have developed for PCCM2, a scalable parallel implementation of the Community Climate Model, and present experimental results that demonstrate the effectiveness of these algorithms on parallel computers. The load-balancing library developed in this work is available for use in other climate models.
BibTeX
@misc{foster1995load,
  author = {Ian Foster and Brian Toonen},
  title = {{Load-balancing algorithms for the parallel community climate model}},
  year = {1995},
  doi = {10.2172/35373},
}
Figure