Introduction to Parallel Programming (eBook)

Steven Brawer (Autor)

eBook Download: PDF

2014 | 1. Auflage
436 Seiten
Elsevier Science (Verlag)
9781483216591 (ISBN)

Infos

Introduction to Parallel Programming focuses on the techniques, processes, methodologies, and approaches involved in parallel programming. The book first offers information on Fortran, hardware and operating system models, and processes, shared memory, and simple parallel programs. Discussions focus on processes and processors, joining processes, shared memory, time-sharing with multiple processors, hardware, loops, passing arguments in function/subroutine calls, program structure, and arithmetic expressions. The text then elaborates on basic parallel programming techniques, barriers and race conditions, and nested loops. The manuscript takes a look at overcoming data dependencies, scheduling summary, linear recurrence relations, and performance tuning. Topics include parallel programming and the structure of programs, effect of the number of processes on overhead, loop splitting, indirect scheduling, block scheduling and forward dependency, and induction variable. The publication is a valuable reference for researchers interested in parallel programming.

Inhalt

Front Cover 1
Introduction to Parallel Programming 4
Copyright Page 5
Table of Contents 8
Dedication 6
Chapter 1. Introduction 14
1.1 Who Should Read This Book 14
1.2 Brief Introduction to Parallel Programming 15
1.3 About the Text 16
1.4 The Context of This Book 19
1.5 Add-Ons 20
Chapter 2. Tiny Fortran 22
2.1 Introduction 22
2.2 Program Structure 23
2.3 Identifiers 25
2.4 Declarations: Scalars and Arrays 26
2.5 I/O 27
2.6 Array Storage 28
2.7 Assignment 28
2.8 Arithmetic Expressions 28
2.9 If-then-else-endif Blocks 30
2.10 Loops 32
2.11 Function/Subroutine Calls 34
2.12 Passing Arguments in Function/Subroutine Calls 35
Chapter 3. Hardware and Operating System Models 40
3.1 Introduction 40
3.2 Hardware 41
3.3 Time-Sharing with a Single Processor 42
3-4 Time-sharing with Multiple Processors 46
3.5 A Brief Description of Tightly Coupled Multiprocessing 47
3.6 Summary 52
Chapter 4. Processes, Shared Memory, and Simple Parallel Programs 54
4.1 Introduction 54
4.2 Processes and Processors 55
4.3 Shared Memory—1 57
4.4 Forking—Creating Processes 59
4.5 Joining Processes 64
4.6 Shared Memory—2 68
4.7 Processes Are Randomly Scheduled—Contention 77
4.8 Summary 80
Chapter 5. Basic Parallel Programming Techniques 82
5.1 Introduction 82
5.2 Loop Splitting 82
5.3 Ideal Speedup 88
5.4 Spin-Locks, Contention, and Self-Scheduling 92
5.5 Histogram 106
5.6 Summary 113
5.7 Additional Problems 114
Chapter 6. Barriers and Race Conditions 116
6.1 Introduction 116
6.2 The Barrier Calls 116
6.3 Expression Splitting 127
6.4 Summary 132
6.5 Additional Problems—Elementary Statistics 133
Chapter 7. Introduction to Scheduling—Nested Loops 134
7.1 Introduction 134
7.2 Variations on Loop Splitting 138
7.3 Variation on Self-Scheduling 146
7.4 Indirect Scheduling 149
7.5 Summary 151
7.6 Additional Problems 152
Chapter 8. Overcoming Data Dependencies 154
8.1 Introduction 154
8.2 Induction Variable 155
8.3 Forward Dependency 158
8.4 Block Scheduling and Forward Dependency 161
8.5 Backward Dependency 167
8.6 Break Out of Loop 168
8.7 Splittable Loops 173
8.8 Reordering Loops 182
8.9 Special Scheduling—Assign Based on Condition 187
8.10 Additional Problems 191
Chapter 9. Scheduling Summary 194
9.1 Introduction 194
9.2 Loop Splitting 194
9.3 Expression Splitting 195
9.4 Self-Scheduling 196
9.5 Indirect Scheduling 197
9.6 Block Scheduling 199
9.7 Special Scheduling 200
Chapter 10. Linear Recurrence Relations—Backward Dependencies 202
10.1 Introduction to Recurrence Relations 202
10.2 x ( i ) = x ( i – 1) + y ( i ) 204
10.3 x ( i ) = a ( i ) * x ( i – 1) + y ( i ) 213
10.4 x ( i ) = a ( i ) * x ( i – 1) + b ( i ) * x ( i – 2) 224
10.5 Additional Problems—Other Recurrence Relations 228
Chapter 11. Performance Tuning 232
11.1 Introduction 232
11.2 Parallel Programming and the Structure of Programs 233
11.3 Positioning the process_fork 238
11.4 The Effect of the Number of Processes on Overhead 242
11.5 Using Cache Effectively 245
Chapter 12. Discrete Event, Discrete Time Simulation 252
12.1 Introduction 252
12.2 Description of the Model 254
12.3 Single-Stream Algorithm and Data Structures 257
12.4 Single-Stream Program 261
12.5 Introduction to the Parallel Version 273
12.6 Data Dependencies in the Parallel Algorithm 273
12.7 Updating Linked Lists—Contention and Deadlock 276
12.8 The Parallel Algorithm 286
12.9 Parallel Program 287
12.10 Summary 304
Chapter 13. Some Applications 306
13.1 Introduction 306
13.2 Average and Mean Squared Deviation 306
13.3 Fitting a Line to Points 308
13.4 Numerical Integration 311
13.5 Exploring a Maze 312
13.6 Traveling Salesman Problem 321
13.7 General Gaussian Elimination 342
13.8 Gaussian Elimination for Tridiagonal Matrix 355
Chapter 14. Semaphores and Events 360
14.1 Introduction 360
14.2 Semaphores 361
14.3 Events 374
14.4 Summary 381
Chapter 15. Programming Projects 382
APPENDIX A: Equivalent C and Fortran Constructs 384
A.1 Program Structure 384
A.2 Loops 385
A.3 Conditionals 386
A.4 Branches 388
A.5 Functions and Subroutines 388
APPENDIX B: EPF: Fortran77 for Parallel Programming 392
B.1 Introduction 392
B.2 Parallel Regions and the Structure of an EPF Module 393
B.3 Sharing Memory—Private 395
B.4 doall—end doall 397
B.5 critical section—end critical section 400
B.6 barrier 402
B.7 barrier begin—end barrier 403
B.8 Spin-Locks 405
B.9 Events 405
B.10 Built-in Functions 406
B.11 Some Subroutines Written in EPF 407
APPENDIX C: Parallel Programming on a Uniprocessor Under Unix 414
C.1 Introduction 414
C.2 Calling C Programs from Fortran and Vice Versa 415
C.3 process_fork 418
C.4 Spin-Locks 419
C.5 Barriers 421
C.6 process_join 423
C.7 Shared Memory 424
C.8 Cleanup 426
C9 An Example 427
Bibliography 430
Index 432
Order Form for Parallel Programs on Diskette 436

Produkt-Details

• Erscheint lt. Verlag: 10.5.2014
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Datenbanken
• Themenwelt: Mathematik / Informatik ► Informatik ► Theorie / Studium
• ISBN-13: 9781483216591 / 9781483216591