PRAMs with variable word-size (Q1198062)

The Parallel Random Access Machine (PRAM) is one of the most widely used models of parallel computation. It abstracts the solution to a problem from details of communication and synchronization. The PRAM also abstracts the solution from the word-size of the processors and the memory. Its processors are assumed to be large enough to be able to perform the operations used, in constant time. Also the size of a memory word is assumed to be the same as the word-size of a processor. In this paper, the effect of relaxing the assumption of a fixed memory word-size is investigated and we show that this can lead to faster algorithms. We propose a model in which the processors can view the memory as made up of as ``small'' words (of contiguous bits) a deemed necessary. This ``fine- grained memory'' model will be called the M-PRAM. Like the PRAM, the M- PRAM can be EREW, CREW or CRCW depending on the restrictions on its memory accesses.