Scientific Computing in TSUBAMEScalable Algorithms and Large-scale Simulations
Scalable Hierarchical Algorithms for Scientific Computing
The fast multipole method (FMM) was
originally 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
elliptic partial differential equations
10
that
have
aGreen’sfunctionsolutionFMM
such as Poisson’ s equation. TheAMG
MUMPS
FMM by itself can only handle far field
1010101010 boundary conditions, but it can beNumber of cores
combined with boundary element methods to handle Dirichlet andNeumann boundary conditions. Comparisons 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

23Performance 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 thecolor map 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−4Compressing Convolutional Neural Networks Algebraic FMM

The matrix representation of the FMM
Hierarchical low-rankalgorithm yields algebraic variants of FMM
approximations cansuch as H-matrices and hierarchical seminaturally be use in
separable (HSS) matrices. These methods
machine learning for
can approximate matrix-matrix multiplications
support vectorand LU decompositions in near-linear
machines with kernel
complexity. These algebraic variants of FMM
methods. In this worklie on the opposite end of the Byte/Flop
we take it one step
spectrum from the analytical FMM because
further and use it to compress deep convolutional neural networks. The
they store more to compute less. When thesame principle as in FMM and H-matrices can be use to compress bothcost of data movement increases faster than
the weights and image data. In doing so, we are able to prune thenetwork to its optimal size without any loss of accuracy. This results in arithmetic operations on future architectures, it is important to consider
the whole spectrum of hierarchical low-rank approximation methods.
huge saving in both the memory consumption and time-to-solution.

Large-scale Mesh-based and Particle-based Simulations
Gas/Liquid-Solid Two-Phase Flow Simulation

Large-scale Granular Simulation

Direct interactions
between fluid andsolid particles arecomputed on themesh to study
gas/liquid-solid
two-phase flows
accurately for highReynolds number
flows with complex
shaped particles. We have carriedout a large-scale simulation of a
fluid-particle system coupled lattice Boltzmann method (LBM) withdiscrete element method (DEM). A direct numerical simulation offluidized bed with 562,500 DEM particles using 128 GPUs is shown in
the right figure. The left figure demonstrates a result of the simulation
for falling leaves using 2.1 billion mesh and 128 GPUs.

Discrete element method(DEM) is often used tosimulate granular
dynamics and its simple
algorithm with the contact
interaction is suitable for
GPU computing.
However so many
particles are included andthe particle distributions
are changing in time andspace. A dynamic domain
decomposition has to be introduced for multiple-node computing. In a
bunker shot, the sand wedge does not hit to the golf ball directly andtransferring the force through the sand to the ball in order to reduce theimpact. In this simulation, 16.7 millions of DEM particles are used torepresent the dynamics of the sands with 256 GPUs.

Weak-Compressible Flow Computations for
Gas-Liquid Two-Phase Flows

Dynamic Load Balancing using A Space-fillingCurve

A fully explicit scheme forincompressible gas-liquid two-phaseflows without solving the Poisson
equation has been developed. The
fractional-step method and the
directional splitting method areincorporated to simplify thecompressible Navior-Stokes
equation to apply the method ofcharacteristics and semi-Lagrangian
method for efficient computations.
The time step is determined by thesound speeds from the ideal-gas equation of state. The gas-fluid
interface is captured by phase-field model and Allen-Cahn equations toreduce the volume oscillation. The results are in good agreement withthose of semi-implicit incompressible flow computations.

For large-scaleparticle-based
simulation and Adaptive
Mesh Refinement(AMR), it is a criticalissue to achieve
computational loadbalance and equal
memory usage on
multiple computenodes. A domain
partitioning in terms of a space-filling curve(SFC) is one of promisingcandidates and it is recognized that a 1-dimensional mapping of
3-dimensional space by cutting the equal length. Due to low cost of
SFC domain partitioning, it is suitable for frequent re-partitioning in thesimulations of unsteady phenomena.

A Hilbert Curve

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