Parallel Programming with Co-Arrays

Cover......Page 1
Half Title......Page 2
Title Page......Page 4
Copyright Page......Page 5
Table of Contents......Page 6
Preface......Page 10
1: Prologue......Page 12
2.1 A co-array program......Page 14
2.2 Exercises......Page 18
3.1 Uniform partitions......Page 20
3.2 Non-uniform partitions......Page 23
3.3 Row-partitioned matrix-vector multiplication......Page 25
3.4 Input/output in the co-array model......Page 27
3.5 Exercises......Page 28
4.1 The partition of unity......Page 30
4.2 Column-partitioned matrix-vector multiplication......Page 32
4.3 The dot-product operation......Page 34
4.4 Extended definition of partition operators......Page 35
4.5 Exercises......Page 36
5.1 Reduction to root......Page 38
5.2 Broadcast from root......Page 41
5.3 The sum-to-all operation......Page 42
5.4 The max-to-all and min-to-all operations......Page 43
5.6 Collectives with array arguments......Page 44
5.7 The scatter and gather operations......Page 45
5.9 Exercises......Page 48
6: Performance Modeling......Page 50
6.1 Execution time for the sum-to-all operation......Page 51
6.2 Execution time for the dot-product operation......Page 52
6.4 Strong scaling under a fixed-size constraint......Page 54
6.5 Weak scaling under a fixed-time constraint......Page 58
6.6 Weak scaling under a fixed-work constraint......Page 60
6.7 Weak scaling under a fixed-efficiency constraint......Page 61
6.8 Some remarks on computer performance modeling......Page 63
6.9 Exercises......Page 65
7.1 The abstract matrix class......Page 68
7.2 Sparse matrix classes......Page 70
7.3 The compressed-sparse-row matrix class......Page 72
7.4 Matrix-vector multiplication for a CSR matrix......Page 75
7.5 Exercises......Page 77
8.1 The conjugate gradient algorithm......Page 78
8.2 Other Krylov solvers......Page 81
8.3 Performance analysis for the conjugate gradient algorithm......Page 82
8.4 Strong scaling......Page 85
8.5 Weak scaling......Page 87
8.7 Exercises......Page 89
9: Blocked Matrices......Page 90
9.2 An abstract class for dense matrices......Page 91
9.3 The dense matrix class......Page 92
9.4 Matrix-matrix multiplication......Page 95
9.5 LU decomposition......Page 98
9.6 Partial pivoting......Page 103
9.7 Solving triangular systems of equations......Page 105
9.8 Exercises......Page 109
10.1 The transpose operation......Page 110
10.2 A row-partitioned matrix transposed to a row-partitioned matrix......Page 113
10.3 The Fast Fourier Transform......Page 116
10.4 Performance analysis......Page 117
10.5 Strong scaling......Page 119
10.6 Weak scaling......Page 120
10.7 Exercises......Page 121
11.1 Finite difference methods......Page 122
11.2 Partitioned finite difference methods......Page 125
11.3 The halo-exchange subroutine......Page 127
11.4 Exercises......Page 129
12.1 Subpartition operators......Page 130
12.2 Assigning blocks to images......Page 132
12.4 Permuted distributions......Page 133
12.5 The cyclic distribution......Page 135
12.6 Load balancing......Page 136
12.7 Exercises......Page 137
13.1 Blocked matrices......Page 138
13.2 The block matrix class......Page 141
13.3 Optimization of the LU-decomposition algorithm......Page 147
13.4 Exercises......Page 149
14: The Finite Element Method......Page 152
14.1 Basic ideas from finite element analysis......Page 153
14.2 Nodes, elements and basis functions......Page 154
14.3 Mesh partition operators......Page 158
14.4 The mesh class......Page 161
14.5 Integrating the heat equation......Page 165
14.6 Exercises......Page 167
15.1 Graphs......Page 170
15.2 The breadth-first search......Page 172
15.3 The graph class......Page 175
15.4 A parallel breadth-first-search algorithm......Page 176
15.5 The Graph 500 benchmark......Page 178
15.6 Exercises......Page 180
16: Epilogue......Page 182
A: A Brief Reference Manual for the Co-array Model......Page 184
A.1 The image index......Page 185
A.2 Co-arrays and co-dimensions......Page 186
A.3 Relative co-dimension indices......Page 188
A.4 Co-array variables with multiple co-dimensions......Page 189
A.5 Co-array variables of derived type......Page 190
A.7 Pointers......Page 193
A.9 Execution control......Page 194
A.10 Full barriers......Page 195
A.11 Partial barriers......Page 196
A.12 Critical segments and locks......Page 198
A.13 Input/output......Page 200
A.14 Command line arguments......Page 201
A.16 Inquiry functions......Page 202
A.18 Execution control statements......Page 203
Bibliography......Page 208
Index......Page 218