Practical PRAM Programming

Can the PRAM (Parallel Random Access Machine) be used for practical parallel computing in addition to its indispensable role as a theoretical model of parallel computation? Absolutely, say Jorg Keller, Christoph Ke?ler, and Jesper Traff, three experts in the area of design and programming of parallel computers. They give a comprehensive overview of basic PRAM theory, discuss emulation of the PRAM in hardware, describe the PRAM programming language Fork, and exhaustively discuss parallel algorithm design and implementation techniques. The discussion is complemented by a complete software package that can be used for learning parallel programming in general and devising PRAM algorithms in particular, including:

• Thorough explanations with extensive examples of the PRAM programming language Fork
• Discussion of many general-purpose parallel programming paradigms and their specific implementation in Fork
• A compiler for Fork with implementation details
• Full details of the SB-PRAM, the hardware prototype of a virtual PRAM with a considerable number of processors
• An extensive library called PAD of fundamental parallel data structures and classical PRAM algorithms
• A larger example from computational geometry putting techniques and algorithms from the book together

An accompanying ftp site contains the complete source code of the SB-PRAM system software, the Fork compiler, and the PAD library, and also includes a simulator for the SB-PRAM.

Contents

• The PRAM Model of Parallel Computation.
• PRAM Emulation.
• An Emulation of a PRAM in Hardware.
• Fork.
• Implementation of Fork.
• Parallel Algorithmic Paradigms and Programming Techniques.
• A Library of Basic PRAM Algorithms.
• An Example Application.
• Appendices.
• Glossary.
• References.