Introduction to Parallel Algorithms and Architectures

Introduction to Parallel Algorithms and Architectures: Arrays Trees Hypercubes provides an introduction to the expanding field of parallel algorithms and architectures. This book focuses on parallel computation involving the most popular network architectures, namely, arrays, trees, hypercubes, and some closely related networks.

Organized into three chapters, this book begins with an overview of the simplest architectures of arrays and trees. This text then presents the structures and relationships between the dominant network architectures, as well as the most efficient parallel algorithms for a wide variety of problems. Other chapters focus on fundamental results and techniques and on rigorous analysis of algorithmic performance. This book discusses as well a hybrid of network architecture based on arrays and trees called the mesh of trees. The final chapter deals with the most important properties of hypercubes.

This book is a valuable resource for readers with a general technical background.

Inhalt

Preface

Organization of the Material

Teaching from the Text

Exercises and Bibliographic Notes

Errors

Preview of Volume II

Acknowledgments

Notation

1 Arrays and Trees

1.1 Elementary Sorting and Counting

1.1.1 Sorting on a Linear Array

1.1.2 Sorting in the Bit Model

1.1.3 Lower Bounds

1.1.4 A Counterexample-Counting

1.1.5 Properties of the Fixed-Connection Network Model

1.2 Integer Arithmetic

1.2.1 Carry-Lookahead Addition

1.2.2 Prefix Computations

1.2.3 Carry-Save Addition

1.2.4 Multiplication and Convolution

1.2.5 Division and Newton Iteration

1.3 Matrix Algorithms

1.3.1 Elementary Matrix Products

1.3.2 Algorithms for Triangular Matrices

1.3.3 Algorithms for Tridiagonal Matrices

1.3.4 Gaussian Elimination

1.3.5 Iterative Methods

1.4 Retiming and Systolic Conversion

1.4.1 A Motivating Example-Palindrome Recognition

1.4.2 The Systolic and Semisystolic Models of Computation

1.4.3 Retiming Semisystolic Networks

1.4.4 Conversion of a Semisystolic Network into a Systolic Network

1.4.5 The Special Case of Broadcasting

1.4.6 Retiming the Host

1.4.7 Design by Systolic Conversion-A Summary

1.5 Graph Algorithms

1.5.1 Transitive Closure

1.5.2 Connected Components

1.5.3 Shortest Paths

1.5.4 Breadth-First Spanning Trees

1.5.5 Minimum-Weight Spanning Trees

1.6 Sorting Revisited

1.6.1 Odd-Even Transposition Sort on a Linear Array

1.6.2 A Simple vN(logN + 1)-Step Sorting Algorithm

1.6.3 Á (3vN + o(vV))-Step Sorting Algorithm

1.6.4 A Matching Lower Bound

1.7 Packet Routing

1.7.1 Greedy Algorithms

1.7.2 Average-Case Analysis of Greedy Algorithms

1.7.3 Randomized Routing Algorithms

1.7.4 Deterministic Algorithms with Small Queues

1.7.5 An Off-Line Algorithm

1.7.6 Other Routing Models and Algorithms

1.8 Image Analysis and Computational Geometry

1.8.1 Component-Labelling Algorithms

1.8.2 Computing Hough Transforms

1.8.3 Nearest-Neighbor Algorithms

1.8.4 Finding Convex Hulls

1.9 Higher-Dimensional Arrays

1.9.1 Definitions and Properties

1.9.2 Matrix Multiplication

1.9.3 Sorting

1.9.4 Packet Routing

1.9.5 Simulating High-Dimensional Arrays on Low-Dimensional Arrays

1.10 Problems

1.11 Bibliographic Notes

2 Meshes of Trees

2.1 The Two-Dimensional Mesh of Trees

2.1.1 Definition and Properties

2.1.2 Recursive Decomposition

2.1.3 Derivation from KN,N

2.1.4 Variations

2.1.5 Comparison With the Pyramid and Multigrid

2.2 Elementary O (Log N) - Step Algorithms

2.2.1 Routing

2.2.2 Sorting

2.2.3 Matrix-Vector Multiplication

2.2.4 Jacobi Relaxation

2.2.5 Pivoting

2.2.6 Convolution

2.2.7 Convex Hull

2.3 Integer Arithmetic

2.3.1 Multiplication

2.3.2 Division and Chinese Remaindering

2.3.3 Related Problems

2.4 Matrix Algorithms

2.4.1 The Three-Dimensional Mesh of Trees

2.4.2 Matrix Multiplication

2.4.3 Inverting Lower Triangular Matrices

2.4.4 Inverting Arbitrary Matrices

2.4.5 Related Problems

2.5 Graph Algorithms

2.5.1 Minimum-Weight Spanning Trees

2.5.2 Connected Components

2.5.3 Transitive Closure

2.5.4 Shortest Paths

2.5.5 Matching Problems

2.6 Fast Evaluation of Straight-Line Code

2.6.1 Addition and Multiplication Over a Semiring

2.6.2 Extension to Codes with Subtraction and Division

2.6.3 Applications

2.7 Higher-Dimensional Meshes of Trees

2.7.1 Definitions and Properties

2.7.2 The Shuffle-Tree Graph

2.8 Problems

2.9 Bibliographic Notes

3 Hypercubes and Related Networks

3.1 The Hypercube

3.1.1 Definitions and Properties

3.1.2 Containment of Arrays

3.1.3 Containment of Complete Binary Trees

3.1.4 Embeddings of Arbitrary Binary Trees

3.1.5 Containment of Meshes of Trees

3.1.6 Other Containment Results

3.2 The Butterfly, Cube-Connected-Cycles, and BeneS Network

3.2.1 Definitions and Properties

3.2.2 Simulation of Arbitrary Networks

3.2.3 Simulation of Normal Hypercube Algorithms

3.2.4 Some Containment and Simulation Results

3.3 The Shuffle-Exchange and de Bruijn Graphs

3.3.1 Definitions and Properties

3.3.2 The Diaconis Card Tricks

3.3.3 Simulation of Normal Hypercube Algorithms

3.3.4 Similarities with the Butterfly

3.3.5 Some Containment and Simulation Results

3.4 Packet-Routing Algorithms

3.4.1 Definitions and Routing Models

3.4.2 Greedy Routing Algorithms and Worst-Case Problems

3.4.3 Packing, Spreading, and Monotone Routing Problems

3.4.4 The Average-Case Behavior of the Greedy Algorithm

3.4.5 Converting Worst-Case Routing Problems into Average-Case Routing Problems

3.4.6 Bounding Queue Sizes

3.4.7 Routing with Combining

3.4.8 The Information Dispersal Approach to Routing

3.4.9 Circuit-Switching Algorithms

3.5 Sorting

3.5.1 Odd-Even Merge Sort

3.5.2 Sorting Small Sets

3.5.3 A Deterministic O (Log N Log Log N)-Step Sorting Algorithm

3.5.4 Randomized O (Log N)-Step Sorting Algorithms

3.6 Simulating a Parallel Random Access Machine

3.6.1 PRAM Models and Shared Memories

3.6.2 Randomized Simulations Based on Hashing

3.6.3 Deterministic Simulations Using Replicated Data

3.6.4 Using Information Dispersal to Improve Performance

3.7 The Fast Fourier Transform

3.7.1 The Algorithm

3.7.2 Implementation on the Butterfly and Shuffle-Exchange Graph

3.7.3 Application to Convolution and Polynomial Arithmetic

3.7.4 Application to Integer Multiplication

3.8 Other Hypercubic Networks

3.8.1 Butterflylike Networks

3.8.2 De Bruijn-Type Networks

3.9 Problems

3.10 Bibliographic Notes

Bibliographic Notes

Index

Lemmas, Theorems, and Corollaries

Author Index

Subject Index