Ayesha Afzal<ayesha.afzal@fau.de>, Georg Hager (advisor), Gerhard Wellein (advisor)

Department of Computer Science | Erlangen National High Performance Computing Center| Friedrich-Alexander University Erlangen-Nürnberg, Germany

DOI: 10.1007/978-3030-78713-4_19

ranks
𝑣! []
s𝜎. 𝜅(𝑑)=𝑇"#$! + 𝑇"#$$

𝐀
0:

=

Pro
05

𝐁:

15

𝑑 = 3,12,3, 𝜎 = 1

DOI:10.1109/CLUST
ER.2019.8890995

DOI: 10.1007/978-3030-78713-4_19

Time [s]Time [s] 2 x 6 x 10 process grid𝑑 = 12, 𝜎 = 1

𝑑 = 12, 𝜎 = 2 (jacobi)

DOI:10.13140/RG.2.2.28259.50726

Afzal et al.

Afzal et al.

De-syncof processes
causes automaticcommunication overlap
and bottleneck evasione
DOI:10.13140/RG.2.2.28259.50726

2025

arXiv: 2011.00243[cs.DC]

0Time step 50

Process-scalable
code

Sloweridle waves,strong bottleneck
and variability help in
amplifying the de-sync

Time step 50

Time step 50
𝐂(: )𝐀 : = 𝐁 : + 𝐜𝐨𝐬()𝐃(: )attern Formation

Variability
is not all
detrimental

De-sync wavefront

De-sync wavefront

Sync wavefront

Rank

95407

Rank7. PHYSICAL OSCILLATOR MODEL

4080

Chebychev Filter Diagonalization

120128x64x64 size, 6.7 GB data set, nonblocking MPI routines, 16 Emmy sockets

5540

Rank

Rank
Rank

01010159

Wall-clock time [s]Time step
MPI+OpenMP

odes

𝑇!"#$ 𝑇!"## 𝑇!"#$ 𝑇!"##

DOI: 10.1007/978-3030-50743-5_20

MPI

visulizationLattice Boltzmann Fluid Solver(c) Timeline
MPI- parallelized

matrix Topi-128-64-64
Time step
cution, niter = 5) running. (a) Performance scaling= 32, (b) scaling up to 10
ads per process, (c) timeWall-clock time [s]De-sync and speed-up increase with time
ybrid execution for nb = 2
ActualModel
100
99t=1 120t = 20t100= 100

60t = 60t =1000
1 000

500t=500

10000
t = 10 000

direct-neighbour
communicationm'

Motivation
Unknown
analogy𝜃!̇ =𝜔!
Inversetime step

80
80

Rank
Rank

𝜃'Cluster and codecharacterization toolEnd-usertool&

http://tiny.cc/IRese
archPoster-ISC21t = 5000
5 000

V'&m%

Parallel MPI
processes

Costeffective

302. lattice cell, 8 GB data set, nonblocking MPI routines, 10 Emmy sockets

Actual measurement
Compositional modelAnalogy

V%(m$Wall-clock time [s]Afzal et al.

= 32

We propose
A non-linear physical coupled phase oscillators model
The phenomenology of distributed applications suggests a physicalinterpretation of individual processes as a set of coupled oscillators
whose inherent frequencies are in^luenced by coupling potential
V&%m&

DOI:10.1109/CLUST
ER.2019.8890995

80120

10T

1515

8 10

Afzal et al.

1T0

Across context,
if de-sync isdesirable, apply
optimization techniques
amplifying the de-sync

𝐀 : = 𝐁 : + 𝐬 ∗ 𝐂(: )06. USABILITYAND GENERALIZATION

159

6060𝑣"+ 𝜁! 𝑡 +* 𝑇!# 𝑉!# (𝜃(𝑡, 𝜏))𝑁"Noise#$%Interaction term

4040

𝑁/ ∶ System size;
1 155

1 127.1

1 127

1 126.9

1 126.8

577.5

563.9

563.8

563.7

563.6

115.5

113.1

113

112.9

112.8

57.7

56.6

56.5

56.4

56.3

11.5

11.4

11.3

11.2

7

6.9

6.8

6.7

2.5

2.4

2.3

2.2

0.4

0.3

0.2

00.1

20200

Time [s]Fig. 2: Measured LBM irregular structure in comparison with expected model regularity. The plot shows that the time steps
with more irregularity (iterations in between and at the end of the results) manifest maximum percentage variation towards
better performance (2.25% at time step t = 500 and 2.42% at time step t = 10 000).
LBM time steps t, from t = 1 to t = 10, 000, where the locationof the time step along the wall-clock time axis is marked oneach process (red markers). For reference, we also show the
expected positions according to the simple nonoverlapping
execution-communication model (1). While the deviation fromthe model and the variation across processes is still small
after 20 time steps (< 0.1 s), a global structure has emerged
at t = 500 with a fundamental “wavelength” equal to the sizeof the system (100 processes) and an amplitude of 0.3 wallclock seconds. This pattern is not static but shifts and changes

ic values. The optimistic

80

96

96

120

112

144

128

4060

487248

80

96

80

64

Wall-clock time [s]Idle wave decay driven by structured
variability owing to system topology

20 %

25 %

30
Time step

30

0102030
4050
60
7080
90
100
119

29394930

Idle wave decay with increasingintensity of variability
à no runtime penalty at 25 %Wall-clock time [s]Idle waves can propagate or
distort according to variability
caused by collective algorithm

5. BANDWIDTH SHARING MODEL FOR BACKTO-BACK DIFFERENT KERNELS TO PREDICTIF DE-SYNC IS AMPLIFIED OR DAMPEDWe show how such idle waves interact and (partially)cancel each other, proving that a linear wave equation isinappropriate to describe the phenomenon.
• We give an analytic expression for the speed of an idle
wave in a noise-free homogeneous system under corebound computational load, i.e., code whose performanceis purely limited by in-core resources. The formula
takes into account execution time, communication time,communication topology, and communication mode (eagervs. rendezvous).

𝑇01 : Communication topology

𝑉01 𝜃 : Coupling potential re^lects bottleneck structure
𝜁0 𝑡 : Local noise;

DDOT2-Allreduceoverlap

Permuted Rank

N=24 (4 sockets)

71

64

72

symGS-DDOT2
overlap

Single socket SuperMUC-NG @2.3 GHz, non-temporal stores,
bi-dir, 1024 B, close chain, distance-1 communication

4748

DOI: 10.1007/978-3030-50743-5_20

Cores per socket, N

23324819

One MPI wait per dir

13 13.4 13.8 2.2 14.6. 15

1.72 1.88

1624959

KEY-TAKEAWAYS:) )(𝐂:)((𝐨𝐬 𝐃odcelba lacsssce

1000

Rank

Memory bandwidth [GB/s]

50

Variability = 0 %1.6 1.8 2 2.2 2.4

Msg [KB]

Rank

1.56

Processes required for full memory bandwidth𝐜

One MPI wait only

Rank
One MPI wait only

4. DE-SYNC WAVEFRONT FORMATION FOR
ACROSS-PROCESSES BOTTLENECK+Afzal et al.

Time [s]0102030405060708090100119

Nonlinearinteraction ofidle waves

Hawk

Binomial

01020
30
405060
7080
90
100
119

Time step

DOI:10.13140/RG.2.2.28259.50726

SuperMUC-NG

Topology aware Shumilin’s

Idle period on rank 5
propagates depending on
communication protocol,
concurrency and topology

200Default MPI_Reduce

Research vision“White-box” -irst-principle performancemodelling of distributed-memory
applications that incorporates thein-luence of variability

010
2030
40
50
60
70
80
90
100
119

85
95

Rank

Model forruntime
driven byvariability

Rendezvous, 𝜎 = 2100Bi-dir(LBM)

515253545556575

Emmy

0102030405060708090100119

Rank

Close-chain(dense MVM)

Rank

Model forModel forruntime ofruntime ofcomputation
communication(Roofline, ECM (Hockney, LogGP oror other model)
other model)

geEd

Tr
ailin
gE
dg
e

Uni-dir, eager,
open-chain, d, 𝜎 = 1
Model forruntime of
distributedmemory
parallelapplications

DOI:10.1109/CLUST
ER.2019.8890995

ginad
Le

ProblemVariability can bring
acceleration, speed down, or neither

3. VARIABILITY-DRIVEN IDLE WAVE
DECAY IN SCALABLE PROCESSES

Rank

2. COMMUNICATION-DEPENDENT IDLE WAVE Afzal et al.
PROPAGATION VELOCITY 𝒗𝒑 (NO VARIABILITY)

Rank

1. MOTIVATION AND CHALLENGES

Wall-clock time [s]HPCG benchmark on Broadwell
Possible de-sync scenarios
1. Multi-phase applications
2. Spatial multitasking in GPUs
3. Task-parallel programs

8. OUTLOOK AND CONCLUSION

Addressing theanalysis andsimulation challengesof the dynamics ofparallel computing

Exploration ofvarious aspects andapplication scenariosof “white-box”
modelling
approach
Encompassing theperformance-limitingbottlenecks, analysis
guides appropriate codechanges and insight into thehardware-software interaction

Connecting parallel
computing dynamics
to the physical world,
oscillator model canserve as a high-levelcluster characterization tool

𝜏: Interaction noise•

POSTERARTIFACT
http://tiny.cc/PosterArtifacts