Introduction to Concurrency in Programming Languages Book

1 Introduction 1

1.1 Motivation 3

1.1.1 Navigating the concurrency sea 3

1.2 Where does concurrency appear? 6

1.3 Why is concurrency considered hard? 9

1.3.1 Real-world concurrency 9

1.4 Timeline 11

1.5 Approach 12

1.5.1 Intended audience 13

1.5.2 Acknowledgments 14

1.6 Exercises 14

2 Concepts in Concurrency 17

2.1 Terminology 19

2.1.1 Units of execution 19

2.1.2 Parallelism versus concurrency 23

2.1.3 Dependencies and parallelism 25

2.1.4 Shared versus distributed memory 28

2.2 Concepts 29

2.2.1 Atomicity 30

2.2.2 Mutual exclusion and critical sections 34

2.2.3 Coherence and consistency 36

2.2.4 Thread safety 38

2.3 Exercises 40

3 Concurrency Control 43

3.1 Correctness 44

3.1.1 Race conditions 44

3.1.2 Deadlock 46

3.1.3 Liveness, starvation and fairness 49

3.1.4 Nondeterminism 51

3.2 Techniques 52

3.2.1 Synchronization 52

3.2.2 Locks 54

3.2.3 Seamphores 56

3.2.4 Monitors 57

3.2.5 Transactions 60

3.3 Exercises 62

4 The State of the Art 65

4.1 Limitations of libraries 66

4.2 Explicit techniques 69

4.2.1 Message passing 69

4.2.2 Explicity controlled threads 75

4.3 Higher-level techniques 76

4.3.1 Transactional memory 77

4.3.2 Event-driven programs 78

4.3.3 The Actor model 79

4.4 The limits of explicit control 80

4.4.1 Pointers and aliasing 81

4.5 Concluding remarks 82

4.6 Exercises 83

5 High-level Language Constructs 85

5.1 Common high-level constructs 88

5.1.1 Expression 89

5.1.2 Control flow primitives 91

5.1.3 Abstract types and data structures 92

5.2 Using and evaluating languages constructs 94

5.2.1 Cognitive dimesions 98

5.2.2 Working with the cognitive dimensions 101

5.3Implications of concurrency 102

5.3.1 Sequential constructs and concurrency 103

5.4 Interpreted languages 104

5.5 Exercises 106

6 Historical Context and Evolution of Languages 109

6.1 Evolution of machines 111

6.1.1 Multiprogramming and interrupt driven I/O 111

6.1.2 Cache-based memory hierarchies 112

6.1.3 Pipelining and vector processing 113

6.1.4 Dataflow 114

6.1.5 Massively parallel computers 115

6.1.6 Clusters and distributed memory systems 117

6.1.7 Integration 118

6.1.8 Flynn's taxonomy 118

6.2 Evoltion of programming languages 120

6.2.1 In the beginning, there was FORTRAN 120

6.2.2 The ALGOL family 122

6.2.3 Coroutines 125

6.2.4 CSP and process algebras 125

6.2.5 Concurrency in Ada 128

6.2.6 Declarative and functional languages 131

6.2.7 Parallel languages 138

6.2.8 Modern languages 144

6.3 Limits to automatic parallelization 145

6.4 Exercises 147

7 Modern Languages and Concurrency Constructs 149

7.1 Array abstraction 150

7.1.1 Array notation 152

7.1.2 Shifts 155

7.1.3 Index sets and regions 157

7.2 Messages passing 158

7.2.1 The Actor model 160

7.2.2 Channels 160

7.2.3 Co-arrays 161

7.3 Control flow 163

7.3.1 ALGOL collateral clauses 163

7.3.2 PAR, SEQ and ALT in occam 164

7.3.3 Parallel loops 166

7.4 Functional languages 168

7.5 Functional operators 169

7.5.1 Discussion of functional operators 171

7.6 Exercises 172

8 Performance Considerations and Modern Systems 175

8.1 Memory 176

8.1.1 Architectural solutions to the performance problem 177

8.1.2 Examining single threaded memory performance 178

8.1.3 Shared memory and cache coherence 180

8.1.4 Distributed memory as a deeper memory hierarchy 185

8.2 Amdahl's law, speedup, and efficiency 186

8.3 Locking 188

8.3.1 Serialization 188

8.3.2 Blocking 189

8.3.3 Wasted operations 190

8.4 Thread overhead 191

8.5 Exercises 194

9 Introduction to Parallel Algorithms 197

9.1 Designing parallel algorithms 198

9.2 Finding concurrency 199

9.3 Strategies for exploiting concurrency 200

9.4 Algorithm patterns 201

9.5 Patterns supporting parallel source code 203

9.6 Demonstrating parallel algorithm patterns 204

9.7 Exercises 205

10 Pattern: Task Parallelism 207

10.1 Supporting algorithm structures 208

10.1.1 The Master-worker pattern 209

10.1.2 Implementation mechanisms 210

10.1.3 Abstractions supporting task parallelism 212

10.2 Case study: Genetic algorithms 215

10.2.1 Population management 218

10.2.2 Individual expression and fitness evaluation 220

10.2.3 Discussion 221

10.3 Case study: Mandelbrot set computation 222

10.3.1 The problem 222

10.3.2 Identifying tasks and separating master from worker 223

10.3.3 Cilk implementation 226

10.3.4 OpenMP implementation 229

10.3.5 Discussion 230

10.4 Exercises 230

11 Pattern: Data Parallelism 233

11.1 Data parallel algorithms 233

11.2 Case study: Matrix multiplication 236

11.3 Case study: Cellular automation 238

11.4 Limitations of SIMD data parallel programming 240

11.5 Beyond SIMD 242

11.5.1 Approximating data parallelism with tasks 243

11.6 Geometric Decomposition 244

11.7 Exercises 245

12 Pattern: Recursive Algorithms 247

12.1 Recursion concepts 248

12.1.1 Recursion and concurrency 252

12.1.2 Recursion and the divide and conquer pattern 253

12.2 Case study: Sorting 254

12.3 Case study: Sudoku 257

12.4 Exercises 261

13 Pattern: Pipelined Algorithms 263

13.1 Pipelining as a software design pattern 265

13.2 Languages support for pipelining 266

13.3 Case study: Pipelining in Erlang 267

13.3.1 Pipeline construction 268

13.3.2 Pipeline stage structure 269

13.3.3 Discussion 270

13.4 Case study: Visual cortex 272

13.4.1 Peta Vision code description 274

13.5 Exercises 276

Appendix A OpenMP Quick Reference 279

A.1 OpenMP fundamentals 280

A.2 Creating threads and their implicit tasks 280

A.3 OpenMP data environment 282

A.4 Synchronization and the OpenMP memory model 285

A.5 Work Sharing 288

A.6 OpenMP runtime library and environment variables 291

A.7 Explicit tasks and OpenMP 3.0 292

Appendix B Erlang Quick Refernce 295

B.1 Language basics 295

B.2 Execution and memory model 300

B.3 Message passing syntax 301

Appendix C Cilk Quick Reference 305

C.1 Cilk keyswords 306

C.2 Cilk model 310

C.2.1 Work and span metrics 310

C.2.2 Memory model 311

C.3 Clik standard library 312

C.4 Further information 314

References 315

Index 323