Introduction to Concurrency in Programming Languages

by Sottile; Matthew J.

• ISBN13: 9781420072136
• ISBN10: 1420072137
• Format: Hardcover
• Copyright: 2009-09-28
• Publisher: Chapman & Hall/

Summary

High-performance parallel architectures have been available for many years, but now for the fist time, parallel computers can be found on the desktop and are available to everyday users. Designed specifically for application developers, Introduction to Concurrency in Programming Languagesprovides a survey of high-level programming constructs that make parallel programming more accessible. The book covers the history of parallel languages and explains the relation of hardware developments that motivated these languages to modern systems. It also describes the current state of the art in parallel languages, with a focus on the PGAS and HPCS language families.  Each chapter is accompanied by a set of exercises.

Table of Contents

Introduction	p. 1
Motivation	p. 3
Navigating the concurrency sea	p. 3
Where does concurrency appear?	p. 6
Why is concurrency considered hard?	p. 9
Real-world concurrency	p. 9
Timeline	p. 11
Approach	p. 12
Intended audience	p. 13
Acknowledgments	p. 14
Exercises	p. 14
Concepts in Concurrency	p. 17
Terminology	p. 19
Units of execution	p. 19
Parallelism versus concurrency	p. 23
Dependencies and parallelism	p. 25
Shared versus distributed memory	p. 28
Concepts	p. 29
Atomicity	p. 30
Mutual exclusion and critical sections	p. 34
Coherence and consistency	p. 36
Thread safety	p. 38
Exercises	p. 40
Concurrency Control	p. 43
Correctness	p. 44
Race conditions	p. 44
Deadlock	p. 46
Liveness, starvation and fairness	p. 49
Nondeterminism	p. 51
Techniques	p. 52
Synchronization	p. 52
Locks	p. 54
Seamphores	p. 56
Monitors	p. 57
Transactions	p. 60
Exercises	p. 62
The State of the Art	p. 65
Limitations of libraries	p. 66
Explicit techniques	p. 69
Message passing	p. 69
Explicity controlled threads	p. 75
Higher-level techniques	p. 76
Transactional memory	p. 77
Event-driven programs	p. 78
The Actor model	p. 79
The limits of explicit control	p. 80
Pointers and aliasing	p. 81
Concluding remarks	p. 82
Exercises	p. 83
High-level Language Constructs	p. 85
Common high-level constructs	p. 88
Expression	p. 89
Control flow primitives	p. 91
Abstract types and data structures	p. 92
Using and evaluating languages constructs	p. 94
Cognitive dimesions	p. 98
Working with the cognitive dimensions	p. 101
Implications of concurrency	p. 102
Sequential constructs and concurrency	p. 103
Interpreted languages	p. 104
Exercises	p. 106
Historical Context and Evolution of Languages	p. 109
Evolution of machines	p. 111
Multiprogramming and interrupt driven I/O	p. 111
Cache-based memory hierarchies	p. 112
Pipelining and vector processing	p. 113
Dataflow	p. 114
Massively parallel computers	p. 115
Clusters and distributed memory systems	p. 117
Integration	p. 118
Flynn's taxonomy	p. 118
Evoltion of programming languages	p. 120
In the beginning, there was FORTRAN	p. 120
The ALGOL family	p. 122
Coroutines	p. 125
CSP and process algebras	p. 125
Concurrency in Ada	p. 128
Declarative and functional languages	p. 131
Parallel languages	p. 138
Modern languages	p. 144
Limits to automatic parallelization	p. 145
Exercises	p. 147
Modern Languages and Concurrency Constructs	p. 149
Array abstraction	p. 150
Array notation	p. 152
Shifts	p. 155
Index sets and regions	p. 157
Messages passing	p. 158
The Actor model	p. 160
Channels	p. 160
Co-arrays	p. 161
Control flow	p. 163
ALGOL collateral clauses	p. 163
PAR, SEQ and ALT in occam	p. 164
Parallel loops	p. 166
Functional languages	p. 168
Functional operators	p. 169
Discussion of functional operators	p. 171
Exercises	p. 172
Performance Considerations and Modern Systems	p. 175
Memory	p. 176
Architectural solutions to the performance problem	p. 177
Examining single threaded memory performance	p. 178
Shared memory and cache coherence	p. 180
Distributed memory as a deeper memory hierarchy	p. 185
Amdahl's law, speedup, and efficiency	p. 186
Locking	p. 188
Serialization	p. 188
Blocking	p. 189
Wasted operations	p. 190
Thread overhead	p. 191
Exercises	p. 194
Introduction to Parallel Algorithms	p. 197
Designing parallel algorithms	p. 198
Finding concurrency	p. 199
Strategies for exploiting concurrency	p. 200
Algorithm patterns	p. 201
Patterns supporting parallel source code	p. 203
Demonstrating parallel algorithm patterns	p. 204
Exercises	p. 205
Pattern: Task Parallelism	p. 207
Supporting algorithm structures	p. 208
The Master-worker pattern	p. 209
Implementation mechanisms	p. 210
Abstractions supporting task parallelism	p. 212
Case study: Genetic algorithms	p. 215
Population management	p. 218
Individual expression and fitness evaluation	p. 220
Discussion	p. 221
Case study: Mandelbrot set computation	p. 222
The problem	p. 222
Identifying tasks and separating master from worker	p. 223
Cilk implementation	p. 226
OpenMP implementation	p. 229
Discussion	p. 230
Exercises	p. 230
Pattern: Data Parallelism	p. 233
Data parallel algorithms	p. 233
Case study: Matrix multiplication	p. 236
Case study: Cellular automation	p. 238
Limitations of SIMD data parallel programming	p. 240
Beyond SIMD	p. 242
Approximating data parallelism with tasks	p. 243
Geometric Decomposition	p. 244
Exercises	p. 245
Pattern: Recursive Algorithms	p. 247
Recursion concepts	p. 248
Recursion and concurrency	p. 252
Recursion and the divide and conquer pattern	p. 253
Case study: Sorting	p. 254
Case study: Sudoku	p. 257
Exercises	p. 261
Pattern: Pipelined Algorithms	p. 263
Pipelining as a software design pattern	p. 265
Languages support for pipelining	p. 266
Case study: Pipelining in Erlang	p. 267
Pipeline construction	p. 268
Pipeline stage structure	p. 269
Discussion	p. 270
Case study: Visual cortex	p. 272
Peta Vision code description	p. 274
Exercises	p. 276
OpenMP Quick Reference	p. 279
OpenMP fundamentals	p. 280
Creating threads and their implicit tasks	p. 280
OpenMP data environment	p. 282
Synchronization and the OpenMP memory model	p. 285
Work Sharing	p. 288
OpenMP runtime library and environment variables	p. 291
Explicit tasks and OpenMP 3.0	p. 292
Erlang Quick Refernce	p. 295
Language basics	p. 295
Execution and memory model	p. 300
Message passing syntax	p. 301
Cilk Quick Reference	p. 305
Cilk keyswords	p. 306
Cilk model	p. 310
Work and span metrics	p. 310
Memory model	p. 311
Clik standard library	p. 312
Further information	p. 314
References	p. 315
Index	p. 323
Table of Contents provided by Ingram. All Rights Reserved.