3-96  : Randomized PRAM Simulation Using T9000 Transputers
        (Zbigniew Czech and Wojciech Mikanik)

The parallel random access machine (PRAM) is the most commonly used
general-purpose machine model for describing parallel computations.
Unfortunately the PRAM model is not physically realizable, since on large
machines a parallel shared memory access can only be accomplished at the
cost of a considerable time delay. A number of PRAM simulation algorithms
have been presented in the literature. The algorithms allow execution of
PRAM programs on more realistic parallel machines. In this paper we study
the randomized simulation of an EREW (exclusive read, exclusive write)
PRAM on a module parallel computer (MPC). The simulation is based on
utilizing universal hashing. The results of our experiments performed on
the MPC built upon Inmos T9000 transputers throw some light on the
question whether using the PRAM model in parallel computations is
practically viable given the present state of technology.

Key-words: Parallel computing, PRAM model, randomized PRAM simulation
algorithms, module parallel computer, universal hashing, T9000
transputer.