首页   按字顺浏览 期刊浏览 卷期浏览 FAST, EFFICIENT MUTUAL AND SELF SIMULATIONS FOR SHARED MEMORY AND RECONFIGURABLE MESH
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)



返 回