Efficient Deterministic and Probabilistic Simulations of PRAMs on Linear Arrays with Reconfigurable Pipelined Bus Systems |
| |
Authors: | Li Keqin Pan Yi Zheng Si Qing |
| |
Affiliation: | (1) Department of Mathematics and Computer Science, State University of New York, New Paltz, NY, 12561;(2) Department of Computer Science, University of Dayton, Dayton, OH, 45469;(3) Department of Computer Science, University of Texas at Dallas, Richardson, TX, 75083 |
| |
Abstract: | In this paper, we present deterministic and probabilistic methods for simulating PRAM computations on linear arrays with reconfigurable pipelined bus systems (LARPBS). The following results are established in this paper. (1) Each step of a p-processor PRAM with m=O(p) shared memory cells can be simulated by a p-processors LARPBS in O(log p) time, where the constant in the big-O notation is small. (2) Each step of a p-processor PRAM with m= (p) shared memory cells can be simulated by a p-processors LARPBS in O(log m) time. (3) Each step of a p-processor PRAM can be simulated by a p-processor LARPBS in O(log p) time with probability larger than 1–1/pc for all c>0. (4) As an interesting byproduct, we show that a p-processor LARPBS can sort p items in O(log p) time, with a small constant hidden in the big-O notation. Our results indicate that an LARPBS can simulate a PRAM very efficiently. |
| |
Keywords: | Concurrent read concurrent write deterministic simulation linear array optical bus parallel random access machine probabilistic simulation shared memory sorting time complexity |
本文献已被 SpringerLink 等数据库收录! |
|