On Implementing EREW Work-Optimally on Mesh of Trees
| dc.creator | Leppänen,Ville | |
| dc.date | 1995 | |
| dc.date.accessioned | 2024-02-06T12:47:34Z | |
| dc.date.available | 2024-02-06T12:47:34Z | |
| dc.description | 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. | |
| dc.format | text/html | |
| dc.identifier | https://doi.org/10.3217/jucs-001-01-0023 | |
| dc.identifier | https://lib.jucs.org/article/27078/ | |
| dc.identifier.uri | https://openrepository.mephi.ru/handle/123456789/6724 | |
| dc.language | en | |
| dc.publisher | Journal of Universal Computer Science | |
| dc.relation | info:eu-repo/semantics/altIdentifier/eissn/0948-6968 | |
| dc.relation | info:eu-repo/semantics/altIdentifier/pissn/0948-695X | |
| dc.rights | info:eu-repo/semantics/openAccess | |
| dc.rights | J.UCS License | |
| dc.source | JUCS - Journal of Universal Computer Science 1(1): 23-34 | |
| dc.subject | EREW | |
| dc.subject | mesh of trees | |
| dc.subject | shared memory | |
| dc.subject | simulation | |
| dc.subject | work-optimal | |
| dc.subject | randomized | |
| dc.subject | coated mesh. | |
| dc.title | On Implementing EREW Work-Optimally on Mesh of Trees | |
| dc.type | Research Article |