PaperlayerView exact revision on arXiv

Source-linked AI summary

Massively Parallel Algorithms for the Lattice Boltzmann Method on Non-uniform Grids

Florian Schornbaum, Ulrich Rüde

arXiv:1508.07982v2cs.DCcs.CE

TL;DR

High-resolution LBM simulations can make uniform grids costly, while refinement introduces more complex data structures and algorithms. This paper implements parallel algorithms, distributed data structures, and communication routines for non-uniform grids in waLBerla. The approach achieves near-perfect weak scaling at nearly a trillion cells and sub-millisecond strong-scaling time steps in reported benchmarks.

  • Problem

    Uniform-grid LBM resolution increases cell counts and computational cost, while grid refinement requires more complex algorithms and data structures, especially at interfaces between grid sizes.

    Source: §1 · pp. 1–2

  • Method

    The paper implements distributed-memory volume-based grid refinement in waLBerla with distributed data structures, communication routines, and load balancing for massively parallel simulations.

    Source: §1 · p. 2, §6 · p. 28

  • Results

    886 billion cells on 1.835 million threads achieved near-perfect weak scaling and close to a trillion cell updates per second, while strong scaling reached less than one millisecond per time step.

    Source: §5.2 · pp. 26, 28

  • Takeaways & Limitations

    The demonstrated scheme supports large-scale LBM simulations on non-uniform grids, including nearly trillion-cell runs and strong scaling of simulations with several million cells.

    Source: §5.2 · p. 28, §6 · p. 28

    The reported refinement uses static grid structures; dynamic refinement and runtime adaptivity are identified as future work.

    Source: §6 · p. 28

Abstract

from arXiv · show

The lattice Boltzmann method exhibits excellent scalability on current supercomputing systems and has thus increasingly become an alternative method for large-scale non-stationary flow simulations, reaching up to a trillion grid nodes. Additionally, grid refinement can lead to substantial savings in memory and compute time. These saving, however, come at the cost of much more complex data structures and algorithms. In particular, the interface between subdomains with different grid sizes must receive special treatment. In this article, we present parallel algorithms, distributed data structures, and communication routines that are implemented in the software framework waLBerla in order to support large-scale, massively parallel lattice Boltzmann-based simulations on non-uniform grids. Additionally, we evaluate the performance of our approach on two current petascale supercomputers. On an IBM Blue Gene/Q system, the largest weak scaling benchmarks with refined grids are executed with almost two million threads, demonstrating not only near-perfect scalability but also an absolute performance of close to a trillion lattice Boltzmann cell updates per second. On an Intel-based system, the strong scaling of a simulation with refined grids and a total of more than 8.5 million cells is demonstrated to reach a performance of less than one millisecond per time step. This enables simulations with complex, non-uniform grids and four million time steps per hour compute time.

1. Introduction.

Uniform grids can make high-resolution three-dimensional LBM simulations costly, while refinement concentrates resolution where accuracy is needed. The paper presents a parallel, volume-based refinement approach in waLBerla and reports large-scale performance on petascale systems.

1. Introduction.

  • Uniform three-dimensional grids can require rapidly increasing cell counts and computational cost as spatial and temporal resolution rise.Grid refinement focuses high resolution on regions that need greater accuracy.Source: §1 · p. 1
  • Existing volume-based parallel refinement approaches use tree-based partitioning, while the authors report that several popular LBM codes lack demonstrated large-scale simulations on non-uniform grids.The passage names MUSUBI's linearized octree and Peano's spacetree as examples.Source: §1 · p. 2
  • The waLBerla implementation combines distributed-memory parallelization of a volume-based refinement algorithm with an interpolation scheme, targeting massively parallel systems.It also proposes scaling the two TRT relaxation parameters across grid resolutions.Source: §1 · p. 2
  • 886 billion cells ran with almost two million threads, with near-perfect weak scaling and close to a trillion cell updates per second.The authors describe this as the largest LBM computation on non-uniform grids to date.Source: §1 · p. 2

2. The lattice Boltzmann method.

The section outlines LBM's local collision and neighbor-based streaming steps, then describes force and boundary handling and grid-refinement scaling. The refinement scheme uses a 2:1 level balance and adjusts relaxation parameters to maintain the stated physical quantities across levels.

2. The lattice Boltzmann method.

  • LBM separates local collision from streaming, which exchanges particle distribution functions only between neighboring cells.The paper focuses on the SRT and TRT collision models.Source: §2 · p. 3

2.1. External forces.

  • For constant acceleration, the force treatment modifies the independently calculated fluid velocity, while leaving the velocity used for equilibrium evaluation unmodified.The force model also adapts the calculation of velocity terms in the equilibrium distribution as needed.Source: §2.1 · p. 4

2.2. Boundary treatment.

  • Boundary PDFs are stored in boundary cells after collision and before streaming, so neighboring fluid cells can pull them without special boundary operations during streaming.The authors state that collision and streaming algorithms can remain unchanged near boundaries.Source: §2.2 · p. 5

2.3. Grid refinement.

  • Grid refinement assumes neighboring levels differ by at most one and uses acoustic scaling, requiring twice as many time steps on level L+1 as on level L.The time step is Δt_L = Δt_0/2^L; the relaxation parameters are scaled to keep kinematic viscosity constant, with Λ_eo held constant to scale λ_o.Source: §2.3 · pp. 5–6

3. Parallelization concept and realization.

The section extends waLBerla’s block-based parallelization to non-uniform grids through a distributed forest-of-octrees structure, a two-stage initialization process, and communication patterns for blocks at different grid levels.

3.1. The waLBerla simulation framework.

  • The framework supports OpenMP, MPI, and hybrid execution, while its extensible components cover domain partitioning, I/O, parallelization, and program flow.waLBerla also uses fine-tuned, vectorized compute kernels.Source: §3.1 · p. 6

3.2. Forest of octrees domain partitioning.

  • The domain is subdivided into eight smaller blocks in 3D, with 2:1-balanced octrees matching the refinement scheme and allowing most block-based algorithms to be reused.Only algorithms closely tied to block arrangement, including parts of the communication layer, require a separate implementation.Source: §3.2 · pp. 7–8
  • The distributed forest stores block IDs and neighboring block/process information, so each process needs knowledge only of local blocks and their neighbors.Per-process memory therefore depends on its assigned blocks, not the global number of blocks.Source: §3.2 · p. 8

3.3. Two-stage initialization.

  • Initialization begins with uniform blocks, removes unneeded regions, applies user-marked refinement and 2:1 balancing, then assigns blocks to processes.The resulting partition can be saved and loaded for a later simulation run.Source: §3.3 · p. 9, Figure 5 · p. 9
  • Load balancing uses per-block memory and workload estimates before allocating the fully resolved grid, enabling partitioning of grids with trillions of cells.Space-filling curves and METIS are available; the hierarchical approach separates domain partitioning from filling blocks with grid data.Source: §3.3 · pp. 9–10

3.4. Inter-block communication.

  • For same-level block communication, neighboring blocks synchronize through ghost layers, exchanging only PDF values that stream into the neighboring block.For D3Q19, the passage reports five PDF values per face cell and one per edge cell, reducing communicated data by an average factor of four.Source: §3.4 · p. 10
  • Refined grids require three communication patterns: same-size exchange, fine-to-coarse transfer, and coarse-to-fine transfer.In 3D, each block contains a grid of equal size, so resolution transitions occur at block boundaries.Source: Figure 3 · p. 7, §3.4 · p. 11, Figure 7 · p. 11

4. The LBM on non-uniform grids.

This section describes a recursive LBM implementation for non-uniform grids, including data exchange between blocks at equal and different resolutions. It also explains level-by-level load balancing that accounts for block weights to minimize process idle time.

4. The LBM on non-uniform grids.

  • The octree block partition assigns equal-sized grids within each block, aligning interfaces between different resolutions with block boundaries.The time-stepping algorithm transfers coarse-cell content into fine-grid ghost layers, advances fine cells, then merges selected fine-grid values back to the coarse grid.Source: §4 · pp. 12–13

4.1. Implementation.

  • The recursive procedure advances one coarse time step, using level-to-level communication and a fused stream-collide operation on the finest grid to reduce memory transfers.The procedure also uses asynchronous communication to overlap data transfer with work on finer blocks, and mass- and momentum-conserving interpolation for coarse-to-fine values [13].Source: §4.1 · pp. 13–15

4.2. Communication between blocks on the same level.

  • The implementation adapts same-level communication near coarser neighbors, while generally exchanging no more than two cell layers and usually only one layer of relevant PDF values.Near a larger coarser neighbor, the two innermost ghost layers must remain valid; face transfers use two layers near edges but only one layer in the interior.Source: §4.2 · pp. 16–17

4.3. Coarse-to-fine communication.

  • Coarse-to-fine communication sends two coarse-grid cell layers and distributes their PDF values across four fine-grid ghost layers using mass- and momentum-conserving interpolation.All PDF values are transferred when boundary conditions operate on the fine-grid ghost layers; fluid-only transitions can instead use one coarse cell and only values streaming into the fine block.Source: §4.3 · p. 17

4.4. Fine-to-coarse communication.

  • Fine-to-coarse communication aggregates corresponding fine-cell values while packing, then copies them from fine ghost layers into the coarse-grid interior.Only values streaming into the coarse block are sent; some values need not be transferred because a neighboring fine block’s communication already includes them.Source: §4.4 · p. 18

4.5. Load balancing.

  • Load balancing must account for interactions between blocks at different refinement levels, since those blocks cannot be processed independently at communication stages.The stated objective is to distribute work across processes without leaving any process idle; block weights that reflect refinement level alone do not fully address this constraint.Source: §4.5 · pp. 19–20
  • Level-wise distribution across all processes accounts for block weights and minimizes idle time, using Morton or Hilbert space-filling curves or METIS.Blocks on the same level can have different weights because their fluid-to-obstacle cell ratios differ. The need for level-wise load balancing was noted in, but had not previously been implemented.Source: §4.5 · p. 20

5. Validation and benchmarks.

The authors validate their parallel non-uniform-grid LBM approach with plane and pipe Poiseuille flows, then benchmark it on SuperMUC and JUQUEEN. The benchmarks show near-perfect weak scaling, close to a trillion cell updates per second, and strong scaling below one millisecond per time step.

5.1. Poiseuille flow.

  • For plane Poiseuille flow, grid refinement at several plate and interior locations preserved convergence to the analytical solution, with L∞ error approaching machine accuracy.The simulations used TRT and fixed Λeo across grid levels; the plane and pipe setups used different boundary arrangements.Source: §5 · p. 20, §5.1 · pp. 21–22
  • For pipe flow, wall refinement produced accuracy comparable to uniform fine grids, while refining only the center had no impact; accuracy was mainly determined by resolution at the fluid-wall interface.The circular boundary was approximated by a staircase with first-order mass-conserving bounce-back, so errors decreased linearly with resolution.Source: §5.1 · pp. 22–23, Figure 17 · p. 23, Table 1 · p. 23

5.2. Performance evaluation.

  • On SuperMUC, 32,768 cores processed up to 110 billion cells at 154,599 MLUPS/sec, with strong-scaling throughput reaching four million time steps per hour.The benchmarks show almost perfect weak scaling; four-thread hybrid runs were slightly faster than MPI-only and eight-thread runs.Source: §5.2 · pp. 25–26, Figure 18 · p. 25
  • Compared with uniform-grid LBM, the non-uniform scheme lost a factor of 2 to 2.5 in MLUPS/sec, but local refinement reduced overall workload and memory requirements.The cited overheads include interpolation, additional communication, and inability to use fused stream-collide kernels.Source: §5.2 · pp. 26–27
  • The vocal-fold example used five refinement levels for 105,676,800 cells and achieved close to 100 time steps per second on 4,300 SuperMUC processes.Compared with refining the entire domain to the finest level, it required 55.2 times less memory and generated 98.2 times less workload.Source: §5.2 · p. 28, Figure 20 · p. 28
  • 886 billion cells and close to a trillion cell updates per second were achieved on JUQUEEN with almost two million threads; strong scaling reached less than one millisecond per time step.The conclusion identifies the simulation as the largest reported LBM computation on non-uniform grids to that date.Source: §5.2 · pp. 26, 28, Figure 19 · p. 27

6. Conclusion and outlook.

The paper presents waLBerla building blocks for massively parallel LBM simulations on non-uniform grids, including distributed data structures, communication, load balancing, and relaxation-parameter scaling. Dynamic refinement and runtime adaptivity remain future work.

6. Conclusion and outlook.

  • Octree-based domain partitioning into blocks provides the foundation for scalability on current supercomputers.The paper also presents parallelization for grid refinement, asynchronous communication requiring minimal communication, and level-wise load balancing suited to the algorithms.Source: §6 · p. 28
  • The paper proposes scaling the two relaxation parameters of the two-relaxation-time collision model across grid resolutions.Source: §6 · p. 28
  • Dynamic grid refinement and runtime adaptivity are future work; they require runtime block splitting, merging, and exchange between processes, plus dynamic load balancing.Source: §6 · p. 28
  • The algorithms and benchmarks are implemented in waLBerla and available as part of the software framework.Researchers are encouraged to contact the framework authors for code access.Source: §6 · p. 29
Loading 1508.07982v2…