book

Introduction to Parallel Computing, Second Edition

by Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar

January 2003

Intermediate to advanced

656 pages

19h 8m

English

Addison-Wesley Professional

Read now

Unlock full access

Dedication
1.1. Motivating Parallelism1.1.1. The Computational Power Argument – from Transistors to FLOPS1.1.2. The Memory/Disk Speed Argument1.1.3. The Data Communication Argument1.2. Scope of Parallel Computing1.2.1. Applications in Engineering and Design1.2.2. Scientific Applications1.2.3. Commercial Applications1.2.4. Applications in Computer Systems1.3. Organization and Contents of the Text1.4. Bibliographic RemarksProblems
2.1. Implicit Parallelism: Trends in Microprocessor Architectures*2.1.1. Pipelining and Superscalar Execution2.1.2. Very Long Instruction Word Processors2.2. Limitations of Memory System Performance*2.2.1. Improving Effective Memory Latency Using Caches2.2.2. Impact of Memory Bandwidth2.2.3. Alternate Approaches for Hiding Memory LatencyMultithreading for Latency HidingPrefetching for Latency Hiding2.2.4. Tradeoffs of Multithreading and Prefetching2.3. Dichotomy of Parallel Computing Platforms2.3.1. Control Structure of Parallel Platforms2.3.2. Communication Model of Parallel PlatformsShared-Address-Space PlatformsMessage-Passing Platforms2.4. Physical Organization of Parallel Platforms2.4.1. Architecture of an Ideal Parallel ComputerArchitectural Complexity of the Ideal Model2.4.2. Interconnection Networks for Parallel Computers2.4.3. Network TopologiesBus-Based NetworksCrossbar NetworksMultistage NetworksCompletely-Connected NetworkStar-Connected NetworkLinear Arrays, Meshes, and k-d MeshesTree-Based Networks2.4.4. Evaluating Static Interconnection Networks2.4.5. Evaluating Dynamic Interconnection Networks2.4.6. Cache Coherence in Multiprocessor SystemsSnoopy Cache SystemsDirectory Based Systems2.5. Communication Costs in Parallel Machines2.5.1. Message Passing Costs in Parallel ComputersStore-and-Forward RoutingPacket RoutingCut-Through RoutingA Simplified Cost Model for Communicating Messages2.5.2. Communication Costs in Shared-Address-Space Machines2.6. Routing Mechanisms for Interconnection Networks2.7. Impact of Process-Processor Mapping and Mapping Techniques2.7.1. Mapping Techniques for GraphsEmbedding a Linear Array into a HypercubeEmbedding a Mesh into a HypercubeEmbedding a Mesh into a Linear ArrayEmbedding a Hypercube into a 2-D MeshProcess-Processor Mapping and Design of Interconnection Networks2.7.2. Cost-Performance Tradeoffs2.8. Bibliographic RemarksProblems
3.1. Preliminaries3.1.1. Decomposition, Tasks, and Dependency Graphs3.1.2. Granularity, Concurrency, and Task-Interaction3.1.3. Processes and Mapping3.1.4. Processes versus Processors3.2. Decomposition Techniques3.2.1. Recursive Decomposition3.2.2. Data Decomposition3.2.3. Exploratory Decomposition3.2.4. Speculative Decomposition3.2.5. Hybrid Decompositions3.3. Characteristics of Tasks and Interactions3.3.1. Characteristics of Tasks3.3.2. Characteristics of Inter-Task Interactions3.4. Mapping Techniques for Load Balancing3.4.1. Schemes for Static MappingMappings Based on Data PartitioningBlock DistributionsCyclic and Block-Cyclic DistributionsRandomized Block DistributionsMappings Based on Task PartitioningHierarchical Mappings3.4.2. Schemes for Dynamic MappingCentralized SchemesDistributed SchemesSuitability to Parallel Architectures3.5. Methods for Containing Interaction Overheads3.5.1. Maximizing Data Locality3.5.2. Minimizing Contention and Hot Spots3.5.3. Overlapping Computations with Interactions3.5.4. Replicating Data or Computations3.5.5. Using Optimized Collective Interaction Operations3.5.6. Overlapping Interactions with Other Interactions3.6. Parallel Algorithm Models3.6.1. The Data-Parallel Model3.6.2. The Task Graph Model3.6.3. The Work Pool Model3.6.4. The Master-Slave Model3.6.5. The Pipeline or Producer-Consumer Model3.6.6. Hybrid Models3.7. Bibliographic RemarksProblems
4.1. One-to-All Broadcast and All-to-One Reduction4.1.1. Ring or Linear Array4.1.2. Mesh4.1.3. Hypercube4.1.4. Balanced Binary Tree4.1.5. Detailed Algorithms4.1.6. Cost Analysis4.2. All-to-All Broadcast and Reduction4.2.1. Linear Array and Ring4.2.2. Mesh4.2.3. Hypercube4.2.4. Cost Analysis4.3. All-Reduce and Prefix-Sum Operations4.4. Scatter and Gather4.5. All-to-All Personalized Communication4.5.1. Ring4.5.2. Mesh4.5.3. HypercubeAn Optimal Algorithm4.6. Circular Shift4.6.1. Mesh4.6.2. Hypercube4.7. Improving the Speed of Some Communication Operations4.7.1. Splitting and Routing Messages in PartsOne-to-All BroadcastAll-to-One ReductionAll-Reduce4.7.2. All-Port Communication4.8. Summary4.9. Bibliographic RemarksProblems
5.1. Sources of Overhead in Parallel Programs5.2. Performance Metrics for Parallel Systems5.2.1. Execution Time5.2.2. Total Parallel Overhead5.2.3. Speedup5.2.4. Efficiency5.2.5. Cost5.3. The Effect of Granularity on Performance5.4. Scalability of Parallel Systems5.4.1. Scaling Characteristics of Parallel Programs5.4.2. The Isoefficiency Metric of ScalabilityThe Isoefficiency Function5.4.3. Cost-Optimality and the Isoefficiency Function5.4.4. A Lower Bound on the Isoefficiency Function5.4.5. The Degree of Concurrency and the Isoefficiency Function5.5. Minimum Execution Time and Minimum Cost-Optimal Execution Time5.6. Asymptotic Analysis of Parallel Programs5.7. Other Scalability Metrics5.8. Bibliographic RemarksProblems
6.1. Principles of Message-Passing Programming6.2. The Building Blocks: Send and Receive Operations6.2.1. Blocking Message Passing OperationsBlocking Non-Buffered Send/ReceiveBlocking Buffered Send/Receive6.2.2. Non-Blocking Message Passing Operations6.3. MPI: the Message Passing Interface6.3.1. Starting and Terminating the MPI Library6.3.2. Communicators6.3.3. Getting Information6.3.4. Sending and Receiving Messages6.3.5. Example: Odd-Even Sort6.4. Topologies and Embedding6.4.1. Creating and Using Cartesian Topologies6.4.2. Example: Cannon’s Matrix-Matrix Multiplication6.5. Overlapping Communication with Computation6.5.1. Non-Blocking Communication OperationsExample: Cannon’s Matrix-Matrix Multiplication (Using Non-Blocking Operations)6.6. Collective Communication and Computation Operations6.6.1. Barrier6.6.2. Broadcast6.6.3. Reduction6.6.4. Prefix6.6.5. Gather6.6.6. Scatter6.6.7 All-to-All6.6.8. Example: One-Dimensional Matrix-Vector Multiplication6.6.9. Example: Single-Source Shortest-Path6.6.10. Example: Sample Sort6.7. Groups and Communicators6.7.1. Example: Two-Dimensional Matrix-Vector Multiplication6.8. Bibliographic RemarksProblems

7.1. Thread Basics7.2. Why Threads?7.3. The POSIX Thread API7.4. Thread Basics: Creation and Termination7.5. Synchronization Primitives in Pthreads7.5.1. Mutual Exclusion for Shared VariablesOverheads of LockingAlleviating Locking Overheads7.5.2. Condition Variables for Synchronization7.6. Controlling Thread and Synchronization Attributes7.6.1. Attributes Objects for Threads7.6.2. Attributes Objects for Mutexes7.7. Thread Cancellation7.8. Composite Synchronization Constructs7.8.1. Read-Write Locks7.8.2. Barriers7.9. Tips for Designing Asynchronous Programs7.10. OpenMP: a Standard for Directive Based Parallel Programming7.10.1. The OpenMP Programming Model7.10.2. Specifying Concurrent Tasks in OpenMPThe for DirectiveAssigning Iterations to ThreadsSynchronization Across Multiple for DirectivesThe sections DirectiveMerging DirectivesNesting parallel Directives7.10.3. Synchronization Constructs in OpenMPSynchronization Point: The barrier DirectiveSingle Thread Executions: The single and master DirectivesCritical Sections: The critical and atomic DirectivesIn-Order Execution: The ordered DirectiveMemory Consistency: The flush Directive7.10.4. Data Handling in OpenMP7.10.5. OpenMP Library FunctionsControlling Number of Threads and ProcessorsControlling and Monitoring Thread CreationMutual Exclusion7.10.6. Environment Variables in OpenMP7.10.7. Explicit Threads versus OpenMP Based Programming7.11. Bibliographic RemarksProblems
8.1. Matrix-Vector Multiplication8.1.1. Rowwise 1-D PartitioningOne Row Per ProcessUsing Fewer than n Processes8.1.2. 2-D PartitioningOne Element Per ProcessUsing Fewer than n2 ProcessesComparison of 1-D and 2-D Partitionings8.2. Matrix-Matrix Multiplication8.2.1. A Simple Parallel Algorithm8.2.2. Cannon’s Algorithm8.2.3. The DNS AlgorithmDNS Algorithm with Fewer than n3 Processes8.3. Solving a System of Linear Equations8.3.1. A Simple Gaussian Elimination AlgorithmParallel Implementation with 1-D PartitioningParallel Implementation with 2-D Partitioning8.3.2. Gaussian Elimination with Partial Pivoting1-D Partitioning2-D Partitioning8.3.3. Solving a Triangular System: Back-Substitution8.3.4. Numerical Considerations in Solving Systems of Linear Equations8.4. Bibliographic RemarksProblems
9.1. Issues in Sorting on Parallel Computers9.1.1. Where the Input and Output Sequences are Stored9.1.2. How Comparisons are PerformedOne Element Per ProcessMore than One Element Per Process9.2. Sorting Networks9.2.1. Bitonic Sort9.2.2. Mapping Bitonic Sort to a Hypercube and a MeshOne Element Per ProcessA Block of Elements Per Process9.3. Bubble Sort and its Variants9.3.1. Odd-Even TranspositionParallel Formulation9.3.2. Shellsort9.4. Quicksort9.4.1. Parallelizing Quicksort9.4.2. Parallel Formulation for a CRCW PRAM9.4.3. Parallel Formulation for Practical ArchitecturesShared-Address-Space Parallel FormulationMessage-Passing Parallel Formulation9.4.4. Pivot Selection9.5. Bucket and Sample Sort9.6. Other Sorting Algorithms9.6.1. Enumeration Sort9.6.2. Radix Sort9.7. Bibliographic RemarksProblems
10.1. Definitions and Representation10.2. Minimum Spanning Tree: Prim’s AlgorithmParallel Formulation10.3. Single-Source Shortest Paths: Dijkstra’s AlgorithmParallel Formulation10.4. All-Pairs Shortest Paths10.4.1. Dijkstra’s AlgorithmParallel Formulations10.4.2. Floyd’s AlgorithmParallel Formulation10.4.3. Performance Comparisons10.5. Transitive Closure10.6. Connected Components10.6.1. A Depth-First Search Based AlgorithmParallel Formulation10.7. Algorithms for Sparse Graphs10.7.1. Finding a Maximal Independent SetShared-Address-Space Parallel Formulation10.7.2. Single-Source Shortest PathsParallelization StrategyDistributed Memory Formulation10.8. Bibliographic RemarksProblems
11.1. Definitions and Examples11.2. Sequential Search Algorithms11.2.1. Depth-First Search AlgorithmsSimple BacktrackingDepth-First Branch-and-BoundIterative Deepening A*11.2.2. Best-First Search Algorithms11.3. Search Overhead Factor11.4. Parallel Depth-First Search11.4.1. Important Parameters of Parallel DFSWork-Splitting StrategiesLoad-Balancing Schemes11.4.2. A General Framework for Analysis of Parallel DFSComputation of V(p) for Various Load-Balancing Schemes11.4.3. Analysis of Load-Balancing Schemes11.4.4. Termination DetectionDijkstra’s Token Termination Detection AlgorithmTree-Based Termination Detection11.4.5. Experimental Results11.4.6. Parallel Formulations of Depth-First Branch-and-Bound Search11.4.7. Parallel Formulations of IDA*11.5. Parallel Best-First SearchCommunication Strategies for Parallel Best-First Tree SearchCommunication Strategies for Parallel Best-First Graph Search11.6. Speedup Anomalies in Parallel Search Algorithms11.6.1. Analysis of Average Speedup in Parallel DFSAssumptionsAnalysis of the Search Overhead Factor11.7. Bibliographic RemarksParallel Depth-First Search AlgorithmsParallel Formulations of Alpha-Beta SearchParallel Best-First SearchSpeedup Anomalies in Parallel Formulations of Search AlgorithmsRole of HeuristicsProblems
12.1. Overview of Dynamic Programming12.2. Serial Monadic DP Formulations12.2.1. The Shortest-Path Problem12.2.2. The 0/1 Knapsack Problem12.3. Nonserial Monadic DP Formulations12.3.1. The Longest-Common-Subsequence Problem12.4. Serial Polyadic DP Formulations12.4.1. Floyd’s All-Pairs Shortest-Paths Algorithm12.5. Nonserial Polyadic DP Formulations12.5.1. The Optimal Matrix-Parenthesization Problem12.6. Summary and Discussion12.7. Bibliographic RemarksProblems
13.1. The Serial Algorithm13.2. The Binary-Exchange Algorithm13.2.1. A Full Bandwidth NetworkOne Task Per ProcessMultiple Tasks Per ProcessScalability Analysis13.2.2. Limited Bandwidth Network13.2.3. Extra Computations in Parallel FFT13.3. The Transpose Algorithm13.3.1. Two-Dimensional Transpose AlgorithmComparison with the Binary-Exchange Algorithm13.3.2. The Generalized Transpose Algorithm13.4. Bibliographic RemarksProblems
A.1. Complexity of FunctionsA.2. Order Analysis of FunctionsProperties of Functions Expressed in Order Notation

Content preview from Introduction to Parallel Computing, Second Edition

Acknowledgments

We would like to begin by acknowledging our spouses, Joanna, Rinku, Krista, and Renu to whom this book is dedicated. Without their sacrifices this project would not have been seen completion. We also thank our parents, and family members, Akash, Avi, Chethan, Eleni, Larry, Mary-Jo, Naina, Petros, Samir, Subhasish, Varun, Vibhav, and Vipasha for their affectionate support and encouragement throughout this project.

Our respective institutions, Computer Sciences and Computing Research Institute (CRI) at Purdue University, Department of Computer Science & Engineering, the Army High Performance Computing Research Center (AHPCRC), and the Digital Technology Center (DTC) at the University of Minnesota, and the IBM T. J. Watson Research ...