Просмотр кода страницы Parallel Random Access Machine (PRAM)

'''Parallel Random Access Machine (PRAM)''' --- параллельная равнодоступная адресная машина (ПРАМ). 

A '''Parallel Random Access Machine''' (or '''PRAM''') is an abstract model of
parallel computation which can be used by parallel algorithms designers to estimate the inherent parellelism of a given problem.
PRAM neglects such issues as synchronization and communication, but provides any (problem size-dependent) number of processors.

An '''<math>(n,m)</math>PRAM''' consists of <math>n</math> processors
running synchronously and <math>m</math> memory locations, where each processor is a random-access machine.
All processors share the memory, and hence are commutative via it.
During a given cycle each processor may read an element from the shared memory into its local memory,
write an element from  its local memory to the shared memory, or perform any RAM operation on the data which it
already has in its local memory. It is a synchronous model, that is no processor will proceed with instruction <math>i+1</math>
until all have finished instruction <math>i</math>.


The read/write conflicts in accessing the same shared memory location simultaneously can be resolved by different strategies.
There is a family of PRAM models, each of which differs in its characteristics on this point. The members of the family are:

(1) the '''Exclusive Read Exclusive Write PRAM''' (or '''EREW PRAM'''), where every memory location can be read or written to by only one processor at a time,

(2) the '''Concurrent Read Exclusive Write PRAM''' (or '''CREW PRAM'''), where multiple processors may read a particular memory location,
but at most one processor may write to a particular memory location at a time,

(3) the '''Concurrent Read Concurrent Write PRAM''' (or '''CRCW PRAM'''), where multiple processors may read or write to any memory location.

The Exclusive Read Concurrent Write PRAMs are not considered, since a machine with enough power to support
concurrent writes should be able to support concurrent reads.

The read causes no discrepancies while the concurrent write is further defined as follows:

(1) the '''Common CRCW PRAM''', where all values written concur\-rent\-ly must be identical,

(2) the '''Arbitrary CRCW PRAM''', where the processor that suc\-ceeds in its concurrent write is chosen arbitrary
from the writing processors,

(3)the '''Priority CRCW PRAM''', where the processor that succeeds in its concurrent write is the processor
with the highest priority, e.g., the smallest processor index,

(4) the '''Combining CRCW PRAM''', where the value written is a linear combination of all values which
where concurrently written, e.g. a sum of the values. The values may be combined with any
associative and commutative operation which is computable in constant time on a RAM.