Exploiting repeated matrix block structures for more efficient CFD on modern supercomputers

This paper proposes a novel CFD methodology that enhances performance on modern supercomputers by converting sparse matrix-vector operations into matrix-matrix products to increase arithmetic intensity and by employing an inline mesh-refinement strategy to accelerate convergence, collectively achieving substantial speed-ups in turbulent flow simulations.

The Gist

Imagine you are trying to solve a massive, complex puzzle (a simulation of how air or water flows) on a supercomputer. The computer is incredibly fast, but it keeps getting stuck waiting for the puzzle pieces to arrive.

This is the core problem the paper addresses: Modern supercomputers are so fast at calculating that they often sit idle, waiting for data to be fetched from memory. It's like having a Formula 1 race car driver who is ready to go, but the pit crew is too slow to hand them the tires. The driver spends more time waiting than driving.

Here is how the authors fixed this, explained through simple analogies:

1. The "Waiting Room" Problem (Memory vs. Compute)

In these simulations, the computer performs a specific task over and over: it takes a giant, mostly empty list of numbers (a "sparse matrix") and multiplies it by a list of values (a "vector").

• The Old Way (SpMV): Imagine the computer has to walk to a library, pick up one book, read a page, walk back to its desk, do some math, and then repeat. It spends most of its time walking (moving data), not reading or calculating. This is called being "memory-bound."
• The Bottleneck: The computer's "brain" (processor) is fast, but the "hallway" (memory bandwidth) is narrow. It can't get data fast enough to keep the brain busy.

2. The "Group Trip" Solution (SpMM)

The authors' first major idea is to stop sending the computer on solo trips and start sending it on group trips.

• The Analogy: Instead of sending the computer to the library to get one book for one calculation, they organize multiple calculations at once. They bundle 4, 8, or even 16 different "what-if" scenarios together.
• How it works: The computer walks to the library once, grabs a stack of books (the matrix data), and then sits down to read all 16 books simultaneously.
• The Result: The "walking" time (data transfer) stays the same, but the "reading and calculating" time (computation) goes up massively. The computer is now busy working instead of waiting. In the paper, this is called changing a Sparse Matrix-Vector product into a Sparse Matrix-Matrix product.
• The Payoff: This makes the simulation run up to 50% faster without buying any new hardware. It's like getting a free speed boost just by organizing your work better.

3. The "Training Wheels" Strategy (Mesh Refinement)

The second major idea is about how to start the simulation. Usually, to get a flow (like wind around a wing) to settle down into a steady state, you have to run the simulation for a long time on a very detailed, high-quality map (a "fine mesh"). This takes a long time.

• The Analogy: Imagine you are trying to learn to ride a bike on a difficult, rocky mountain trail. You could spend hours just trying to balance and get moving on the rocks before you even start your real ride.
• The New Strategy: The authors suggest starting on a smooth, flat, easy path (a "coarse mesh") first. You get the bike moving and balanced quickly. Once you are rolling smoothly, you switch to the rocky mountain trail (the "fine mesh") and continue from there.
• The Result: You skip the slow, frustrating "getting started" phase on the difficult terrain. The paper shows this saves a significant amount of "wall-clock time" (real-world time) because the computer can take bigger, faster steps on the easy map before switching to the hard one.

4. Real-World Tests

The authors tested these two tricks on three different scenarios:

1. Turbulent Channel Flow: Simulating water flowing through a pipe.
2. Rayleigh-Bénard Convection: Simulating hot air rising (like a pot of boiling water).
3. Airfoil Simulation: Simulating air flowing over a complex airplane wing (the 30P30N airfoil).

The Results:

• In the Airfoil test (which is an industrial, real-world case), they didn't just speed up one simulation; they ran multiple simulations of the wing at different angles simultaneously using the "Group Trip" method. This allowed them to generate performance curves much faster.
• In the Channel Flow test, combining the "Group Trip" method with the "Training Wheels" (mesh refinement) strategy resulted in speed-ups of over 50%.
• They found that the more complex the math (using more detailed grids), the bigger the speed boost, because the computer had even more work to do once the data arrived.

Summary

The paper doesn't invent a new type of computer or a new law of physics. Instead, it acts like a traffic manager for the supercomputer:

1. Batching: It stops the computer from making one trip at a time and forces it to carry a heavy load of data for multiple calculations at once.
2. Warm-up: It lets the computer practice on an easy version of the problem before tackling the hard, detailed version.

By doing this, they ensure the supercomputer's powerful brain is actually doing math, rather than just waiting for data to arrive. This makes expensive simulations finish much faster, saving time and energy.

Technical Summary

1. Problem Statement

Computational Fluid Dynamics (CFD) simulations, particularly for incompressible Navier-Stokes equations, are increasingly constrained by memory bandwidth rather than computational power. This limitation arises because the core algebraic operations (Sparse Matrix-Vector Products, or SpMV) have low arithmetic intensity (the ratio of floating-point operations to data transferred).

According to the Roofline Model, when arithmetic intensity is low, performance is "memory-bound," meaning the system spends more time waiting for data from memory than performing calculations. This bottleneck prevents modern High-Performance Computing (HPC) systems from reaching their peak theoretical performance. While various sparse matrix formats (e.g., ELLPACK, SELL-C-σ) have been developed to optimize SpMV, they do not fundamentally increase arithmetic intensity enough to overcome the "memory wall."

2. Methodology

The authors propose a two-pronged strategy to shift CFD simulations from a memory-bound regime to a compute-bound regime by increasing arithmetic intensity.

A. SpMV to SpMM Transformation (Exploiting Repeated Block Structures)

Instead of solving for a single flow state at a time, the method runs $m$ simultaneous simulations (either multiple flow states or multiple parameter sets).

• Mechanism: If $m$ independent simulations share the same geometry and boundary conditions, their governing linear operators (Divergence, Gradient, Laplacian, and Poisson matrix) are identical.
• Transformation: The $m$ separate right-hand side (RHS) vectors are stacked into a single dense matrix $X \in \mathbb{R}^{n \times m}$. The standard SpMV operation ($A \cdot x$) is replaced by a Sparse Matrix-Matrix Product (SpMM) ($A \cdot X$).
• Benefit: The sparse matrix $A$ is loaded from memory only once for all $m$ RHS vectors, while the number of floating-point operations increases linearly with $m$. This drastically increases arithmetic intensity, allowing the hardware to utilize its full compute potential.
• Scope: Unlike previous works that applied this only to the Poisson equation solver, this method extends the SpMM transformation to all operators in the CFD loop (convective, diffusive, gradient, divergence, and Laplacian).

B. Inline Mesh-Refinement Strategy

To further reduce wall-clock time, the authors introduce a strategy to accelerate the transition phase (the time required for a flow to reach a statistically steady state before averaging begins).

• Process:
  1. Coarse Phase: The simulation starts on a coarse mesh to rapidly develop the flow until a time $T_D$.
  2. Mapping: The flow field is interpolated from the coarse mesh to the target fine mesh.
  3. Fine Phase: The simulation continues on the fine mesh until the transition time $T_T$ is reached, followed by the averaging phase.
• Rationale: Coarse meshes allow for larger time steps and faster iterations. By developing the flow on a coarse mesh, the total wall-clock time to reach the statistically steady state is significantly reduced without compromising the accuracy of the final averaging phase.

3. Key Contributions

1. Generalization of SpMM: Extending the SpMM approach from just the Poisson equation solver to all sparse operators (gradient, divergence, Laplacian) in the CFD algorithm, maximizing the performance gain across the entire simulation.
2. Inline Mesh Refinement: A novel workflow that combines ensemble averaging with dynamic mesh refinement to minimize the time spent in the non-averaging (transition) phase.
3. Theoretical Bounds: Derivation of upper and lower bounds for speed-up based on the number of right-hand sides ($m$), matrix sparsity (non-zeros per row), and the ratio of averaging time to transition time ($\beta$).
4. Validation Across Scales: Comprehensive testing on both structured (academic) and unstructured (industrial) meshes.

4. Results

The methodology was validated using three test cases on the MareNostrum 5 supercomputer:

• Turbulent Planar Channel Flow ($Re_\tau = 180$):

  • SpMM Kernel: Achieved speed-ups of 3.0x for SpMM operations compared to SpMV.
  • Poisson Solver: Achieved speed-ups of up to 2.0x.
  • Whole Iteration: Achieved speed-ups of 1.3x to 1.5x.
  • Full Simulation: With mesh refinement, the total simulation speed-up reached ~1.55x (55% reduction in wall-clock time) for 4-8 simultaneous flow states, without additional computational resources.
  • Higher-Order Schemes: Tests with denser matrices (13 and 27 non-zeros per row) showed even higher potential speed-ups (up to 4.1x for kernels), suggesting greater benefits for high-order discretization methods.

• Rayleigh-Bénard Convection ($Ra = 10^9$):

  • Validated the method with an additional transport equation (energy).
  • Results showed that while the addition of the energy equation dilutes the SpMM impact slightly, the method remains robust, achieving similar speed-up trends to the channel flow.

• Industrial Case (30P30N Airfoil):

  • Applied to an unstructured mesh with 14 million cells.
  • Demonstrated that the method works effectively on complex, industrial geometries.
  • Achieved iteration speed-ups of up to 80% for multiple parameter studies (e.g., varying angles of attack), significantly outperforming the ensemble averaging cases due to the nature of full-simulation parallelism.

5. Significance and Future Outlook

• Overcoming the Memory Wall: The paper demonstrates a practical, software-level approach to bypass memory bandwidth limitations in CFD by leveraging the "compute-bound" regime through SpMM.
• Cost Efficiency: The method reduces wall-clock time and computational cost without requiring new hardware, making high-fidelity simulations (DNS/LES) more accessible.
• Scalability: The approach is agnostic to the specific discretization method (FVM, FEM, DG) or grid type (structured/unstructured), making it highly versatile for various CFD solvers.
• Future Trends: The authors project that as supercomputer efficiency (FLOPS/Watt) improves slower than raw performance, the relative cost of memory-bound operations will increase. Therefore, techniques that increase arithmetic intensity, like SpMM, will become critical for future CFD applications.

Conclusion: By transforming SpMV to SpMM across all operators and integrating an inline mesh-refinement strategy, the authors have developed a robust framework that significantly accelerates CFD simulations on modern supercomputers, offering speed-ups of up to 50-80% in wall-clock time for complex turbulent flows.