Parallel Computing Using the Prefix Problem.

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.

Description based on publisher supplied metadata and other sources.

Electronic reproduction. Ann Arbor, Michigan : ProQuest Ebook Central, 2024. Available via World Wide Web. Access may be limited to ProQuest Ebook Central affiliated libraries.