Ebook: Algorithms for Parallel Processing

This IMA Volume in Mathematics and its Applications ALGORITHMS FOR PARALLEL PROCESSING is based on the proceedings of a workshop that was an integral part of the 1996-97 IMA program on "MATHEMATICS IN HIGH-PERFORMANCE COMPUTING. " The workshop brought together algorithm developers from theory, combinatorics, and scientific computing. The topics ranged over models, linear algebra, sorting, randomization, and graph algorithms and their analysis. We thank Michael T. Heath of University of lllinois at Urbana (Com­ puter Science), Abhiram Ranade of the Indian Institute of Technology (Computer Science and Engineering), and Robert S. Schreiber of Hewlett­ Packard Laboratories for their excellent work in organizing the workshop and editing the proceedings. We also take this opportunity to thank the National Science Founda­ tion (NSF) and the Army Research Office (ARO), whose financial support made the workshop possible. A vner Friedman Robert Gulliver v PREFACE The Workshop on Algorithms for Parallel Processing was held at the IMA September 16 - 20, 1996; it was the first workshop of the IMA year dedicated to the mathematics of high performance computing. The work­ shop organizers were Abhiram Ranade of The Indian Institute of Tech­ nology, Bombay, Michael Heath of the University of Illinois, and Robert Schreiber of Hewlett Packard Laboratories. Our idea was to bring together researchers who do innovative, exciting, parallel algorithms research on a wide range of topics, and by sharing insights, problems, tools, and methods to learn something of value from one another.

---

Models and Mechanisms in Parallel Computation.- A General Purpose Shared-Memory Model For Parallel Computation.- Supporting A Coherent Shared Address Space Across SMP Nodes: An Application-Driven Investigation.- Single-Message Vs. Batch Communication.- Some Simple and Practical Strategies For Parallelism; Discrete and Combinatorial Algorithms.- Locality In Computing Connected Components.- Routing In Optical and Wireless Networks.- Transparent Parallel Transactions On Replicated Autonomous Databases; Mathematicsof Parallelizing Compilers.- Mathematical Tools For Loop Transformations: From Systems of Uniform Recurrence Equations To The Polytope Model; Numerical Algorithms.- The Scalability of Mesh Improvement Algorithms.- Data Parallel Performance Optimizations Using Array Aliasing.- Coarsening, Sampling and Smoothing: Elements of The Multilevel Method.- Some Methods Of Parallel Pseudorandom Number Generation.- Performance of Parallel Sparse Triangular Solution.- Determining An out-of-core FFT Decomposition Strategy for Parallel Disks by Dynamic Programming; Parallel ComputerSystems and Software.- Enabling Department-Scale Supercomputing.- Providing Uniform Dynamic Access To Numerical Software.

---

Models and Mechanisms in Parallel Computation.- A General Purpose Shared-Memory Model For Parallel Computation.- Supporting A Coherent Shared Address Space Across SMP Nodes: An Application-Driven Investigation.- Single-Message Vs. Batch Communication.- Some Simple and Practical Strategies For Parallelism; Discrete and Combinatorial Algorithms.- Locality In Computing Connected Components.- Routing In Optical and Wireless Networks.- Transparent Parallel Transactions On Replicated Autonomous Databases; Mathematicsof Parallelizing Compilers.- Mathematical Tools For Loop Transformations: From Systems of Uniform Recurrence Equations To The Polytope Model; Numerical Algorithms.- The Scalability of Mesh Improvement Algorithms.- Data Parallel Performance Optimizations Using Array Aliasing.- Coarsening, Sampling and Smoothing: Elements of The Multilevel Method.- Some Methods Of Parallel Pseudorandom Number Generation.- Performance of Parallel Sparse Triangular Solution.- Determining An out-of-core FFT Decomposition Strategy for Parallel Disks by Dynamic Programming; Parallel ComputerSystems and Software.- Enabling Department-Scale Supercomputing.- Providing Uniform Dynamic Access To Numerical Software.
Content:
Front Matter....Pages i-x
A General-Purpose Shared-Memory Model for Parallel Computation....Pages 1-17
Supporting a Coherent Shared Address Space Across SMP Nodes: An Application-Driven Investigation....Pages 19-59
Single-Message vs. Batch Communication....Pages 61-74
Some Simple and Practical Strategies for Parallelism....Pages 75-87
Locality in Computing Connected Components....Pages 89-99
Routing in Optical and Wireless Networks....Pages 101-116
Transparent Parallel Transactions on Replicated Autonomous Databases....Pages 117-145
Mathematical Tools for Loop Transformations: From Systems of Uniform Recurrence Equations to the Polytope Model....Pages 147-183
The Scalability of Mesh Improvement Algorithms....Pages 185-211
Data Parallel Performance Optimizations Using Array Aliasing....Pages 213-245
Coarsening, Sampling, and Smoothing: Elements of the Multilevel Method....Pages 247-276
Some Methods of Parallel Pseudorandom Number Generation....Pages 277-288
Performance of Parallel Sparse Triangular Solution....Pages 289-305
Determining an out-of-Core FFT Decomposition Strategy for Parallel Disks by Dynamic Programming....Pages 307-320
Enabling Department-Scale Supercomputing....Pages 321-344
Providing Uniform Dynamic Access to Numerical Software....Pages 345-366
Back Matter....Pages 367-373

---

Models and Mechanisms in Parallel Computation.- A General Purpose Shared-Memory Model For Parallel Computation.- Supporting A Coherent Shared Address Space Across SMP Nodes: An Application-Driven Investigation.- Single-Message Vs. Batch Communication.- Some Simple and Practical Strategies For Parallelism; Discrete and Combinatorial Algorithms.- Locality In Computing Connected Components.- Routing In Optical and Wireless Networks.- Transparent Parallel Transactions On Replicated Autonomous Databases; Mathematicsof Parallelizing Compilers.- Mathematical Tools For Loop Transformations: From Systems of Uniform Recurrence Equations To The Polytope Model; Numerical Algorithms.- The Scalability of Mesh Improvement Algorithms.- Data Parallel Performance Optimizations Using Array Aliasing.- Coarsening, Sampling and Smoothing: Elements of The Multilevel Method.- Some Methods Of Parallel Pseudorandom Number Generation.- Performance of Parallel Sparse Triangular Solution.- Determining An out-of-core FFT Decomposition Strategy for Parallel Disks by Dynamic Programming; Parallel ComputerSystems and Software.- Enabling Department-Scale Supercomputing.- Providing Uniform Dynamic Access To Numerical Software.
Content:
Front Matter....Pages i-x
A General-Purpose Shared-Memory Model for Parallel Computation....Pages 1-17
Supporting a Coherent Shared Address Space Across SMP Nodes: An Application-Driven Investigation....Pages 19-59
Single-Message vs. Batch Communication....Pages 61-74
Some Simple and Practical Strategies for Parallelism....Pages 75-87
Locality in Computing Connected Components....Pages 89-99
Routing in Optical and Wireless Networks....Pages 101-116
Transparent Parallel Transactions on Replicated Autonomous Databases....Pages 117-145
Mathematical Tools for Loop Transformations: From Systems of Uniform Recurrence Equations to the Polytope Model....Pages 147-183
The Scalability of Mesh Improvement Algorithms....Pages 185-211
Data Parallel Performance Optimizations Using Array Aliasing....Pages 213-245
Coarsening, Sampling, and Smoothing: Elements of the Multilevel Method....Pages 247-276
Some Methods of Parallel Pseudorandom Number Generation....Pages 277-288
Performance of Parallel Sparse Triangular Solution....Pages 289-305
Determining an out-of-Core FFT Decomposition Strategy for Parallel Disks by Dynamic Programming....Pages 307-320
Enabling Department-Scale Supercomputing....Pages 321-344
Providing Uniform Dynamic Access to Numerical Software....Pages 345-366
Back Matter....Pages 367-373
....