Adaptive parallel communications for large-scale computational fluid dynamics [Elektronische Ressource] / Katharina Benkert. Betreuer: Michael Resch

Sujets

• Informatik

Informations

• Publié par: universitat_stuttgart
• Publié le: 01 janvier 2012
• Nombre de lectures: 8
• Langue: English
• Poids de l'ouvrage: 3 Mo

Extrait

AdaptiveParallelCommunicationsforLarge-ScaleComputational
FluidDynamics
A thesis accepted by the Faculty of Energy Technology, Process
Engineering and Biological Engineering of the Universität Stuttgart
in partial fulfilment of the requirements for the degree of
Doctor of Engineering Sciences (Dr. Ing.)
by
KatharinaBenkert
from Augsburg
Main-referee: Prof. Dr. M. Resch
1. Co-referee: Assoc. Prof. Dr. E. Gabriel
2. Co-referee: Prof. Dr. S. Roller
Date of defence: 23.9.2011
Institut für Höchstleistungsrechnen der Universität Stuttgart
2011

G
p
G
"
B

E
O

F
E
–
E
N
O

C

V





H
G

F
I


[
Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie;
detaillierte bibliografische Daten sind im Internet über
abrufbar.
ISBN 978-3-8439-0231-1
© Verlag Dr. Hut, München 2011
Sternstr. 18, 80538 München
Tel.: [phone]
www.dr.hut-verlag.de
Alle Rechte, auch die des auszugsweisen Nachdrucks, der Vervielfältigung und Verbreitung in besonderen Verfahren wie
fotomechanischer Nachdruck, Fotokopie, Mikrokopie, elektronische Datenaufzeichnung einschließlich Speicherung und
Übertragung auf weitere Datenträger sowie Übersetzung in andere Sprachen, behält sich der Autor vor.
1. Auflage 2011
WFSC MJFC FOF FIMFSIB UF OH FO OE FSFO 'PMH FO
FWFOUVFMM GÛS )B UV OH JSHFOE FJOF PE FS 7FSB OUXPSUVOH KVSJTUJTDIF LFJOF ÛCFSOFINFO ¾CFSTFU FS HHG VOE "VU PSF 7FSMB XFSEFO
BVTHF TDI MPTTF WPMMT UÅ OE JH OJD IU 'FIMFS LÖOOFO %FOOPD I FSB SC FJUFU 4PSHGBMU HSP S NJU XVSEFO #VD I EJ TF JO *OGPSNBU JPOFO %JF
IUUQ E OC OC F
TDI F*O GPSNBU JPO EFS%FVU TDI FO / BU JPO BMCJCMJPU FL #JC MJPH SBIn memory of my mother
Ursula "Wu" Benkert
iiiivContents
1 Introduction 1
1.1 High-Performance Computing for Simulations . . . . . . . . . . . 1
1.2 Requirements for HPC . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 The Difficulties and Drawbacks of Code Tuning . . . . . . . . . . 3
1.4 The Impact on Scientific Simulations . . . . . . . . . . . . . . . . . 4
1.5 Automatic performance tuning . . . . . . . . . . . . . . . . . . . . 5
1.6 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 Fundamentals 7
2.1 The governing equations . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Finite Volume Methods . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.1 Discretization in space . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.2 Discr in time . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.3 Boundary conditions . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.4 Higher-order schemes . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.5 Algorithm and Parallelization . . . . . . . . . . . . . . . . . . . . . 15
2.3 Spectral Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.1 Derivation of the spectral equations . . . . . . . . . . . . . . . . . 17
2.3.2 Algorithm and Parallelization . . . . . . . . . . . . . . . . . . . . . 18
2.4 Application Test Cases . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4.1 Euler3D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4.2 The NAS FT Benchmark . . . . . . . . . . . . . . . . . . . . . . . . 19
2.5 HPC Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3 Automatic Performance Tuning 25
3.1 Historic Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.1.1 The Beginnings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.1.2 Formalization efforts . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.1.3 Linear algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.1.4 Solvers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.1.5 Automatic performance tuning for MPI communications . . . . . 29
3.2 Characteristics of automatic tuning systems . . . . . . . . . . . . 30
3.2.1 When to Tune . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.2 How to Tune . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
vContents
3.2.2.1 Heuristic modelling . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2.2.2 Empirical Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2.2.3 Advantages and Disadvantages of Heuristic Modelling and Em-
pirical Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3 The Abstract Data and Communication Library (ADCL) . . . . . 33
3.3.1 Using ADCL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.3.2 Mode of operation . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3.3 Overheads and Countermeasures: A Sophisticated Selection Logic
and Historic Learning . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4 Previously Missing Features and Contributions of This Work . . 42
3.4.1 Area of Application . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.4.2 Outlier Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.4.3 Reliable Performance Measurements . . . . . . . . . . . . . . . . . 44
3.4.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4 Extending the Area of Application of ADCL 47
4.1 Semantics of new ADCL interfaces . . . . . . . . . . . . . . . . . . 47
4.1.1 The ADCL vector-map object . . . . . . . . . . . . . . . . . . . . . 48
4.1.2 Extension of the ADCL Interfaces . . . . . . . . . . . . . . . . . . 49
4.1.3 The new function sets . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.2 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . 53
4.2.1 Integration of ADCL . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.2.2 Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.2.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5 Outlier Analysis and Evaluation of Different Decision Algorithms 59
5.1 Outliers in Performance Data . . . . . . . . . . . . . . . . . . . . . 59
5.2 Techniques for Data Evaluation . . . . . . . . . . . . 61
5.2.1 Heuristic approach . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.2.2 Standard Interquartile Range Method . . . . . . . . . . . . . . . . 63
5.2.3 Cluster Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.2.4 Robust statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.2.5 Complexity estimates . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.3 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . 67
5.3.1 Integration of the ADCL . . . . . . . . . . . . . . . . . . . . . . . . 67
5.3.2 Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
5.3.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.3.3.1 Characterizing the performance of codelets . . . . . . . . . . . . . 71
5.3.3.2 Potential Performance Benefits of ADCL . . . . . . . . . . . . . . 73
5.3.3.3 Statistical Data Analysis . . . . . . . . . . . . . . . . . . . . . . . . 78
5.3.3.4 Performance of ADCL . . . . . . . . . . . . . . . . . . . . . . . . . 85
viContents
5.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6 Timing Techniques for Collective Communications 89
6.1 Timing T to Generate Performance Data . . . . . . . . . 89
6.2 Technical Concept of the ADCL Timer Object . . . . . . . . . . . . 92
6.2.1 Case 1: Optimizing One Request . . . . . . . . . . . . . . . . . . . 92
6.2.2 Case 2: Multiple Requests . . . . . . . . . . . . . . . . 94
6.2.3 Integration of the Timer Object . . . . . . . . . . . . . . . . . . . . 95
6.3 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . 98
6.3.1 Ranking the codelets from best to worst . . . . . . . . . . . . . . . 98
6.3.2 Assessment of the timing techniques . . . . . . . . . . . . . . . . . 101
6.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
7 Conclusions and Outlook 107
Bibliography 111
Glossary 121
viiContents
viiiNomenclature
b Bound for heuristic outlier filtering approach
c Codelet
metac Meta codelet
C Condition for empirical data point to fulfill to be not an outlier
e Internal energy
e (c, d) Minimum error concerning the ranking of two codelets c and dmin
according to their performance
e (c, d) Average error concerning the ranking of two codelets c and d ac-avg
cording to their performance
e (c, d) Maximum error concerning the ranking of two codelets c and dmax
according to their performance
h Dynamic viscosity
E Total energy
g (k) percentage gain/loss when comparing the averaged verificationavg
runtimes of the code version with an ADCL codelet k to those of the
original code without ADCL
I(c) Instability of a codelet c
K Problem class for NAS Parallel Benchmark
L Characteristic linear dimension
m Measurement
m Mean
mˆ Estimated mean
ixmˆ Estimated mean based on the set of filtered empirical data Sf f
imˆ (c)