Next Section

Introduction to Parallel Computing, Second Edition

Increasingly, parallel processing is being seen as the only cost-effective method for the fast solution of computationally large and data-intensive problems. The emergence of inexpensive parallel computers such as commodity desktop multiprocessors and clusters of workstations or PCs has made such parallel methods generally applicable, as have software standards for portable parallel programming. This sets the stage for substantial growth in parallel software.

Data-intensive applications such as transaction processing and information retrieval, data mining and analysis and multimedia services have provided a new challenge for the modern generation of parallel platforms. Emerging areas such as computational biology and nanotechnology have implications for algorithms and systems development, while changes in architectures, programming models and applications have implications for how parallel platforms are made available to users in the form of grid-based services.

This book takes into account these new developments as well as covering the more traditional problems addressed by parallel computers.Where possible it employs an architecture-independent view of the underlying platforms and designs algorithms for an abstract model. Message Passing Interface (MPI), POSIX threads and OpenMP have been selected as programming models and the evolving application mix of parallel computing is reflected in various examples throughout the book.


Table of Contents

    Chapter 1.  Introduction to Parallel Computing
     Section 1.1.  Motivating Parallelism
     Section 1.2.  Scope of Parallel Computing
     Section 1.3.  Organization and Contents of the Text
     Section 1.4.  Bibliographic Remarks
    Chapter 2.  Parallel Programming Platforms
     Section 2.1.  Implicit Parallelism: Trends in Microprocessor Architectures*
     Section 2.2.  Limitations of Memory System Performance*
     Section 2.3.  Dichotomy of Parallel Computing Platforms
     Section 2.4.  Physical Organization of Parallel Platforms
     Section 2.5.  Communication Costs in Parallel Machines
     Section 2.6.  Routing Mechanisms for Interconnection Networks
     Section 2.7.  Impact of Process-Processor Mapping and Mapping Techniques
     Section 2.8.  Bibliographic Remarks
    Chapter 3.  Principles of Parallel Algorithm Design
     Section 3.1.  Preliminaries
     Section 3.2.  Decomposition Techniques
     Section 3.3.  Characteristics of Tasks and Interactions
     Section 3.4.  Mapping Techniques for Load Balancing
     Section 3.5.  Methods for Containing Interaction Overheads
     Section 3.6.  Parallel Algorithm Models
     Section 3.7.  Bibliographic Remarks
    Chapter 4.  Basic Communication Operations
     Section 4.1.  One-to-All Broadcast and All-to-One Reduction
     Section 4.2.  All-to-All Broadcast and Reduction
     Section 4.3.  All-Reduce and Prefix-Sum Operations
     Section 4.4.  Scatter and Gather
     Section 4.5.  All-to-All Personalized Communication
     Section 4.6.  Circular Shift
     Section 4.7.  Improving the Speed of Some Communication Operations
     Section 4.8.  Summary
     Section 4.9.  Bibliographic Remarks
    Chapter 5.  Analytical Modeling of Parallel Programs
     Section 5.1.  Sources of Overhead in Parallel Programs
     Section 5.2.  Performance Metrics for Parallel Systems
     Section 5.3.  The Effect of Granularity on Performance
     Section 5.4.  Scalability of Parallel Systems
     Section 5.5.  Minimum Execution Time and Minimum Cost-Optimal Execution Time
     Section 5.6.  Asymptotic Analysis of Parallel Programs
     Section 5.7.  Other Scalability Metrics
     Section 5.8.  Bibliographic Remarks
    Chapter 6.  Programming Using the Message-Passing Paradigm
     Section 6.1.  Principles of Message-Passing Programming
     Section 6.2.  The Building Blocks: Send and Receive Operations
     Section 6.3.  MPI: the Message Passing Interface
     Section 6.4.  Topologies and Embedding
     Section 6.5.  Overlapping Communication with Computation
     Section 6.6.  Collective Communication and Computation Operations
     Section 6.7.  Groups and Communicators
     Section 6.8.  Bibliographic Remarks
    Chapter 7.  Programming Shared Address Space Platforms
     Section 7.1.  Thread Basics
     Section 7.2.  Why Threads?
     Section 7.3.  The POSIX Thread API
     Section 7.4.  Thread Basics: Creation and Termination
     Section 7.5.  Synchronization Primitives in Pthreads
     Section 7.6.  Controlling Thread and Synchronization Attributes
     Section 7.7.  Thread Cancellation
     Section 7.8.  Composite Synchronization Constructs
     Section 7.9.  Tips for Designing Asynchronous Programs
     Section 7.10.  OpenMP: a Standard for Directive Based Parallel Programming
     Section 7.11.  Bibliographic Remarks
    Chapter 8.  Dense Matrix Algorithms
     Section 8.1.  Matrix-Vector Multiplication
     Section 8.2.  Matrix-Matrix Multiplication
     Section 8.3.  Solving a System of Linear Equations
     Section 8.4.  Bibliographic Remarks
    Chapter 9.  Sorting
     Section 9.1.  Issues in Sorting on Parallel Computers
     Section 9.2.  Sorting Networks
     Section 9.3.  Bubble Sort and its Variants
     Section 9.4.  Quicksort
     Section 9.5.  Bucket and Sample Sort
     Section 9.6.  Other Sorting Algorithms
     Section 9.7.  Bibliographic Remarks
    Chapter 10.  Graph Algorithms
     Section 10.1.  Definitions and Representation
     Section 10.2.  Minimum Spanning Tree: Prim's Algorithm
     Section 10.3.  Single-Source Shortest Paths: Dijkstra's Algorithm
     Section 10.4.  All-Pairs Shortest Paths
     Section 10.5.  Transitive Closure
     Section 10.6.  Connected Components
     Section 10.7.  Algorithms for Sparse Graphs
     Section 10.8.  Bibliographic Remarks
    Chapter 11.  Search Algorithms for Discrete Optimization Problems
     Section 11.1.  Definitions and Examples
     Section 11.2.  Sequential Search Algorithms
     Section 11.3.  Search Overhead Factor
     Section 11.4.  Parallel Depth-First Search
     Section 11.5.  Parallel Best-First Search
     Section 11.6.  Speedup Anomalies in Parallel Search Algorithms
     Section 11.7.  Bibliographic Remarks
    Chapter 12.  Dynamic Programming
     Section 12.1.  Overview of Dynamic Programming
     Section 12.2.  Serial Monadic DP Formulations
     Section 12.3.  Nonserial Monadic DP Formulations
     Section 12.4.  Serial Polyadic DP Formulations
     Section 12.5.  Nonserial Polyadic DP Formulations
     Section 12.6.  Summary and Discussion
     Section 12.7.  Bibliographic Remarks
    Chapter 13.  Fast Fourier Transform
     Section 13.1.  The Serial Algorithm
     Section 13.2.  The Binary-Exchange Algorithm
     Section 13.3.  The Transpose Algorithm
     Section 13.4.  Bibliographic Remarks
    Appendix A.  Complexity of Functions and Order Analysis
     Section A.1.  Complexity of Functions
     Section A.2.  Order Analysis of Functions

  Next Section