The Moving Target (Static Load Balancing)

We have secured our I/O at scale, but our CPUs are still out of sync.

In our baseline, we simply divided the grid evenly: int Ny_loc = NY_GLOBAL / size;. For the 800x800 grid on 16 processes every rank received 50 rows. But we can assume that the exponentially-scaling Arrhenius chemistry in the Forest is more expensive than the linear chemistry in the Brush, and, most importantly, it is being divided into many sub-steps for numerical stability.

To fix this imbalance, we will use time-integrated Static Load Balancing in an attempt to partition work by computational cost rather than physical space in fire_balanced.cpp. During initialization, every processor independently assigns a “weight” to each global row based on two factors: the substrate cost (heavy for Forest, very small for Brush) and a base weight to prevent overload on idle edge processors. We assign substrate cost approximately within a radius of expected fire propagation during the 2000 steps (hence “time-integrated”), while leaving rows that never burn with base weight only:

const double base_weight = 5.0; // We don't want any rank to get too many rows
const double forest_amplifier = 13.0; // Forest computational factor when it burns
const double brush_amplifier = 1.0; // Brush factor when it burns
const double rmax_fire = 260.0; // Measure of how far fire propagates from the grid center (radius)
const double rmax_brush = 340.0; // Measure of how far fire propagates from the grid center (radius)

double total_weight = 0.0;
std::vector<double> weights(NY_GLOBAL, base_weight);
double center = NY_GLOBAL / 2.0;

for (int row = 0; row < NY_GLOBAL; ++row){
    double amplitude = 0.0;
    if (row <= center && (center - row) < rmax_fire){
        amplitude = forest_amplifier;
    } else if (row > center && (row - center) < rmax_brush) {
        amplitude = brush_amplifier;
    }
    weights[row] += amplitude;
    total_weight += weights[row];
}

The algorithm then iterates through the grid, keeping a running total of these weights. Whenever the cumulative sum crosses an equal-share threshold (total grid weight divided by the number of MPI ranks), the threshold-breaking row is assigned to the next processor:

// Based on weights, calculate local number of rank rows and offset
int my_nrows = 0;
int my_offset = 0;
int irank = 0;
double curr_weight = 0.0;
double weight_per_rank = total_weight / size;
for (int row = 0; row < NY_GLOBAL; ++row){
    curr_weight += weights[row];
    if (curr_weight >= (irank + 1)*weight_per_rank && irank < size - 1){
        irank++;
        if (irank == rank) my_offset = row;
    }
    if (irank == rank) my_nrows++;
}

This creates a contiguous, synchronized domain decomposition where ranks handling Forest fire are assigned a minimal numbers of rows, while ranks handling Brush fire, and even more so idle peripheral ranks, process much more rows.

Let’s profile this weighted version with Linaro MAP.

Performance Improvement

We observe that our static load-balancing was a success - by simply adjusting the array boundaries, both the application wall time and MPI time decreased significantly:

Linaro MAP profiling summary
============================
Profiling time:      12 seconds (between MPI init and finalize)
Peak process memory: 79343616 B (~75.7 MiB)

Compute:              27.1%     (3.1s) |==|
MPI:                  59.3%     (6.7s) |=====|
I/O:                  13.6%     (1.6s) ||
  (based on time on the main thread)

If we look at the new Time-wise communication matrix, we see a much more symmetric distribution of row colors - central (larger) part of the grid is green, while top and bottom rows are a spectrum of yellow:

../../_images/map_mpi_comm_matrix_fire_balanced_time.png

Fig. 31 Linaro MAP Time-wise communication matrix for the load-balanced version of the wildfire application run using an 800x800 grid for 2000 steps on 16 processes.

The matrix is also more “shallow” - difference between maximum and minimum time spent in different ranks is much smaller (and of course the absolute values of the maximum time spent per rank is smaller too) than previously.

Remaining Imbalance

While alleviated to a degree, slight imbalance however remains. This is due to the fact that our simulation is very dynamic, while our load balancing is static (even though time-integrated). Fire spreads unevenly, with Brush burning faster and wider, and burning out quicker in the center than the forest (due to having less “fuel”). We had to tune the weights and fire radius parameters by hand to obtain the best result for the given propagation time for the purposes of this demo.

To achieve a perfectly flat, zero wait time MPI profile for this wildfire application, a developer would have to implement dynamic load balancing. The application would need to regularly measure the timing of each rank and physically migrate rows of data across the network from slow processors to fast processors on the fly.

In modern production codes, rather than writing this complex and error-prone migration logic by hand, HPC engineers frequently rely on advanced libraries such as Zoltan, parallel programming systems such as Charm++ or AMR (Adaptive Mesh Refinement) frameworks to handle the dynamic re-balancing for them.