Data structures for parallel recursion
Jacob Kornerup, Jayadev Misra · 1997
vii Chapter 1 Introduction 1 1.1 Synchronous Parallel Programming . . . . . . . . . . . . . . . . . . . 4 1.2 Basic Definitions and Notations . . . . . . . . . . . . . . . . . . . . . 6 1.2.1 Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.2 Operator Priority . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2.3 Notation and Proof Style . . . . . . . . . . . . . . . . . . . . 9 1.3 Cost Calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3.1 Parallel Algorithm Complexity . . . . . . . . . . . . . . . . . 14 1.3.2 Parallel Computation Models . . . . . . . . . . . . . . . . . . 17 Chapter 2 Powerlists 20 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.1.1 Induction Principle for PowerLists . . . . . . . . . . . . . . . . 25 2.1.2 Data Movement and Permutation Functions . . . . . . . . . . 26 2.2 Hypercubes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.3 A Cost Calculus for P...