Efficient Simulations Between Concurrent-Read Concurrent-Write PRAM Models

Abstract We give several simple and efficient algorithms for simulations of stronger CRCW PRAMs on weaker ones. The models that we consider are the well-known PRIORITY, ARBITRARY and COMMON PRAMs, and COLLISION and COLLISION +, defined by the property that a special collision symbol is stored in each memory cell into which more than one processor attempts to write, or more than one value is attempted to be written, respectively, in a given step. Our results are the following, where n denotes the number of processors of the simulated PRAM: 1) A O (1)-time simulation between any pair of models, provided that the simulating machine has O( n log n ) processors; 2) Two n -processor simulations: of PRIORITY on ARBITRARY with O(loglog n ) slowdown, and of PRIORITY on COLLISION + with O((loglog n ) 2 ) slowdown.

Authors

• Bogdan S. Chlebus
• Krzysztof Diks
• Torben Hagerup
• Tomasz Radzik

Keywords

No keywords are indexed for this paper.