In Praise of An Introduction to Parallel Programming With the coming of multicore processors and the cloud, parallel computing is most cer- tainly not a niche area off in a corner of the computing world. Parallelism has become central to the efficient use of resources, and this new textbook by Peter Pacheco will go a long way toward introducing students early in their academic careers to both the art and practice of parallel computing. Duncan Buell Department of Computer Science and Engineering University of South Carolina An Introduction to Parallel Programming illustrates fundamental programming principles in the increasingly important area of shared-memory programming using Pthreads and OpenMP and distributed-memory programming using MPI. More important, it empha- sizes good programming practices by indicating potential performance pitfalls.
These topics are presented in the context of a variety of disciplines, including computer science, physics, and mathematics. The chapters include numerous programming exercises that range from easy to very challenging. This is an ideal book for students or professionals looking to learn parallel programming skills or to refresh their knowledge. Leigh Little Department of Computational Science The College at Brockport, The State University of New York An Introduction to Parallel Programming is a well-written, comprehensive book on the field of parallel computing.
Students and practitioners alike will appreciate the rele- vant, up-to-date information. Peter Pacheco’s very accessible writing style, combined with numerous interesting examples, keeps the reader’s attention. In a field that races forward at a dizzying pace, this book hangs on for the wild ride covering the ins and outs of parallel hardware and software. Liszka Department of Computer Science University of Akron Parallel computing is the future and this book really helps introduce this complicated subject with practical and useful examples.
Sloss, FBCS Consultant Engineer, ARM Author of ARM System Developer’s Guide Recommended Reading List For students interested in furthering their understanding of parallel programming, the content in the following books supplements this textbook: Programming Massively Parallel Processors A Hands-on Approach By David B. Kirk and Wen-mei W. Hwu ISBN: 9780123814722 The Art of Multiprocessor Programming By Maurice Herlihy and Nir Shavit ISBN: 9780123705914 Parallel Programming with MPI By Peter Pacheco ISBN: 9781558603394 The Sourcebook of Parallel Computing Edited by Jack Dongarra et al. ISBN: 9781558608719 Parallel Computer Architecture A Hardware/Software Approach By David Culler, J.
Singh and Anoop Gupta ISBN: 9781558603431 Engineering a Compiler, Second Edition By Keith D. Cooper and Linda Torczon ISBN: 9780120884780 mkp.com An Introduction to Parallel Programming This page intentionally left blank An Introduction to Parallel Programming Peter S. Pacheco University of San Francisco AMSTERDAM • BOSTON • HEIDELBERG • LONDON NEW YORK • OXFORD • PARIS • SAN DIEGO SAN FRANCISCO • SINGAPORE • SYDNEY • TOKYO Morgan Kaufmann Publishers is an imprint of Elsevier Acquiring Editor: Todd Green Development Editor: Nate McFadden Project Manager: Marilyn E. Rash Designer: Joanne Blank Morgan Kaufmann Publishers is an imprint of Elsevier.
30 Corporate Drive, Suite 400 Burlington, MA 01803, USA Copyright c 2011 Elsevier Inc. All rights reserved. No part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording, or any information storage and retrieval system, without permission in writing from the publisher. Details on how to seek permission, further information about the Publisher’s permissions policies and our arrangements with organizations such as the Copyright Clearance Center and the Copyright Licensing Agency, can be found at our website: www.
This book and the individual contributions contained in it are protected under copyright by the Publisher (other than as may be noted herein). Notices Knowledge and best practice in this field are constantly changing. As new research and experience broaden our understanding, changes in research methods, professional practices, or medical treatment may become necessary. Practitioners and researchers must always rely on their own experience and knowledge in evaluating and using any information, methods, compounds, or experiments described herein.
In using such information or methods they should be mindful of their own safety and the safety of others, including parties for whom they have a professional responsibility. To the fullest extent of the law, neither the Publisher nor the authors, contributors, or editors, assume any liability for any injury and/or damage to persons or property as a matter of products liability, negligence or otherwise, or from any use or operation of any methods, products, instructions, or ideas contained in the material herein. Library of Congress Cataloging-in-Publication Data Pacheco, Peter S. An introduction to parallel programming / Peter S.20 75–dc22 2010039584 British Library Cataloguing-in-Publication Data A catalogue record for this book is available from the British Library.
For information on all Morgan Kaufmann publications, visit our web site at www.com or www.com Printed in the United States 11 12 13 14 15 10 9 8 7 6 5 4 3 2 1 To the memory of Josephine F. Pacheco This page intentionally left blank Contents Preface. xviii About the Author. xix CHAPTER 1 Why Parallel Computing? .1 Why We Need Ever-Increasing Performance .2 Why We’re Building Parallel Systems .3 Why We Need to Write Parallel Programs .4 How Do We Write Parallel Programs? .5 What We’ll Be Doing .6 Concurrent, Parallel, Distributed .7 The Rest of the Book .8 A Word of Warning.
12 CHAPTER 2 Parallel Hardware and Parallel Software .1 The von Neumann architecture .2 Processes, multitasking, and threads .2 Modifications to the von Neumann Model .1 The basics of caching.3 Caches and programs: an example .5 Instruction-level parallelism .5 Shared-memory versus distributed-memory .2 Coordinating the processes/threads.5 Programming hybrid systems .5 Input and Output .1 Speedup and efficiency .7 Parallel Program Design .8 Writing and Running Parallel Programs .4 Input and output .6 Parallel program design. 77 CHAPTER 3 Distributed-Memory Programming with MPI .1 Compilation and execution.3 MPI Init and MPI Finalize .4 Communicators, MPI Comm size and MPI Comm rank .10 The status p argument .11 Semantics of MPI Send and MPI Recv .12 Some potential pitfalls .2 The Trapezoidal Rule in MPI .1 The trapezoidal rule .2 Parallelizing the trapezoidal rule .1 Tree-structured communication. point-to-point communications .5 MPI Derived Datatypes .6 Performance Evaluation of MPI Programs.3 Speedup and efficiency .7 A Parallel Sorting Algorithm .1 Some simple serial sorting algorithms .2 Parallel odd-even transposition sort .3 Safety in MPI programs .4 Final details of parallel odd-even sort. 147 CHAPTER 4 Shared-Memory Programming with Pthreads .1 Processes, Threads, and Pthreads .3 Starting the threads .4 Running the threads .5 Stopping the threads .7 Other approaches to thread startup .3 Matrix-Vector Multiplication .7 Producer-Consumer Synchronization and Semaphores.8 Barriers and Condition Variables .1 Busy-waiting and a mutex .9 Read-Write Locks .1 Linked list functions .2 A multi-threaded linked list .3 Pthreads read-write locks .4 Performance of the various implementations .5 Implementing read-write locks .10 Caches, Cache Coherence, and False Sharing .1 Incorrect programs can produce correct output.
206 CHAPTER 5 Shared-Memory Programming with OpenMP .1 Compiling and running OpenMP programs.2 The Trapezoidal Rule .1 A first OpenMP version .3 Scope of Variables .4 The Reduction Clause .5 The parallel for Directive .3 Finding loop-carried dependences .5 More on scope .6 More About Loops in OpenMP: Sorting .2 Odd-even transposition sort .1 The schedule clause .2 The static schedule type .3 The dynamic and guided schedule types.4 The runtime schedule type .8 Producers and Consumers .7 The atomic directive .8 Critical sections and locks .9 Using locks in the message-passing program .10 critical directives, atomic directives, or locks? .9 Caches, Cache Coherence, and False Sharing .1 Incorrect programs can produce correct output. 267 CHAPTER 6 Parallel Program Development .1 Two n-Body Solvers .2 Two serial programs .3 Parallelizing the n-body solvers .5 Parallelizing the basic solver using OpenMP .6 Parallelizing the reduced solver using OpenMP .7 Evaluating the OpenMP codes .8 Parallelizing the solvers using pthreads .9 Parallelizing the basic solver using MPI .10 Parallelizing the reduced solver using MPI .11 Performance of the MPI solvers .1 Recursive depth-first search.2 Nonrecursive depth-first search .3 Data structures for the serial implementations .4 Performance of the serial implementations .5 Parallelizing tree search .6 A static parallelization of tree search using pthreads .7 A dynamic parallelization of tree search using pthreads .8 Evaluating the pthreads tree-search programs .9 Parallelizing the tree-search programs using OpenMP .10 Performance of the OpenMP implementations .11 Implementation of tree search using MPI and static partitioning .12 Implementation of tree search using MPI and dynamic partitioning .3 A Word of Caution .1 Pthreads and OpenMP. 350 CHAPTER 7 Where to Go from Here. 361 Preface Parallel hardware has been ubiquitous for some time now.
It’s difficult to find a lap- top, desktop, or server that doesn’t use a multicore processor. Beowulf clusters are nearly as common today as high-powered workstations were during the 1990s, and cloud computing could make distributed-memory systems as accessible as desktops. In spite of this, most computer science majors graduate with little or no experience in parallel programming. Many colleges and universities offer upper-division elective courses in parallel computing, but since most computer science majors have to take numerous required courses, many graduate without ever writing a multithreaded or multiprocess program.
It seems clear that this state of affairs needs to change. Although many programs can obtain satisfactory performance on a single core, computer scientists should be made aware of the potentially vast performance improvements that can be obtained with parallelism, and they should be able to exploit this potential when the need arises. An Introduction to Parallel Programming was written to partially address this problem. It provides an introduction to writing parallel programs using MPI, Pthreads, and OpenMP—three of the most widely used application programming interfaces (APIs) for parallel programming.
The intended audience is students and professionals who need to write parallel programs. The prerequisites are mini- mal: a college-level course in mathematics and the ability to write serial programs in C. They are minimal because we believe that students should be able to start programming parallel systems as early as possible. At the University of San Francisco, computer science students can fulfill a requirement for the major by taking the course, on which this text is based, immedi- ately after taking the “Introduction to Computer Science I” course that most majors take in the first semester of their freshman year.
We’ve been offering this course in parallel computing for six years now, and it has been our experience that there really is no reason for students to defer writing parallel programs until their junior or senior year. To the contrary, the course is popular, and students have found that using concurrency in other courses is much easier after having taken the Introduction course. If second-semester freshmen can learn to write parallel programs by taking a class, then motivated computing professionals should be able to learn to write paral- lel programs through self-study. We hope this book will prove to be a useful resource for them.
About This Book As we noted earlier, the main purpose of the book is to teach parallel programming in MPI, Pthreads, and OpenMP to an audience with a limited background in computer science and no previous experience with parallelism. We also wanted to make it as xv xvi Preface flexible as possible so that readers who have no interest in learning one or two of the APIs can still read the remaining material with little effort. Thus, the chapters on the three APIs are largely independent of each other: they can be read in any order, and one or two of these chapters can be bypass. This independence has a cost: It was necessary to repeat some of the material in these chapters.
Of course, repeated material can be simply scanned or skipped. Readers with no prior experience with parallel computing should read Chapter 1 first. It attempts to provide a relatively nontechnical explanation of why parallel sys- tems have come to dominate the computer landscape.