Parallel Programming in OpenMP

by Chandra; Menon; Dagum; Kohr; Maydan; McDonald

• ISBN13: 9781558606715
• ISBN10: 1558606718
• Format: Paperback
• Copyright: 2000-10-02
• Publisher: Elsevier Science

Summary

The rapid and widespread acceptance of shared-memory multiprocessor architectures has created a pressing demand for an efficient way to program these systems. At the same time, developers of technical and scientific applications in industry and in government laboratories find they need to parallelize huge volumes of code in a portable fashion. OpenMP, developed jointly by several parallel computing vendors to address these issues, is an industry-wide standard for programming shared-memory and distributed shared-memory multiprocessors. It consists of a set of compiler directives and library routines that extend FORTRAN, C, and C++ codes to express shared-memory parallelism. Parallel Programming in OpenMP is the first book to teach both the novice and expert parallel programmers how to program using this new standard. The authors, who helped design and implement OpenMP while at SGI, bring a depth and breadth to the book as compiler writers, application developers, and performance engineers. * Designed so that expert parallel programmers can skip the opening chapters, which introduce parallel programming to novices, and jump right into the essentials of OpenMP. * Presents all the basic OpenMP constructs in FORTRAN, C, and C++. * Emphasizes practical concepts to address the concerns of real application developers. * Includes high quality example programs that illustrate concepts of parallel programming as well as all the constructs of OpenMP. * Serves as both an effective teaching text and a compact reference. * Includes end-of-chapter programming exercises.

Table of Contents

Foreward	vii
John L. Hennessy
Preface	xiii
Introduction	1	(14)
Performance with OpenMP	2	(4)
A First Glimpse of OpenMP	6	(2)
The OpenMP Parallel Computer	8	(1)
Why OpenMP?	9	(4)
History of OpenMP	13	(1)
Navigating the Rest of the Book	14	(1)
Getting Started with OpenMP	15	(26)
Introduction	15	(1)
OpenMP from 10,000 Meters	16	(7)
OpenMP Compiler Directives or Pragmas	17	(3)
Parallel Control Structures	20	(1)
Communication and Data Environment	20	(2)
Synchronization	22	(1)
Parallelizing a Simple Loop	23	(6)
Runtime Execution Model of an OpenMP Program	24	(1)
Communication and Data Scoping	25	(2)
Synchronization in the Simple Loop Example	27	(1)
Final Words on the Simple Loop Example	28	(1)
A More Complicated Loop	29	(3)
Explicit Synchronization	32	(3)
The reduction Clause	35	(1)
Expressing Parallelism with Parallel Regions	36	(3)
Concluding Remarks	39	(1)
Exercises	40	(1)
Exploiting Loop-Level Parallelism	41	(52)
Introduction	41	(1)
Form and Usage of the parallel do Directive	42	(4)
Clauses	43	(1)
Restrictions on Parallel Loops	44	(2)
Meaning of the parallel do Directive	46	(1)
Loop Nests and Parallelism	46	(1)
Controlling Data Sharing	47	(18)
General Properties of Data Scope Clause	49	(1)
The shared Clause	50	(1)
The private Clause	51	(2)
Default Variable Scopes	53	(3)
Changing Default Scoping Rules	56	(3)
Parallelizing Reduction Operations	59	(4)
Private Variable Initialization and Finalization	63	(2)
Removing Data Dependences	65	(17)
Why Data Dependences Are a Problem	66	(1)
The First Step: Detection	67	(4)
The Second Step: Classification	71	(2)
The Third Step: Removal	73	(8)
Summary	81	(1)
Enhancing Performance	82	(8)
Ensuring Sufficient Work	82	(3)
Scheduling Loops to Balance the Load	85	(1)
Static and Dynamic Scheduling	86	(1)
Scheduling Options	86	(2)
Comparison of Runtime Scheduling Behavior	88	(2)
Concluding Remarks	90	(1)
Exercises	90	(3)
Beyond Loop-Level Parallelism: Parallel Regions	93	(48)
Introduction	93	(1)
Form and Usage of the parallel Directive	94	(3)
Clauses on the parallel Directive	95	(1)
Restrictions on the parallel Directive	96	(1)
Meaning of the parallel Directive	97	(3)
Parallel Regions and SPMD-Style Parallelism	100	(1)
threadprivate Variables and the copyin Clause	100	(8)
The threadprivate Directive	103	(3)
The copyin Clause	106	(2)
Work-Sharing in Parallel Regions	108	(11)
A Parallel Task Queue	108	(1)
Dividing Work Based on Thread Number	109	(2)
Work-Sharing Constructs in OpenMP	111	(8)
Restrictions on Work-Sharing Constructs	119	(4)
Block Structure	119	(1)
Entry and Exit	120	(2)
Nesting of Work-Sharing Constructs	122	(1)
Orphaning of Work-Sharing Constructs	123	(3)
Data Scoping of Orphaned Constructs	125	(1)
Writing Code with Orphaned Work-Sharing Constructs	126	(1)
Nested Parallel Regions	126	(4)
Directive Nesting and Binding	129	(1)
Controlling Parallelism in an OpenMP Program	130	(7)
Dynamically Disabling the parallel Directives	130	(1)
Controlling the Number of Threads	131	(2)
Dynamic Threads	133	(2)
Runtime Library Calls and Environment Variables	135	(2)
Concluding Remarks	137	(1)
Exercises	138	(3)
Synchronization	141	(30)
Introduction	141	(1)
Data Conflicts and the Need for Synchronization	142	(5)
Getting Rid of Data Races	143	(1)
Examples of Acceptable Data Races	144	(2)
Synchronization Mechanisms in OpenMP	146	(1)
Mutual Exclusion Synchronization	147	(10)
The Critical Section Directive	147	(5)
The atomic Directive	152	(3)
Runtime Library Lock Routines	155	(2)
Event Synchronization	157	(5)
Barriers	157	(2)
Ordered Sections	159	(2)
The master Directive	161	(1)
Custom Synchronization: Rolling Your Own	162	(3)
The flush Directive	163	(2)
Some Practical Considerations	165	(6)
Concluding Remarks	168	(1)
Exercises	168	(3)
Performance	171	(40)
Introduction	171	(2)
Key Factors That Impact Performance	173	(25)
Coverage and Granularity	173	(2)
Load Balance	175	(4)
Locality	179	(13)
Synchronization	192	(6)
Performance-Tuning Methodology	198	(3)
Dynamic Threads	201	(3)
Bus-Based and NUMA Machines	204	(3)
Concluding Remarks	207	(1)
Exercises	207	(4)
Appendix A A Quick Reference to OpenMP	211	(6)
References	217	(4)
Index	221