On Implementing EREW Work-Optimally on Mesh of Trees

dc.creatorLeppänen,Ville
dc.date1995
dc.date.accessioned2024-02-06T12:47:34Z
dc.date.available2024-02-06T12:47:34Z
dc.descriptionWe 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.
dc.formattext/html
dc.identifierhttps://doi.org/10.3217/jucs-001-01-0023
dc.identifierhttps://lib.jucs.org/article/27078/
dc.identifier.urihttps://openrepository.mephi.ru/handle/123456789/6724
dc.languageen
dc.publisherJournal of Universal Computer Science
dc.relationinfo:eu-repo/semantics/altIdentifier/eissn/0948-6968
dc.relationinfo:eu-repo/semantics/altIdentifier/pissn/0948-695X
dc.rightsinfo:eu-repo/semantics/openAccess
dc.rightsJ.UCS License
dc.sourceJUCS - Journal of Universal Computer Science 1(1): 23-34
dc.subjectEREW
dc.subjectmesh of trees
dc.subjectshared memory
dc.subjectsimulation
dc.subjectwork-optimal
dc.subjectrandomized
dc.subjectcoated mesh.
dc.titleOn Implementing EREW Work-Optimally on Mesh of Trees
dc.typeResearch Article
Файлы
Коллекции