Introduction to Parallel Processing

1. Front Matter

   Pages i-xxi

   PDF

2. Fundamental Concepts

   1. Introduction to Parallelism

      Pages 3-23

   2. A Taste of Parallel Algorithms

      Pages 25-43

   3. Parallel Algorithm Complexity

      Pages 45-63

   4. Models of Parallel Processing

      Pages 65-86

3. Extreme Models

   1. PRAM and Basic Algorithms

      Pages 89-108

   2. More Shared-memory Algorithms

      Pages 109-128

   3. Sorting and Selection Networks

      Pages 129-147

   4. Other Circuit-Level Examples

      Pages 149-168

4. Mesh-Based Architectures

   1. Sorting on a 2D Mesh or Torus

      Pages 171-190

   2. Routing on a 2D Mesh or Torus

      Pages 191-210

   3. Numerical 2D Mesh Algorithms

      Pages 211-233

   4. Other Mesh-Related Architectures

      Pages 235-256

5. Low-Diameter Architectures

   1. Hypercubes and Their Algorithms

      Pages 259-278

   2. Sorting and Routing on Hypercubes

      Pages 281-299

   3. Other Hypercubic Architectures

      Pages 301-320

   4. A Sampler of Other Networks

      Pages 321-344

6. Some Broad Topics

   1. Emulation and Scheduling

      Pages 347-367

   2. Data Storage, Input, and Output

      Pages 369-389

   3. Reliable Parallel Processing

      Pages 391-413

THE CONTEXT OF PARALLEL PROCESSING The field of digital computer architecture has grown explosively in the past two decades. Through a steady stream of experimental research, tool-building efforts, and theoretical studies, the design of an instruction-set architecture, once considered an art, has been transformed into one of the most quantitative branches of computer technology. At the same time, better understanding of various forms of concurrency, from standard pipelining to massive parallelism, and invention of architectural structures to support a reasonably efficient and user-friendly programming model for such systems, has allowed hardware performance to continue its exponential growth. This trend is expected to continue in the near future. This explosive growth, linked with the expectation that performance will continue its exponential rise with each new generation of hardware and that (in stark contrast to software) computer hardware will function correctly as soon as it comes off the assembly line, has its down side. It has led to unprecedented hardware complexity and almost intolerable dev- opment costs. The challenge facing current and future computer designers is to institute simplicity where we now have complexity; to use fundamental theories being developed in this area to gain performance and ease-of-use benefits from simpler circuits; to understand the interplay between technological capabilities and limitations, on the one hand, and design decisions based on user and application requirements on the other.

• Processing
• algorithms
• architecture
• complexity
• networks
• scheduling

• University of California at Santa Barbara, Santa Barbara

  Behrooz Parhami

Policies and ethics