Thomas Rauber Gudula Rünger Parallel Programming for Multicore and Cluster Systems Second Edition Parallel Programming Thomas Rauber Gudula Rünger • Parallel Programming for Multicore and Cluster Systems Second Edition 123 ThomasRauber Gudula Rünger Computer Science Department Computer Science Department Universityof Bayreuth ChemnitzUniversity ofTechnology Bayreuth Chemnitz Germany Germany ISBN 978-3-642-37800-3 ISBN 978-3-642-37801-0 (eBook) DOI 10.1007/978-3-642-37801-0 SpringerHeidelbergNewYorkDordrechtLondon LibraryofCongressControlNumber:2013936950 ExtendedEnglishlanguagetranslationfromtheGermanlanguageedition:ParalleleProgrammierung (3rdedn.)byT.RauberandG.Rünger. (cid:2)Springer-VerlagBerlinHeidelberg2007,2012 ACMComputingClassification(1998):D.1,C.1,C.2,C.4 (cid:2)Springer-VerlagBerlinHeidelberg2010,2013 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation,broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionor informationstorageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilar methodology now known or hereafter developed. Exempted from this legal reservation are brief excerpts in connection with reviews or scholarly analysis or material supplied specifically for the purposeofbeingenteredandexecutedonacomputersystem,forexclusiveusebythepurchaserofthe work. Duplication of this publication or parts thereof is permitted only under the provisions of theCopyright Law of the Publisher’s location, in its current version, and permission for use must always be obtained from Springer. Permissions for use may be obtained through RightsLink at the CopyrightClearanceCenter.ViolationsareliabletoprosecutionundertherespectiveCopyrightLaw. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publicationdoesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexempt fromtherelevantprotectivelawsandregulationsandthereforefreeforgeneraluse. While the advice and information in this book are believed to be true and accurate at the date of publication,neithertheauthorsnortheeditorsnorthepublishercanacceptanylegalresponsibilityfor anyerrorsoromissionsthatmaybemade.Thepublishermakesnowarranty,expressorimplied,with respecttothematerialcontainedherein. Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) Preface Innovationsinhardwarearchitecture,likehyper-threadingormulticoreprocessors, make parallel computing resources available for inexpensive desktop computers. However, the use of these innovations requires parallel programming techniques. In a few years, many standard software products will be based on concepts of parallelprogrammingtousethehardwareresourcesoffuturemulticoreprocessors efficiently. Thus, the need for parallel programming will extend to all areas of software development. The application area will be much larger than the area of scientific computing, which used to be the main area for parallel computing for a manyyears.Theexpansionoftheapplicationareaforparallelcomputingwilllead to an enormous need for software developers with parallel programming skills. Some chip manufacturers already demand to include parallel programming as a standard course in computer science curricula. A more recent trend is the use of Graphics Processing Units (GPUs) comprising several hundreds of cores to execute compute-intensive non-graphics applications. This book takes up the new development in processor architecture by giving a detailed description of important parallel programming techniques that are nec- essary for developing efficient programs for multicore processors as well as for parallel cluster systems or supercomputers. Both shared and distributed address space architectures are covered. The main goal of the book is to present parallel programmingtechniquesthatcanbeusedinmanysituationsformanyapplication areas and to enable the reader to develop correct and efficient parallel programs. Many example programs and exercises are provided to support this goal and to show how the techniques can be applied to further applications. The book can be used both a textbook for students and a reference book for professionals. The materialofthebookhasbeenusedforcoursesinparallelprogrammingatdifferent universities for many years. ThissecondeditionoftheEnglishbookonparallelprogrammingisanupdated and revised version based on the third edition of the German versionof this book from 2012. The two earlier German editions appeared in 2000 and 2007, respectively. The update of this new English edition includes a new chapter on v vi Preface general purpose GPUs and the corresponding programming techniques. The remaining chapters have been revised carefully. Especially the chapter on the architecture of parallel systems has been updated considerably putting a larger emphasisonthearchitectureofmulticoresystemsandaddingnewmaterialonthe recent development in computer architecture. The content of the book comprises of three main parts, covering all areas of parallel computing: the architecture of parallel systems, parallel programming models and environments, and the implementation of efficient application algo- rithms.Theemphasisliesonparallelprogrammingtechniquesneededfordifferent architectures. The first part contains an overview of the architecture of parallel systems, including cache and memory organization, interconnection networks, routing and switching techniques, as well as technologies that are relevant for modern and future multicore processors. The second part presents parallel programming models, performance models, and parallel programming environments for message passing and shared memory models, including MPI, Pthreads, Java threads, and OpenMP. For each of these parallelprogrammingenvironments,thebookgivesbasicconceptsaswellasmore advanced programming methods and enables the reader to write and run seman- tically correct and efficient parallel programs. Parallel design patterns like pipe- lining, client–server, or task pools are presented for different environments to illustrate parallel programming techniques and to facilitate the implementation of efficient parallel programs for a wide variety of application areas. Performance models and techniques for runtime analysis are described in detail, as they are a prerequisiteforachievingefficiencyandhighperformance.Anewchaptergivesa detailed description ofthe architecture ofGPUs and also containsan introduction into programming approaches for general purpose GPUs concentrating on CUDA and OpenCL. Programming examples are provided to demonstrate the use of the specific programming techniques introduced. The third part applies the programming techniques from the second part to representative algorithms from scientific computing. The emphasis lies on basic methods for solving linear equation systems, which play an important role for many scientific simulations. The focus of the presentation lies on the analysis of the algorithmic structure of the different algorithms, which is the basis for a parallelization, and not on mathematical properties of the solution methods. For eachalgorithm,thebookdiscussesdifferentparallelizationvariants,usingdifferent methods and strategies. Manycolleaguesandstudentshavehelpedtoimprovethequalityofthisbook. We would like to thank all of them for their help and constructive criticisms. For numerous corrections we would like to thank Jörg Dümmler, Marvin Ferber, Michael Hofmann, Ralf Hoffmann, Sascha Hunold, Matthias Korch, Raphael Kunis, Jens Lang, John O’Donnell, Andreas Prell, Carsten Scholtes, Michael Preface vii Schwind, and Jesper Träff. Many thanks to Matthias Korch, Carsten Scholtes and Michael Schwind for their help with the exercises. We thank Monika Glaser and Luise Steinbachfor their help andsupportwith the typesettingofthe book. We also thank all the people who have been involved in the writing of the three Germanversionsofthisbook.IthasbeenapleasureworkingwithSpringer-Verlag in the development of this book. We especially thank Ralf Gerstner for his con- tinuous support. Bayreuth, March 2013 Thomas Rauber Chemnitz, March 2013 Gudula Rünger Contents 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Classical Use of Parallelism . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Parallelism in Today’s Hardware. . . . . . . . . . . . . . . . . . . . . . 2 1.3 Basic Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Overview of the Book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Parallel Computer Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.1 Processor Architecture and Technology Trends . . . . . . . . . . . . 9 2.2 Flynn’s Taxonomy of Parallel Architectures . . . . . . . . . . . . . . 13 2.3 Memory Organization of Parallel Computers. . . . . . . . . . . . . . 14 2.3.1 Computers with Distributed Memory Organization. . . . 15 2.3.2 Computers with Shared Memory Organization. . . . . . . 18 2.3.3 Reducing memory access times. . . . . . . . . . . . . . . . . 20 2.4 Thread-Level Parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.4.1 Simultaneous Multithreading. . . . . . . . . . . . . . . . . . . 24 2.4.2 Energy Consumption of Processors . . . . . . . . . . . . . . 25 2.4.3 Multicore Processors . . . . . . . . . . . . . . . . . . . . . . . . 26 2.4.4 Architecture of Multicore Processors . . . . . . . . . . . . . 28 2.4.5 Example: Architecture of the Intel Core i7 . . . . . . . . . 32 2.5 Interconnection Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.5.1 Properties of Interconnection Networks. . . . . . . . . . . . 36 2.5.2 Direct Interconnection Networks . . . . . . . . . . . . . . . . 38 2.5.3 Embeddings. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.5.4 Dynamic Interconnection Networks . . . . . . . . . . . . . . 47 2.6 Routing and Switching. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 2.6.1 Routing Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.6.2 Routing in the Omega Network. . . . . . . . . . . . . . . . . 61 2.6.3 Switching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 2.6.4 Flow control mechanisms . . . . . . . . . . . . . . . . . . . . . 71 2.7 Caches and Memory Hierarchy . . . . . . . . . . . . . . . . . . . . . . . 72 2.7.1 Characteristics of Caches . . . . . . . . . . . . . . . . . . . . . 73 2.7.2 Write Policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 2.7.3 Cache coherency . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 ix x Contents 2.7.4 Memory consistency. . . . . . . . . . . . . . . . . . . . . . . . . 91 2.8 Example: IBM Blue Gene supercomputer. . . . . . . . . . . . . . . . 97 2.9 Exercises for Chapter 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 3 Parallel Programming Models . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 3.1 Models for parallel systems. . . . . . . . . . . . . . . . . . . . . . . . . . 105 3.2 Parallelization of programs . . . . . . . . . . . . . . . . . . . . . . . . . . 108 3.3 Levels of parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 3.3.1 Parallelism at instruction level. . . . . . . . . . . . . . . . . . 110 3.3.2 Data parallelism. . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 3.3.3 Loop parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 3.3.4 Functional parallelism. . . . . . . . . . . . . . . . . . . . . . . . 116 3.3.5 Explicit and implicit representation of parallelism . . . . 117 3.3.6 Parallel programming patterns. . . . . . . . . . . . . . . . . . 120 3.4 SIMD Computations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 3.4.1 Execution of vector operations. . . . . . . . . . . . . . . . . . 125 3.4.2 SIMD instructions . . . . . . . . . . . . . . . . . . . . . . . . . . 127 3.5 Data distributions for arrays . . . . . . . . . . . . . . . . . . . . . . . . . 128 3.5.1 Data distribution for one-dimensional arrays. . . . . . . . 129 3.5.2 Data distribution for two-dimensional arrays. . . . . . . . 130 3.5.3 Parameterized data distribution . . . . . . . . . . . . . . . . . 132 3.6 Information exchange. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 3.6.1 Shared variables. . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 3.6.2 Communication operations . . . . . . . . . . . . . . . . . . . . 134 3.7 Parallel matrix-vector product . . . . . . . . . . . . . . . . . . . . . . . . 141 3.7.1 Parallel computation of scalar products. . . . . . . . . . . . 142 3.7.2 Parallel computation of the linear combinations. . . . . . 145 3.8 Processes and Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 3.8.1 Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 3.8.2 Threads. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 3.8.3 Synchronization mechanisms. . . . . . . . . . . . . . . . . . . 152 3.8.4 Developing efficient and correct thread programs . . . . 156 3.9 Further parallel programming approaches . . . . . . . . . . . . . . . . 158 3.9.1 Approaches for new parallel languages. . . . . . . . . . . . 159 3.9.2 Transactional memory . . . . . . . . . . . . . . . . . . . . . . . 161 3.10 Exercices for Chapter 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 4 Performance Analysis of Parallel Programs . . . . . . . . . . . . . . . . . 169 4.1 Performance Evaluation of Computer Systems. . . . . . . . . . . . . 170 4.1.1 Evaluation of CPU Performance . . . . . . . . . . . . . . . . 170 4.1.2 MIPS and MFLOPS. . . . . . . . . . . . . . . . . . . . . . . . . 172 4.1.3 Performance of Processors with a Memory Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 4.1.4 Benchmark Programs . . . . . . . . . . . . . . . . . . . . . . . . 176 Contents xi 4.2 Performance Metrics for Parallel Programs. . . . . . . . . . . . . . . 179 4.2.1 Speedup and Efficiency . . . . . . . . . . . . . . . . . . . . . . 180 4.2.2 Scalability of Parallel Programs. . . . . . . . . . . . . . . . . 183 4.3 Asymptotic Times for Global Communication. . . . . . . . . . . . . 184 4.3.1 Implementing Global Communication Operations . . . . 186 4.3.2 Communications Operations on a Hypercube. . . . . . . . 191 4.4 Analysis of Parallel Execution Times. . . . . . . . . . . . . . . . . . . 199 4.4.1 Parallel Scalar Product . . . . . . . . . . . . . . . . . . . . . . . 199 4.4.2 Parallel Matrix-vector Product. . . . . . . . . . . . . . . . . . 201 4.5 Parallel Computational Models . . . . . . . . . . . . . . . . . . . . . . . 203 4.5.1 PRAM Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204 4.5.2 BSP Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 4.5.3 LogP Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 4.6 Loop Scheduling and Loop Tiling . . . . . . . . . . . . . . . . . . . . . 211 4.6.1 Loop Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 4.6.2 Loop Tiling. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 4.7 Exercises for Chapter 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 5 Message-Passing Programming. . . . . . . . . . . . . . . . . . . . . . . . . . . 227 5.1 Introduction to MPI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 5.1.1 MPI point-to-point communication. . . . . . . . . . . . . . . 230 5.1.2 Deadlocks with Point-to-point Communications. . . . . . 234 5.1.3 Nonblocking Operations and Communication Modes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 5.1.4 Communication mode. . . . . . . . . . . . . . . . . . . . . . . . 241 5.2 Collective Communication Operations . . . . . . . . . . . . . . . . . . 243 5.2.1 Collective Communication in MPI. . . . . . . . . . . . . . . 243 5.2.2 Deadlocks with Collective Communication. . . . . . . . . 256 5.3 Process Groups and Communicators. . . . . . . . . . . . . . . . . . . . 258 5.3.1 Process Groups in MPI. . . . . . . . . . . . . . . . . . . . . . . 259 5.3.2 Process Topologies. . . . . . . . . . . . . . . . . . . . . . . . . . 264 5.3.3 Timings and aborting processes. . . . . . . . . . . . . . . . . 268 5.4 Introduction to MPI-2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269 5.4.1 Dynamic Process Generation and Management . . . . . . 269 5.4.2 One-sided communication. . . . . . . . . . . . . . . . . . . . . 272 5.5 Exercises for Chapter 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281 6 Thread Programming. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287 6.1 Programming with Pthreads. . . . . . . . . . . . . . . . . . . . . . . . . . 287 6.1.1 Creating and Merging Threads. . . . . . . . . . . . . . . . . . 289 6.1.2 Thread Coordination with Pthreads . . . . . . . . . . . . . . 293 6.1.3 Condition Variables . . . . . . . . . . . . . . . . . . . . . . . . . 298 6.1.4 Extended Lock Mechanism. . . . . . . . . . . . . . . . . . . . 304 6.1.5 One-Time Initialization. . . . . . . . . . . . . . . . . . . . . . . 306 6.1.6 Implementation of a Task Pool . . . . . . . . . . . . . . . . . 307