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
expand article infoVille Leppänen‡
‡ Department of Computer Science, University of Turku, Finland

Corresponding author: Ville Leppänen ( ville.leppanen@cs.utu.fi )

© Ville Leppänen.
This article is freely available under the J.UCS Open Content License.
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
Open Access
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.