Randomized PRAM Simulation Using T9000 Transputers

Czech, Zbigniew and Mikanik, Wojciech (1996) Randomized PRAM Simulation Using T9000 Transputers. Technical report. UKC, University of Kent, Canterbury, UK (Full text available)

PDF
Download (221kB)
[img]
Preview
Postscript
Download (171kB)
[img]
Preview

Abstract

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. Keywords: Parallel computing, PRAM model, randomized PRAM simulation algorithms, module parallel computer, universal hashing, T9000 transputer.

Item Type: Monograph (Technical report)
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Faculties > Science Technology and Medical Studies > School of Computing
Depositing User: Mark Wheadon
Date Deposited: 06 Sep 2009 23:31
Last Modified: 06 Sep 2011 03:52
Resource URI: http://kar.kent.ac.uk/id/eprint/21406 (The current URI for this page, for reference purposes)
  • Depositors only (login required):

Downloads

Downloads per month over past year