FAST, EFFICIENT MUTUAL AND SELF SIMULATIONS FOR SHARED MEMORY AND RECONFIGURABLE MESH
作者:
YOSSI MATIAS,
ASSAF SCHUSTER,
期刊:
Parallel Algorithms and Applications
(Taylor Available online 1996)
卷期:
Volume 8,
issue 3-4
页码: 195-221
ISSN:1063-7192
年代: 1996
DOI:10.1080/10637199608915553
出版商: Taylor & Francis Group
数据来源: Taylor
摘要:
This paper studies relations between the parallel random access machine (PRAM) model, and the recon-figurable mesh (RMESH) model, by providing mutual simulations between the models. We present an algorithm simulating one step of an (nlglgn)-processor CRCW PRAM on ann×nRMESH with delayO(lglgn) with high probability. We use our PRAM simulation to obtain the first efficient self-simulation algorithm of an RMESH with general switches: An algorithm running on ann×nRMESH is simulated on ap×pRMESH with delayO((n/p)2× lgnlglgp) with high probability, which is optimal for allp≤n/√lgnlglgn. Finally, we consider the simulation of RMESH on the PRAM. We show that a 2 ×nRMESH can be optimally simulated on a CRCW PRAM in Θ(α(n)) time, where α(·) is the slow-growing inverse Ackermann function. In contrast, a PRAM with polynomial number of processors cannot simulate the 3 ×nRMESH in less than Ω(lgn/lglgn) expected time.
点击下载:
PDF (1880KB)
返 回