PRINCIPLES OF PARALLEL PROGRAMMING Calvin Lin Department of Computer Sciences The University of Texas at Austin Lawrence Snyder Department of Computer Science and Engineering University of Washington, Seattle ▲ Boston San Francisco New York London Toronto Sydney Tokyo Singapore Madrid Mexico City Munich Paris Cape Town Hong Kong Montreal Executive Editor: Michael Hirsch Acquisition Editor: Matt Goldstein Editorial Assistant: Sarah Milmore Senior Production Supervisor: Marilyn Lloyd Text Designer: Gillian Hall Cover Designer: Barbara T. Atkinson Cover Image: Flip Nicklin/Hinden Pictures (Orca whales) Media Producer: Bethany Tidd Senior Media Buyer: Ginny Michaud Marketing Manager: Christopher Kelly Senior Manufacturing Buyer: Carol Melville Production Services: Gillian Hall, TheAardvark Group Publishing Services Illustrations: Donna Ellison Copyeditor: Kathleen Cantwell, C4 Technologies Proofreader: Holly McLean-Aldis Indexer: Jack Lewis Access the latest information about Addison-Wesley titles from our World Wide Web site: http://www.aw.com/computing Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in this book, and Addison-Wesley was aware of a trademark claim, the designations have been printed in initial caps or all caps. The programs and applications presented in this book have been included for their instructional value. They have been tested with care but are not guaranteed for any particular purpose. The publisher does not offer any warranty or representation, nor does it accept any liabilities with respect to the programs or applications. Library of Congress Cataloging-in-Publication Data Snyder, Lawrence. Parallel programming / Lawrence Snyder, Calvin Lin. — 1st ed. p. cm. ISBN 978-0-321-53134-6 1. Parallel programming (Computer science) I. Lin, Calvin. II. Title. QA76.642.S667 2008 005.2'75—dc22 2008000970 Copyright © 2009 Pearson Education, Inc. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior written permission of the publisher. Printed in the United States of America. For information on obtaining permission for use of material in this work, please submit a written request to Pearson Education, Inc., Rights and Contracts Department, 501 Boylston Street, Suite 900, Boston, MA 02116, fax your request to 617-671-3447, or e-mail at http://www.pearsoned.com/legal/permissions.htm. ISBN-13:9780321487902 ISBN-10:0-321-48790-7 123456789 10—CRW—11 10 09 08 To Mom and Dad (Josette and Min Shuey) To Julie, Dave, and Dan Preface Welcome! For readers who are motivated by the advent of multi-core chips to learn parallel programming, you’ve come to the right place. This book is written for a world in which parallel computers are everywhere, ranging from laptops with two-core chips to supercomputers to huge data-center clusters that index the Internet. This book focuses on scalable parallelism, that is, the ability of a parallel program to run well on any number of processors. This notion is critical for two reasons: (1) Most of the techniques needed to create scalable parallel computations are the same techniques that produce efficient solutions on a multi-core chip, and (2) while multi-core chips currently have a modest number of processors, typically 2-8, the number of cores per chip promises to increase dramatically in the coming years, making the notion of scalable parallelism directly relevant. Thus, while today’s multi-core chips offer opportunities for low latency communication among cores, this characteristic is likely a short-term advantage, as on-chip delays to different parts of the chip will become increasingly apparent as the number of cores grows. So, we focus not on exploiting such short-term advantages, but on emphasizing approaches that work well now and in the future. Of course, multi-core chips present their own challenges, particularly with their limited bandwidth to off-chip memory and their limited aggregate on-chip cache. This book discusses these issues as well. First, we discuss the principles that underlie effective and efficient parallel pro grams. Learning the principles is essential to acquiring any capability as sophisti cated as programming, of course, but principles are perhaps even more important for parallel programming because the state of the art changes rapidly. Training that is tied too closely to a specific computer or language will not have the staying power needed to keep pace with advancing technology. But the principles—concepts that apply to any parallel computing system and ideas that exploit these features—lead to an understanding that is timeless and knowledge that will always be applicable. But we do more than discuss abstract concepts. We also apply those principles to everyday computations, which makes the book very practical. We introduce several parallel programming systems, and we describe how to apply the principles in those IV Preface programming systems. On completion, we expect readers to be able to write paral lel programs. Indeed, the final chapter is devoted to parallel programming tech niques and the development of a term-long parallel programming capstone project. Audience Our intended audience is anyone—students or professionals—who has written suc cessful programs in C or similar languages and who describes himself as a program mer. It is helpful to have a basic idea of how a computer executes sequential programs, including knowledge of the fetch/execute cycle and basics of caching. This book was originally targeted to upper level undergraduate computer science majors or first year graduate students with a CS undergraduate degree, and it con tinues to be appropriate for that level. However, as the book evolved, we reduced the assumed knowledge and emphasized pedagogy in the belief that if some explana tions cover knowledge the reader already has, it’s easy to skip forward. Organization Because parallel programming is not a direct extension of sequential programming with which the reader is doubtless familiar, we have organized this book into four parts: Foundations: Chapters 1-3 Abstractions: Chapters 4-5 Languages: Chapters 6-9 Looking Forward: Chapters 10-11 To enable you to select intelligently from these parts, we now explain their goals and content. Foundations. In Chapter 1 we discover the many issues that parallel program mers must address by showing how difficult it is to implement a computation that is trivial when written for sequential computers. The example focuses our attention on issues that concern us throughout the entire book, but it also emphasizes the importance of understanding how a parallel computer operates. Chapter 2 intro duces five different types of parallel computers, giving a few details about their architecture and their ability to scale to a larger size. There are two key conclusions from the chapter: First, unlike sequential computing, there is no standard architec ture. Second, to be successful at spanning this architectural diversity we need an abstract machine model to guide our programming. And we give one. With the architectures in mind, Chapter 3 covers basic ideas of concurrency, including threads and processes, latency, bandwidth, speedup, and so forth, with an emphasis on issues related to performance. These foundations of Part 1 prepare us for an exploration of algorithms and abstractions. VI Preface Abstractions. As an aid to designing and discussing parallel algorithms, Chapter 4 introduces an informal pseuodcode notation for writing parallel programs in a language-independent way. The notation has a variety of features that span various programming models and approaches, allowing us to discuss algorithms without bias toward any particular language or machine. To bootstrap your thinking about parallel algorithms, Chapter 5 covers a series of basic algorithmic techniques. By the end of Part 2, you should be able to conceptualize ways to solve a problem in paral lel, bringing us to the final issue of encoding your algorithms in a concrete parallel programming language. Languages. There is no single parallel programming language that fulfills the role that, say, C or Java plays in sequential programming, that is, a language widely known and accepted as a baseline medium to encode algorithms. As a result, Part 3 introduces three kinds of parallel programming languages: thread-based (Chapter 6), message-passing (Chapter 7), and high-level (Chapter 8). We cover each lan guage well enough for you to write small exercises; serious computations require a more complete language introduction that is available through online resources. In addition to introducing a language, each chapter includes a brief overview of related languages that have a following in the parallel programming community. Chapter 9 briefly compares and contrasts all of the languages presented, noting their strengths and weaknesses. There is benefit to reading all three chapters, but we realize that many readers will focus on one approach, so these chapters are independent of one another. Onward. Part 4 looks to the future. Chapter 10 covers a series of new, promising parallel technologies that will doubtless impact future research and practice. In our view, they are not quite “ready for prime time,” but they are important and worth becoming familiar with even before they are fully deployed. Finally, Chapter 11 focuses on hands-on techniques for programming parallel machines. The first two sections of the chapter can be read early in your study of parallel programming, per haps together with your study of abstractions in Chapters 4 and 5. But the main goal of the chapter is to assist you in writing a substantial program as a capstone design project. In this capacity we assume that you will return to Chapter 11 repeatedly. Using This Book Although the content is presented in a logical order, it is not necessary to read this book front to back. Indeed, in a one term course, it may be sensible to begin pro gramming exercises before all of the topics have been introduced. We see the follow ing as a sensible general plan: ■ Chapters 1,2 ■ Chapter 11 first section, Chapter 3 through Performance Tradeoffs; begin programming exercises ■ Chapters 4,5 ■ One of Chapters 6-8, programming language chapters ■ Complete Chapter 3 and 11, begin term project ■ Complete remaining chapters in order: language chapters, Chapters 9,10 There is, of course, no harm in reading the book straight through, but the advantage of this approach is that the reading and programming can proceed in parallel. Acknowledgments Sincere thanks are due to E Christopher Lewis and Robert van de Geijn, who cri tiqued an early draff of this book. Thanks also to the following reviewers for their valuable feedback and suggestions: David Bader, Georgia Institute of Technology Purushotham Bangalore, University of Alabama, Birmingham John Cavazos, University of Delaware Sandhya Dwarkadas, University of Rochester John Gilbert, UC Santa Barbara Robert Henry, Cray Inc. E Christopher Lewis, VMWare Kai Li, Princeton Glenn Reinman, UCLA Darko Stefanovic, University of New Mexico We thank Karthik Murthy and Brandon Plost for their assistance in writing and running parallel programs and for finding bugs in the text, and we are grateful to Bobby Blumofe, whose early collaborations on a multi-threaded programming course are evident in many places in the book. We recognize and thank the students of the Parallel Programming Environments Seminar (CSE590o) at the University of Washington in autumn quarter, 2006 for their contributions to the text: Ivan Beschastnikh, Alex Colburn, Roxana Geambasu, Sangyun Hahn, Ethan Katz- Bassett, Nathan Kuchta, Harsha Madhyastha, Marianne Shaw, Brian Van Essen, and Benjamin Ylvisaker. Other contributors are Sonja Keserovic, Kate Moore, Brad Chamberlain, Steven Deitz, Dan Grossman, Jeff Diamond, Don Fussell, Bill Mark, and David Mohr. We would like to thank our editor, Matt Goldstein, and the Addison Wesley team: Sarah Milmore, Marilyn Lloyd, Barbara Atkinson, Joyce Wells, and Chris Kelly. Thanks to Gillian Hall who has been especially tolerant of our antics. Finally, we thank our families for their patience through the writing of this book. Calvin Lin Lawrence Snyder February 2008 Contents PART 1 Chapter Summary 27 Foundations Historical Perspective 28 1 Exercises 28 Chapter 1 Chapter 2 Introduction 1 Understanding Parallel The Power and Potential of Parallelism 2 Computers 30 Parallelism, a Familiar Concept 2 Balancing Machine Specifics Parallelism in Computer Programs 3 with Portability 30 Multi-Core Computers, an Opportunity 4 Even More Opportunities to Use Parallel A Look at Six Parallel Computers 31 Hardware 5 Chip Multiprocessors 31 Parallel Computing versus Distributed Symmetric Multiprocessor Architectures 34 Computing 6 Heterogeneous Chip Designs 36 System Level Parallelism 6 Clusters 39 Convenience of Parallel Abstractions 8 Supercomputers 40 Observations from Our Six Examining Sequential and Parallel Parallel Computers 43 Programs 8 Parallelizing Compilers 8 An Abstraction of a Sequential Computer 44 A Paradigm Shift 9 Applying the RAM Model 44 Parallel Prefix Sum 13 Evaluating the RAM Model 45 Parallelism Using Multiple Instruction The PRAM: A Parallel Computer Model 46 Streams 15 The Concept of a Thread 15 The CTA: A Practical Parallel A Multithreaded Solution to Counting 3s 15 Computer Model 47 The CTA Model 47 The Goals: Scalability and Performance Communication Latency 49 Portability 25 Properties of the CTA 52 Scalability 25 Performance Portability 26 Memory Reference Mechanisms 53 Principles First 27 Shared Memory 53 VIII ix One-Sided Communication 54 Implications for Hardware 82 Message Passing 54 Implications for Software 83 Memory Consistency Models 55 Scaling the Problem Size 83 Programming Models 56 Chapter Summary 84 A Closer Look at Communication 57 Historical Perspective 84 Exercises 85 Applying the CTA Model 58 Chapter Summary 59 Historical Perspective 59 Exercises 59 PART 2 Parallel Abstractions 87 Chapter 3 Reasoning about Performance 61 Chapter 4 First Steps Toward Parallel Motivation and Basic Concepts 61 Parallelism versus Performance 61 Programming 88 Threads and Processes 62 Data and Task Parallelism 88 Latency and Throughput 62 Definitions 88 Sources of Performance Loss 64 Illustrating Data and Task Parallelism 89 Overhead 64 The Peril-L Notation 89 Non-Parallelizable Code 65 Extending C 90 Contention 67 Parallel Threads 90 Idle Time 67 Synchronization and Coordination 91 Parallel Structure 68 Memory Model 92 Dependences 68 Synchronized Memory 94 Dependences Limit Parallelism 70 Reduce and Scan 95 Granularity 72 The Reduce Abstraction 96 Locality 73 Count 3s Example 97 Performance Trade-Offs 73 Formulating Parallelism 97 Communication versus Computation 74 Fixed Parallelism 97 Memory versus Parallelism 75 Unlimited Parallelism 98 Overhead versus Parallelism 75 Scalable Parallelism 99 Measuring Performance 77 Alphabetizing Example 100 Execution Time 77 Unlimited Parallelism 101 Speedup 78 Fixed Parallelism 102 Superlinear Speedup 78 Scalable Parallelism 104 Efficiency 79 Concerns with Speedup 79 Comparing the Three Solutions 109 Scaled Speedup versus Fixed-Size Speedup 81 Chapter Summary 110 Scalable Performance 81 Historical Perspective 110 Scalable Performance Is Difficult to Achieve 81 Exercises 110 Contents Chapter 5 Mutual Exclusion 150 Scalable Algorithmic Synchronization 153 Safety Issues 163 Techniques 112 Performance Issues 167 Blocks of Independent Computation 112 Case Study: Successive Over-Relaxation 174 Case Study: Overlapping Synchronization Schwartz’ Algorithm 113 with Computation 179 The Reduce and Scan Abstractions 115 Case Study: Streaming Computations Example of Generalized Reduces on a Multi-Core Chip 187 and Scans 116 The Basic Structure 118 Java Threads 187 Structure for Generalized Reduce 119 Synchronized Methods 189 Example of Components Synchronized Statements 189 of a Generalized Scan 122 The Count 3s Example 190 Applying the Generalized Scan 124 Volatile Memory 192 Generalized Vector Operations 125 Atomic Objects 192 Lock Objects 193 Assigning Work to Processes Statically 125 Executors 193 Block Allocations 126 Concurrent Collections 193 Overlap Regions 128 Cyclic and Block Cyclic Allocations 129 OpenMP 193 Irregular Allocations 132 The Count 3s Example 194 Semantic Limitations on parallel for 195 Assigning Work to Processes Reduction 196 Dynamically 134 Thread Behavior and Interaction 197 Work Queues 134 Sections 199 Variations of Work Queues 137 Summary of OpenMP 199 Case Study: Concurrent Memory Allocation 137 Chapter Summary 200 Historical Perspective 200 Trees 139 Exercises 200 Allocation by Sub-Tree 139 Dynamic Allocations 140 Chapter 7 Chapter Summary 141 MPI and Other Local View Historical Perspective 142 Exercises 142 Languages 202 MPI: The Message Passing Interface 202 PART 3 The Count 3s Example 203 Parallel Programming Groups and Communicators 211 Point-to-Point Communication 212 Languages 143 Collective Communication 214 Example: Successive Over-Relaxation 219 Chapter 6 Performance Issues 222 Programming with Threads 145 Safety Issues 228 POSIX Threads 145 Partitioned Global Address Space Thread Creation and Destruction 146 Languages 229