Algorithms for Parallel Processing

1. Front Matter

   Pages i-x

   PDF

2. Models and Mechanisms in Parallel Computation

   1. A General-Purpose Shared-Memory Model for Parallel Computation

      • Vijaya Ramachandran

      Pages 1-17

   2. Supporting a Coherent Shared Address Space Across SMP Nodes: An Application-Driven Investigation

      • Angelos Bilas, Liviu Iftode, Rudrajit Samanta, Jaswinder Pal Singh

      Pages 19-59

   3. Single-Message vs. Batch Communication

      • Mark W. Goudreau, Satish B. Rao

      Pages 61-74

   4. Some Simple and Practical Strategies for Parallelism

      • Nicholas Carriero, David Gelernter

      Pages 75-87

3. Discrete and Combinatorial Algorithms

   1. Locality in Computing Connected Components

      • Abhiram Ranade

      Pages 89-99

   2. Routing in Optical and Wireless Networks

      • Eric J. Schwabe

      Pages 101-116

   3. Transparent Parallel Transactions on Replicated Autonomous Databases

      • Rekha Goel, Gautam M. Shroff

      Pages 117-145

4. Mathematics of Parallelizing Compilers

   1. Mathematical Tools for Loop Transformations: From Systems of Uniform Recurrence Equations to the Polytope Model

      • Alain Darte

      Pages 147-183

5. Numerical Algorithms

   1. The Scalability of Mesh Improvement Algorithms

      • Lori A. Freitag, Mark T. Jones, Paul E. Plassmann

      Pages 185-211

   2. Data Parallel Performance Optimizations Using Array Aliasing

      • Y. Charlie Hu, S. Lennart Johnsson

      Pages 213-245

   3. Coarsening, Sampling, and Smoothing: Elements of the Multilevel Method

      • Shang-Hua Teng

      Pages 247-276

   4. Some Methods of Parallel Pseudorandom Number Generation

      • Michael Mascagni

      Pages 277-288

   5. Performance of Parallel Sparse Triangular Solution

      • Michael T. Heath, Padma Raghavan

      Pages 289-305

   6. Determining an out-of-Core FFT Decomposition Strategy for Parallel Disks by Dynamic Programming

      • Thomas H. Cormen

      Pages 307-320

6. Parallel Computer Systems and Software

   1. Enabling Department-Scale Supercomputing

      • David S. Greenberg, William E. Hart, Cynthia A. Phillips

      Pages 321-344

   2. Providing Uniform Dynamic Access to Numerical Software

      • Henri Casanova, Jack Dongarra

      Pages 345-366

7. Back Matter

   Pages 367-373

   PDF

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.

• Combinatorics
• Hochleistungsrechnen
• Scala
• algorithm
• algorithms
• databases
• optimization
• parallelism
• programming
• scientific computing
• sorting
• algorithm analysis and problem complexity

• Department of Computer Science, University of Illinois at Urbana, Urbana, USA

  Michael T. Heath

• Department of Computer Science and Engineering, Indian Institute of Technology, Powai, India

  Abhiram Ranade

• Hewlett-Packard, Inc., Palo Alto, USA

  Robert S. Schreiber

Policies and ethics