Parallel Computing Using the Prefix Problem
1st Edition
Published on 21. July 1994
313 pages
978-0-19-535847-6 (ISBN)
Description
The prefix operation on a set of data is one of the simplest and most useful building blocks in parallel algorithms. This introduction to those aspects of parallel programming and parallel algorithms that relate to the prefix problem emphasizes its use in a broad range of familiar and important problems. The book illustrates how the prefix operation approach to parallel computing leads to fast and efficient solutions to many different kinds of problems. Students, teachers, programmers, and computer scientists will want to read this clear exposition of an important approach.
More details
Other editions
Additional editions
S. Lakshmivarahan | Sudarshan K. Dhall
Parallel Computing Using the Prefix Problem
Book
09/1994
Oxford University Press Inc
€96.10
Shipment within 15-20 days
Content
- Intro
- Contents
- Preface
- Acknowledgments
- Part One - Getting Started
- Chapter 1 - The Prefix Problem And Its Applications
- 1.1 The Prefix Problem
- 1.2 Why Prefix Problem
- 1.3 Exercises
- 1.4 Notes and References
- Chapter 2 - Parallel Machines And Models - An Overview
- 2.1 The Need for Parallelism
- 2.2 A Classification of Parallel Computers
- 2.3 Parallel Models
- 2.4 Performance Measures
- 2.5 A Parallel Complexity Class
- 2.6 Brent's Inequality
- 2.7 A Simple Lower Bound
- 2.8 Exercises
- 2.9 Notes and References
- Part Two - Algorithms For Shared Memory Models
- Chapter 3 - Parallel Prefix Algorithms On Arrays
- 3.1 Methods of Cyclic Elimination and Reduction
- 3.2 Schwartz's Method
- 3.3 An Algorithm for Fixed Parallelism
- 3.4 A Balanced Binary Tree Algorithm
- 3.5 Cole-Vishkin Algorithm
- 3.6 A Comparison
- 3.7 Exercises
- 3.8 Notes and References
- Chapter 4 - Parallel Prefix Algorithms On Linked Lists
- 4.1 Basic Pointer-jumping
- 4.2 A Strategy for Optimal List Ranking
- 4.3 Independent Set via Coloring
- 4.4 Cole and Vishkin's Algorithm
- 4.5 Independent Set via Randomization
- 4.6 Exercises
- 4.7 Notes and References
- Part Three - Algorithms For Circuit Models
- Chapter 5 - Parallel Prefix Circuits
- 5.1 Serial Circuit
- 5.2 A Simple Parallel Prefix Circuit
- 5.3 Ladner-Fischer Parallel Prefix Circuits
- 5.4 Exercises
- 5.5 Notes and References
- Chapter 6 - Size Vs. Depth Trade-Off In Parallel Prefix Circuits
- 6.1 A Lower Bound on (Size + Depth)
- 6.2 A Layered Prefix Circuit CR(N)
- 6.3 (s, d)-Optimal Design and Snir's Circuit
- 6.4 LYD Circuit
- 6.5 Exercises
- 6.6 Notes and References
- Part Four - Analysis Of Fan-In And Fan-Out In Circuits
- Chapter 7 - Bounding Fan-Out In Parallel Prefix Circuits
- 7.1 Methods for Bounding Fan-out
- 7.2 Prefix Circuits with Bounded Fan-out
- 7.3 Exercises
- 7.4 Notes and References
- Chapter 8 - Constant Depth Prefix Circuits With Unbounded Fan-in
- 8.1 The Need for Group-Free Semigroups
- 8.2 Small Prefix Circuits with Unbounded Fan-in
- 8.3 Small Circuits for Binary Addition
- 8.4 Small Circuits and Group-Free Semigroups
- 8.5 Exercises
- 8.6 Notes and References
- Appendices
- Appendix A -Semigroups and Monoids
- A1. Definitions and Properties
- A2. A Classification of Semigroups
- A3. Notes and References
- Appendix B - Group-free Semigroups, Star-free Regular Expressions, and Unbounded Fan-in Circuits
- B1. Star-Free Regular Expressions
- B2. Relating Star-Free Regular Expression to Group-Free Semigroup
- B3. Relating Group-Free Semigroups to Unbounded Fan-in Circuits
- B4. Notes and References
- Appendix C - Boolean Circuits for Computing Parity
- C1. Definition and Properties of Parity
- C2. A Depth-Size Trade-off
- C3. A Lower Bound on the Size
- C4. Notes and References
- References
- Index
- A
- B
- C
- D
- E
- F
- G
- H
- I
- K
- L
- M
- N
- O
- P
- R
- S
- T
- U
- W
