Efficient Simulation of PRAM Algorithms on Shared Memory Machines

Abstract

The parallel random-access machine (PRAM) is an abstract shared memory register machine used in computer science to model the algorithmic performance of parallel algorithms. Although being used as theoretical model for many years, only few attempts have been made to prove technical feasibility of the model for the use in real world applications. One of these attempts was the SB-PRAM Project, which included the development of a real PRAM hardware, a high-level PRAM programming language and a compiler. It offered programmers the ability to implement algorithms designed for a PRAM in a natural way. Today, the hardware based prototype no longer exists, but a simulation software is still available. Even though the simulated hardware contains a huge amount of inherent parallelism, it turned out to be hard to provide an efficient parallel implementation of the simulation. In this article a promising new approach for this problem, its implementation and evaluation is presented. Experiments have shown the high potential of its efficiency and discover even more potential that can be exploited by future work.