This book is a practical introduction to parallel programming in C using the MPI (Message Passing Interface) library and the OpenMP application programming interface. It is targeted to upper-division undergraduate students, beginning graduate students, and computer professionals learning this material on their own. It assumes the reader has a good background in C programming and has had an introductory class in the analysis of algorithms.

The era of practical parallel programming has arrived, marked by the popularity of the MPI and OpenMP software standards and the emergence of commodity clusters as the hardware platform of choice for an increasing number of organizations. This exciting new book, Parallel Programming in C with MPI and OpenMP, addresses the needs of students and professionals who want tO learn how to design, analyze, implement, and benchmark parallel programs in C using MPI and/or OpenMP. It combines a rock-solid design methodology with coverage of the most important MPI functions and OpenMP directives. It also demonstrates, through a wide range of examples, how to develop parallel programs that will execute efficiently on today's parallel platforms.

Preface xiv

1 Motivation and History 1

2 Parallel Architectures 27

3 Parallel Algorithm Design 63

4 Message-Passing Programming 93

5 The Sieve of Eratosthenes 115

6 Floyd's Algorithm 137

7 Performance Analysis 159

8 Matrix-Vector Multiplication 178

9 Document Classification 216

10 Monte Carlo Methods 239

11 Matrix Multiplication 273

12 Solving Linear Systems 290

13 Finite Difference Methods 318

14 Sorting 338

15 The Fast Fourier Transform 353

16 Combinatorial Search 369

17 Shared-Memory Programming 404

18 Combining MPI and OpenMP 436

Appendix A MPI Functions 450

Appendix B Utility Functions 485

Appendix C Debugging MPI Programs 505

Appendix D Review of Complex Numbers 509

Appendix E OpenMP Functions 513

Bibliography 515

Author Index 520

Subject Index 522