JUCS - Journal of Universal Computer Science 1(1): 23-34, doi: 10.3217/jucs-001-01-0023

On Implementing EREW Work-Optimally on Mesh of Trees

‡ Department of Computer Science, University of Turku, Finland

Corresponding author: Ville Leppänen ( ville.leppanen@cs.utu.fi ) Citation:
Leppänen V (1995) On Implementing EREW Work-Optimally on Mesh of Trees. JUCS - Journal of Universal Computer Science 1(1): 23-34. https://doi.org/10.3217/jucs-001-01-0023 |

Abstract

We show how to implement an -processor EREW PRAM workoptimally on a 2-dimensional n-sided mesh of trees, consisting of n processors, n memory modules, and nodes. Similarly, we prove that an -processor EREW PRAM can be implemented work-optimally on a 3-dimensional n-sided mesh of trees. By the work-optimality of implementations we mean that the expected routing time of PRAM memory requests is per simulated PRAM processor with high probability. Experiments show that on relatively small and the cost per simulated PRAM processor is 1.5-2.5 in the 2-dimensional case, and 2-3 in the 3-dimensional case. If at each step at most 1/3'th of the PRAM processors make a reference to the shared memory, then the simulation cost is approximately 1. We also compare our work-optimal simulations to those proposed for coated meshes.

Keywords

EREW, mesh of trees, shared memory, simulation, work-optimal, randomized, coated mesh.