Introduction to Parallel Programming

1 Introduction


1.1 Who Should Read This Book


1.2 Brief Introduction to Parallel Programming


1.3 About the Text


1.4 The Context of This Book


1.5 Add-Ons


2 Tiny Fortran


2.1 Introduction


2.2 Program Structure


2.3 Identifiers


2.4 Declarations: Scalars and Arrays


2.5 I/O


2.6 Array Storage


2.7 Assignment


2.8 Arithmetic Expressions


2.9 If-Then-Else-Endif Blocks


2.10 Loops


2.11 Function/Subroutine Calls


2.12 Passing Arguments in Function/Subroutine Calls


3 Hardware and Operating System Models


3.1 Introduction


3.2 Hardware


3.3 Time-Sharing with a Single Processor


3.4 Time-Sharing with Multiple Processors


3.5 A Brief Description of Tightly Coupled Multiprocessing


3.6 Summary


4 Processes, Shared Memory, and Simple Parallel Programs


4.1 Introduction


4.2 Processes and Processors


4.3 Shared Memory—1


4.4 Forking—Creating Processes


4.5 Joining Processes


4.6 Shared Memory—2


4.7 Processes Are Randomly Scheduled—Contention


4.8 Summary


5 Basic Parallel Programming Techniques


5.1 Introduction


5.2 Loop Splitting


5.3 Ideal Speedup


5.4 Spin-Locks, Contention and Self-Scheduling


5.5 Histogram


5.6 Summary


5.7 Additional Problems


6 Barriers and Race Conditions


6.1 Introduction


6.2 The Barrier Calls


6.3 Expression Splitting


6.4 Summary


6.5 Additional Problems—Elementary Statistics


7 Introduction to Scheduling—Nested Loops


7.1 Introduction


7.2 Variations on Loop Splitting


7.3 Variation on Self-Scheduling


7.4 Indirect Scheduling


7.5 Summary


7.6 Additional Problems


8 Overcoming Data Dependencies


8.1 Introduction


8.2 Induction Variable


8.3 Forward Dependency


8.4 Block Scheduling and Forward Dependency


8.5 Backward Dependency


8.6 Break Out of Loop


8.7 Splittable Loops


8.8 Reordering Loops


8.9 Special Scheduling—Assign Based on Condition


8.10 Additional Problems


9 Scheduling Summary


9.1 Introduction


9.2 Loop Splitting


9.3 Expression Splitting


9.4 Self-Scheduling


9.5 Indirect Scheduling


9.6 Block Scheduling


9.7 Special Scheduling


10 Linear Recurrence Relations—Backward Dependencies


10.1 Introduction to Recurrence Relations


10.2 x(i) = x(i - 1) + y(i)


10.3 x(i) = a(i)*x(i - 1) + y(i)


10.4 x(i) = a(i)*x(i - 1) + b(i)*x(i - 2)


10.5 Additional Problems—Other Recurrence Relations


11 Performance Tuning


11.1 Introduction


11.2 Parallel Programming and the Structure of Programs


11.3 Positioning the Process_Fork


11.4 The Effect of the Number of Processes on Overhead


11.5 Using Cache Effectively


12 Discrete Event, Discrete Time Simulation


12.1 Introduction


12.2 Description of the Model


12.3 Single-Stream Algorithm and Data Structures


12.4 Single-Stream Program


12.5 Introduction to the Parallel Version


12.6 Data Dependencies in the Parallel Algorithm


12.7 Updating Linked Lists—Contention and Deadlock


12.8 The Parallel Algorithm


12.9 Parallel Program


12.10 Summary


13 Some Applications


13.1 Introduction


13.2 Average and Mean Squared Deviation


13.3 Fitting a Line to Points


13.4 Numerical Integration


13.5 Exploring a Maze


13.6 Traveling Salesman Problem


13.7 General Gaussian Elimination


13.8 Gaussian Elimination for Tridiagonal Matrix


14 Semaphores and Events


14.1 Introduction


14.2 Semaphores


14.3 Events


14.4 Summary


15 Programming Projects

Appendix A—Equivalent C and Fortran Constructs

A.1 Program Structure

A.2 Loops

A.3 Conditionals

A.4 Branches

A.5 Functions and Subroutines

Appendix B—EPF: Fortran77 for Parallel Programming

B.1 Introduction

B.2 Parallel Regions and the Structure of an EPF Module

B.3 Sharing Memory—Private

B.4 Doall-End Doall

B.5 Critical Section-End Critical section

B.6 Barrier

B.7 Barrier Begin-End Barrier

B.8 Spin-Locks

B.9 Events

B.10 Built-In Functions

B.11 Some Subroutines Written in EPF

Appendix C—Parallel Programming on a Uniprocessor Under Unix

C.1 Introduction

C.2 Calling C Programs from Fortran and Vice Versa

C.3 Process_Fork

C.4 Spin-Locks

C.5 Barriers

C.6 Process_Join

C.7 Shared Memory

C.8 Cleanup

C.9 An Example

Bibliography

Index

Order Form for Parallel Programs on Diskette