Hierarhical Algorithms and Mesh-Based CFD
for High Performance Computing
Scalable Hierarchical Algorithms for Scientific Computing
The fast multipole method (FMM) wasoriginally developed as an O(N)algorithm for solving N-body
10problems. However, it can be used asa direct solver or preconditioner forsolving linear systems that arise from
10
elliptic partial differntial equations thathave a Green’ s function solution
FMM
AMG
such as Poisson’ s equation. TheMUMPS
FMM by itself can only handle far field
1010101010
boundary conditions, but it can be
Number of cores
combined with boundary element methods to handle Dirichlet andNeumann boundary conditions. Comparsions against the algebraic
multigrid code BoomerAMG and sparse direct solver MUMPS, showsthat the FMM preconditioner becomes competitive as the degree ofparallelization increases.
410time [s]

20

−20

1

23

FMM for Molecular Dynamics

The scalability of FMM makes it aninteresting alternative to long range
force calculation methods in classicalmolecular dynamics such as PME.
For problems that have a highcontrast in the distribution of atoms,
such as phase transition calculations,the FMM has an advantage over
FFT-based methods. The challenge
for FMM is to incorporate techniques
to smooth the transition between theshort range direct calcualtion and the long range approximation, which
will allow the FMM to conserve energy over long time integrations.

Performance Model for FMM Communication

The FMM has a complex
actualcommunication
pattern,10
α−β Model
α−β−γ Model
which results from its
β Penaltyhierarchical and global
α,β Penalties
10β,γ Penalties
data dependency.
α,β,γ Penalties
We have developed a10performance model forthe communication inFMM, which accurately
10predicts the23456789 10Level
communication time foreach level in the tree structure. The model considers latency, bandwidth,hops, and multicore penalties in the network. The left 4 figures show thecolormap of the FMM communication for different levels of the treestructure. The right figure shows the communication time at each level
along with the model prediction on Shaheen2 (KAUST).
−1−2Time (s)Fast Multipole Method Preconditioner−3−4Algebraic FMM

The matrix representation of the FMM
algorithm yields algebraic variants of FMM
such as H-matrices and hierarchical semiseperable (HSS) matrices. These methods
can approximate matrix-matrix multiplicationsand LU decompositions in near-linearcomplexity. These algebraic varients of FMM
lie on the opposite end of the Byte/Flopspectrum from the analytical FMM because
they store more to compute less. When thecost of data movement increases faster thanarithmetic opera- tions on future architectures, it is important to consider
the whole spectrum of hierarchical low-rank approximation methods.

Large-scale Mesh-based CFD SimulationsLarge-scale Fluid-structure Interaction Simulation Tsunami Simulation
Direct numericalsimulations ofinteraction between
fluid and solid particles
require huge amount ofcomputationalresources. We havedeveloped a large scale
simulation of a
fluid-particle systemusing coupled a lattice Boltzmann method (LBM) witha discrete element method (DEM) by means of theGPU performance. We demonstrate a direct numericalsimulation of fluidized bed with 562,500 DEM particles
using 128 GPUs. The left figure shows a result of a simulation forfalling leaves using 2.1 billion mesh system and 128 GPUs.

Aerodynamics Simulation using Locally
Mesh-refined Lattice Boltzmann Method

Tsunami impact pressure
analysis for coast areabuildings is conducted witha goal of high accurate
safety estimation. Volumeof Fluid based finite
difference method isapplied to calculate theincompressible two phaseflow. AMG-BiCGSTAB isapplied to solve thepressure Poisson equation with is the most time consuming part of thesimulation. The picture shows building structures are hit by a 10 mheight tsunami. 18 GPUs on TSUBAME2.5 are used to calculate
768x768x128 grids simulation.

Framework-based Weather Prediction code

Numerical weather prediction isone of the major applications inhigh-performance computing
and is accelerated on GPU
supercomputers. Obtaining
high-performance using
thousands of GPUs often needs
skillful programming. We have
implemened the weatherprediction code ASUCA on amulti-GPU platform by using aC++ high-productivity framework. Our framework automatically translates
A lattice Boltzmann method is one of suitable methods for
aerodynamics simulation especially for GPU computing. The area near user-written stencil functions that update grid points and generates botha complex body is locally refined to assign high resolution to calculate GPU and CPU codes. User-written codes are parallelized by MPI. Thesethe turbulent flow in the way of large eddy simulation. An octree-based codes can easily utilize optimizations such as overlapping technique tohide communication overhead by computation.
mesh refinement has been introduced and we optimize theimplementation by using the C++ template for code-expansion.
Reference: T. Shimokawabe, T. Aoki and N. Onodera "High-productivity Framework on
GPU-rich Supercomputers for Operational Weather Prediction Code ASUCA," inTurbulent flows with Reynolds number of more than 100,000 have
Proceedings of the 2014 ACM/IEEE conference on Supercomputing (SC'14) , New Orleans, LA,been studied on a GPU computation.
USA, Nov 2014.

http://www.gsic.titech.ac.jp/sc16