Parallel Iterative Algorithms: From Sequential to Grid Computing (Chapman and Hall/CRC Numerical Analy and Scient Comp. Series)

✍ Scribed by Jacques Mohcine Bahi, Sylvain Contassot-Vivier, Raphael Couturier

• Publisher: Chapman and Hall/CRC
• Year: 2007
• Tongue: English
• Leaves: 225
• Series: Chapman and Hall/CRC Numerical Analysis and Scientific Computation Series
• Edition: 1
• Category: Library

✦ Synopsis

This book addresses a kind of computing that has become common, in terms of physical resources, but that has been difficult to exploit properly. It's not cluster computing, where processors tend to be homogeneous and communications have low latency. It's not the "SETI at home" model, with extreme heterogeneity and long latencies. Instead, it's the Grid model: long latencies between heterogeneous subnets, but cluster-like speeds within the subnet. This creates unique demands, but also addresses a number of other two-level systems beyond those the authors discuss.

Synchronous algorithms work well within clusters, where communication latency lies below the computation time of one step on each node, and where each node can be expected to run at roughly the same speed as each other. Such algorithms have a fair literature of their own, and are addressed only in the prepratory chapters. Grid communication is different. Processor speeds lie in the nanosecond range these days. Intra-cluster communications range up many microseconds, and intercluster latencies range from milliseconds to seconds. The network of networks is a different beast, and this book addresses that strange creature.

These authors address algorithms that expect to iterate repeatedly and an unpredictable number of times between communication with neighboring sub-problems. In particular, the authors address iterative solution of sparse linear systems - perhaps a loss of generality, but not a loss of practical value. They present their approaches methodically and rigorously - expect to go through this book slowly, and maybe even go back to Strang once in a while. They also address the fact that distributed determination of convergence is at least as demanding as distributed agreements of many other kinds. As an interesting bonus, the asynchronous algorithms also grant some degree of fault tolerance in the presence of intermittent communication failure, such as packet loss due to network congestion.

This book's strengths, for me at least, lie in two areas. The first is its emphasis on pseudocode for critical algorithms - not cut&paste material, but clearly illustrative. The second lies in its progression from cluster-scale synchronous algorithms to Grid-scale asynchronous ones. This can also describe hardware-accelerated nodes within a cluster: fast communication with the accelerator, but orders of magnitude slower and less predictable communication betwee accelerated nodes. The absolute time scales and distances differ, but the ratios of local to non-local communication time and computation time hold up well.

Only the most dedicated readers will invest the time and effort needed to extract this book's value. Those readers, however, will be richly rewarded.

-- wiredweird

✦ Table of Contents

Parallel Iterative Algorithms: From Sequential to Grid Computing......Page 3
Contents......Page 5
List of Tables......Page 8
List of Figures......Page 10
Acknowledgments......Page 12
Appendix......Page 213
References......Page 217
Introduction......Page 13
1.1.1 Characteristic elements of a matrix......Page 17
1.1.2 Norms......Page 18
1.2 Sequential iterative algorithms......Page 21
1.3 A classical illustration example......Page 24
2.1.1 Construction and convergence of linear iterative algorithms......Page 26
2.1.2 Speed of convergence of linear iterative algorithms......Page 28
2.1.3 Jacobi algorithm......Page 30
2.1.4 Gauss-Seidel algorithm......Page 32
2.1.5 Successive overrelaxation method......Page 34
2.1.6 Block versions of the previous algorithms......Page 35
2.1.7 Block tridiagonal matrices......Page 37
2.1.8 Minimization algorithms to solve linear systems......Page 39
2.1.8.1 Descent and Gradient algorithms......Page 40
2.1.8.2 Conjugate gradient algorithm......Page 41
2.1.8.3 GMRES......Page 42
2.1.8.4 BiConjugate Gradient algorithm......Page 47
2.1.9 Preconditioning......Page 48
2.1.9.2 Preconditioning matrices for the conjugate gradient algorithm......Page 50
2.1.9.3 Implementation of the preconditioned conjugate gradient solver......Page 51
2.1.9.4 Incomplete LU factorization......Page 53
2.2 Nonlinear equation systems......Page 54
2.2.1 Derivatives......Page 55
2.2.2 Newton method......Page 56
2.2.3 Convergence of the Newton method......Page 58
2.3 Exercises......Page 60
3.1 Historical context......Page 64
3.2.1 Classifications of the architectures......Page 66
3.2.1.1 Parallel machines......Page 67
3.2.1.2 Local clusters......Page 71
3.2.1.3 Distributed clusters/grids......Page 72
3.3 Trends of used configurations......Page 75
3.4 Classification of parallel iterative algorithms......Page 76
3.4.1 Synchronous iterations - synchronous communications (SISC)......Page 77
3.4.2 Synchronous iterations - asynchronous communications (SISC)......Page 78
3.4.3 Asynchronous iterations - asynchronous communications (AIAC)......Page 79
3.4.3.1 Semi-flexible communications......Page 81
3.4.3.2 Flexible communications......Page 82
3.4.4.1 Parallel machines......Page 83
3.4.4.3 Distributed clusters/grids......Page 84
4.1.1 Block Jacobi and O’Leary and White multisplitting algorithms......Page 85
4.1.2 General multisplitting algorithms......Page 90
4.1.2.1 Obtaining O’Leary and White multisplitting......Page 91
4.1.2.3 Obtaining discrete analogues of multisubdomain Schwarz algorithms......Page 92
4.2.1 Newton-Jacobi algorithms......Page 93
4.2.2 Newton-multisplitting algorithms......Page 94
4.4 Implementation......Page 96
4.4.1 Survey of synchronous algorithms with shared memory architecture......Page 98
4.4.2 Synchronous Jacobi algorithm......Page 99
4.4.4 Synchronous block Jacobi algorithm......Page 102
4.4.5 Synchronous multisplitting algorithm for solving linear systems......Page 105
4.4.5.3 Overlapping strategy that mixes overlapped components with close neighbors......Page 110
4.4.5.4 Overlapping strategy that mixes all overlapped components......Page 114
4.4.6 Synchronous Newton-multisplitting algorithm......Page 115
4.5 Convergence detection......Page 118
4.6 Exercises......Page 121
Introduction......Page 124
5.1 Advantages of asynchronous algorithms......Page 125
5.2.1 The mathematical model of asynchronous algorithms......Page 126
5.2.2 Some derived basic algorithms......Page 128
5.2.3 Convergence results of asynchronous algorithms......Page 129
5.3.1 The linear framework......Page 131
5.4 Parallel asynchronous multisplitting algorithms......Page 133
5.4.1 A general framework of asynchronous multisplitting methods......Page 134
5.4.2 Asynchronous multisplitting algorithms for linear problems......Page 137
5.4.3 Asynchronous multisplitting algorithms for nonlinear problems......Page 138
5.4.3.2 The discrete analogue of Schwarz alternating method and its multisubdomain generalizations......Page 140
5.4.3.4 Discrete analogue of the multisubdomain Schwarz method......Page 141
5.5.1 Newton-multisplitting algorithms: multisplitting algorithms as inner algorithms in the Newton method......Page 142
5.6 Implementation......Page 144
5.6.1 Some solutions to manage the communications using threads......Page 146
5.6.3 Asynchronous block Jacobi algorithm......Page 148
5.6.4 Asynchronous multisplitting algorithm for solving linear systems......Page 151
5.6.5 Asynchronous Newton-multisplitting algorithm......Page 153
5.6.6 Asynchronous multisplitting-Newton algorithm......Page 155
5.7.1 Decentralized convergence detection algorithm......Page 158
5.7.1.1 Local convergence detection......Page 159
5.7.1.2 Global convergence detection......Page 160
5.8 Exercises......Page 182
Introduction......Page 186
6.1.1 Comparison of the environments......Page 187
6.1.1.2 Ease of programming......Page 188
6.2 Two environments dedicated to asynchronous iterative algorithms......Page 189
6.2.1.1 The daemon......Page 190
6.2.1.2 The computing task......Page 191
6.2.1.3 The spawner......Page 192
6.2.2 CRAC......Page 193
6.2.2.1 Architecture......Page 194
6.4.1 Context of experimentation......Page 199
6.4.2 Comparison of local and distant executions......Page 202
6.4.3 Impact of the computation amount......Page 204
6.4.4 Larger experiments......Page 205
6.4.5.1 Influence of the overlapping......Page 206
6.4.5.2 Memory requirements with a direct method......Page 207
6.5 Experiments in the context of partial differential equations using a finite difference scheme......Page 209
A-1.1 Z-matrices, M -matrices and H-matrices......Page 214
A-1.3 Sequences and sets......Page 215