Cover Page
The handle http://hdl.handle.net/1887/28464 holds various files of this Leiden University
dissertation
Author: Jeroen Bédorf
Title: The gravitational billion body problem / Het miljard deeltjes probleem
Issue Date: 2014-09-02
The Gravitational
Billion Body Problem
Het miljard deeltjes probleem
Proefschrift
ter verkrijging van
de graad van Doctor aan de Universiteit Leiden,
op gezag van Rector Magnificus prof. mr. C.J.J.M. Stolker,
volgens besluit van het College voor Promoties
te verdedigen op dinsdag 2 september 2014
klokke 16:15 uur
door
Jeroen Bédorf
geboren te Alkmaar
in 1984
ii
Promotiecommissie
Promotor:
Prof. dr. Simon Portegies Zwart
Overige leden:
Prof. dr. Steve L.W. McMillan
Prof. dr. Henk Sips
Prof. dr. Joost Batenburg
(Drexel University)
(Technische Universiteit Delft)
(Centrum Wiskunde & Informatica /
Universiteit Leiden)
Prof. dr. Huub Röttgering
ISBN: 978-94-6259-260-5
© 2014 Jeroen Bédorf
Dit proefschrift werd ondersteund door NWO IsFast grant #643.000.802.
Contents
1
Introduction
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 e very beginning . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 1960 - 1986: e Era Of Digital Computers . . . . . . . . . . . . . . . .
1.4 1986 - 2000 : Advances in software . . . . . . . . . . . . . . . . . . . . .
1.5 2000 - 2006: e Era Of e GRAPE . . . . . . . . . . . . . . . . . . .
1.5.1 GRAPE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5.2 Multi-Core Processors and Vector Instructions . . . . . . . . . .
1.5.3 Collisionless methods . . . . . . . . . . . . . . . . . . . . . . . .
1.6 2006 - Today: e Era Of Commercial High Performance Processing Units
1.6.1 Collisional methods . . . . . . . . . . . . . . . . . . . . . . . . .
1.6.2 Collisionless methods . . . . . . . . . . . . . . . . . . . . . . . .
1.7 Graphics Processing Units . . . . . . . . . . . . . . . . . . . . . . . . .
1.8 esis Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.8.1 Chapter 2 - Sapporo2 . . . . . . . . . . . . . . . . . . . . . . . .
1.8.2 Chapter 3 - OctGrav . . . . . . . . . . . . . . . . . . . . . . . .
1.8.3 Chapter 4 - Bonsai . . . . . . . . . . . . . . . . . . . . . . . . .
1.8.4 Chapter 5 - Many Minor Mergers . . . . . . . . . . . . . . . . .
1.8.5 Chapter 6 - Parallel Bonsai . . . . . . . . . . . . . . . . . . . . .
1
3
5
5
7
8
8
10
11
11
11
13
14
16
17
17
18
18
18
2
Sapporo2
2.1 Background . . . . . . . . . . . . . . . . . . . . .
2.2 Methods . . . . . . . . . . . . . . . . . . . . . . .
2.2.1 Parallelisation method . . . . . . . . . . .
2.2.2 Implementation . . . . . . . . . . . . . . .
2.3 Results . . . . . . . . . . . . . . . . . . . . . . . .
2.3.1 read-block configuration . . . . . . . . .
2.3.2 Block-size / active-particles . . . . . . . .
2.3.3 Range of N . . . . . . . . . . . . . . . . .
2.3.4 Double precision vs Double-single precision
2.3.5 Sixth order performance . . . . . . . . . .
2.3.6 Multi-GPU . . . . . . . . . . . . . . . . .
21
22
23
23
24
26
27
28
29
30
32
32
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
iv
2.4
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
34
34
35
36
Octgrav
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Implementation . . . . . . . . . . . . . . . . . . . . . .
3.2.1 Building the octree . . . . . . . . . . . . . . . .
3.2.2 Construction of an interaction list . . . . . . . .
3.2.3 Calculating accelerations from the interaction list
3.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.1 Accuracy of approximation . . . . . . . . . . . .
3.3.2 Timing . . . . . . . . . . . . . . . . . . . . . .
3.3.3 Device utilisation . . . . . . . . . . . . . . . . .
3.4 Discussion and Conclusions . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
37
38
39
39
40
41
42
43
44
45
46
Bonsai
4.1 Introduction . . . . . . . . . .
4.2 Sparse octrees on GPUs . . . .
4.2.1 Tree construction . . .
4.2.2 Tree traverse . . . . .
4.3 Gravitational Tree-code . . . .
4.3.1 Time Integration . . .
4.3.2 Tree-cell properties . .
4.3.3 Cell opening criterion
4.4 Performance and Accuracy . .
4.4.1 Performance . . . . .
4.4.2 Accuracy . . . . . . .
4.5 Discussion and Conclusions .
4.A Scan algorithms . . . . . . . .
4.A.1 Stream Compaction .
4.A.2 Split and Sort . . . . .
4.A.3 Implementation . . . .
4.B Morton Key generation . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
49
50
52
52
54
56
56
56
57
58
59
61
64
67
67
67
68
68
e Effect of Many Minor Mergers
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Constraining the model parameters . . . . . . . . . . . . . . . . . . . .
5.3 Initializing the galaxy mergers . . . . . . . . . . . . . . . . . . . . . .
5.3.1 Configuring the major mergers . . . . . . . . . . . . . . . . . .
5.3.2 Configuring the minor mergers . . . . . . . . . . . . . . . . .
5.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4.1 e growth of the primary due to subsequent mergers . . . . . .
5.4.2 e effect on the shape of the galaxies due to subsequent mergers
.
.
.
.
.
.
.
.
71
72
73
77
77
78
79
80
82
2.5
3
4
5
CONTENTS
Discussion and CPU support
2.4.1 CPU . . . . . . . .
2.4.2 XeonPhi . . . . . .
Conclusion . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
v
CONTENTS
5.4.3 e effect of the virial temperature
Discussion . . . . . . . . . . . . . . . . .
5.5.1 Properties of the merger remnant
5.6 Conclusion . . . . . . . . . . . . . . . .
5.A Resolution effects . . . . . . . . . . . . .
5.B e effect of child density . . . . . . . . .
5.B.1 Circular velocity . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
84
87
87
91
91
92
94
Parallel Bonsai
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 Quantitative discussion of current state of the art . . . . .
6.3 Implementation . . . . . . . . . . . . . . . . . . . . . . .
6.3.1 Tree-walk kernel optimizations . . . . . . . . . . .
6.3.2 Parallelization . . . . . . . . . . . . . . . . . . . .
6.4 Simulating the Milky Way Galaxy . . . . . . . . . . . . .
6.5 System and environment where performance was measured
6.6 Performance results . . . . . . . . . . . . . . . . . . . . .
6.6.1 Operation counts . . . . . . . . . . . . . . . . . .
6.6.2 Parallel performance . . . . . . . . . . . . . . . .
6.6.3 Time-to-solution . . . . . . . . . . . . . . . . . .
6.6.4 Peak performance . . . . . . . . . . . . . . . . . .
6.7 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
97
98
100
101
102
103
106
106
108
108
109
111
112
112
5.5
6
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
7
Conclusions
115
7.1 BRIDGE; Combining direct and hierarchical N -body methods . . . . . 115
7.2 e future . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
8
Samenvatting
8.1 De hoofdstukken in dit proefschrift
8.1.1 Hoofdstuk 2 . . . . . . . .
8.1.2 Hoofdstuk 3 . . . . . . . .
8.1.3 Hoofdstuk 4 . . . . . . . .
8.1.4 Hoofdstuk 5 . . . . . . . .
8.1.5 Hoofdstuk 6 . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
119
120
120
120
121
121
122
List of publications
123
Bibliography
125
Curriculum Vitae
137
Acknowledgements
139

View Uploaded Details

【ポイント10倍】 送料無料 【LEGEND WALKER】レジェンドウォーカー

Haneen NUR Biological and clinical implications of invariant natural

Top Sector Chemistry Student Competition Together

here - Lehrstuhl für ABWL und Corporate Governance

Student Presentations

The London Irish Studies Seminar

here - funCOS - Friedrich-Alexander-Universität Erlangen

Expert Talk: Diploma Computer Engineering

Summer School SFB TR 23 and SFB 834

Leaflet (PDF)

一人時間差相関 ∼ BHの直接検出を目指して ∼

this PDF file - Journal of Agriculture and Rural