There are several concurrency schemes that describe how parallelism can be performed. Concurrency schemes such as peer-to-peer, boss-worker, workpile, and pipeline describes how tasks distribute work in parallel. SIMD (Single Instruction Multiple Data) and MIMD (Multiple Instructions Multiple Data) are concurrency schemes that achieve data level parallelism.The PRAM (Parallel Random-Access Machine) is a simplified theoretical model that can be used to estimate an algorithm's performance. In the PRAM model there are N processors labeled as P1, P2, P3, . . . PN, that share one global memory. All the processors have simultaneous read and write access to shared global memory. Each of these theoretical processors can access the global shared memory in one uninterruptible unit of time. The PRAM model has four basic algorithmic approaches to access the shared global memory:

1. Concurrent read algorithms are allowed to read the same piece of memory simultaneously with no data corruption.
2. Concurrent write algorithms allow multiple processors to write to the shared memory.
3. Exclusive read algorithms are used to ensure that no two processors ever read the same memory location at the same time.
4. Exclusive write ensures that no two processors write to the same memory at the same time.

They can be combined into the following four strategies for possible read-write access:

• EREW (exclusive read and exclusive write)
• CREW (concurrent read and exclusive write)
• ERCW (exclusive read and concurrent write)
• CRCW (concurrent read and concurrent write)

These strategies can be viewed as access policy implemented by the tasks sharing the data and executed on multiple cores. Figure 1 shows these access policies.

Each of these four access policies requires different levels and types of synchronization. They can be analyzed on a continuum with the access policy that requires the least amount of synchronization to implement on one end and the access policy that requires the most synchronization at the other end. EREW, the simplest to implement, means access to the shared memory is serialized where only one task at a time is given access to the shared memory (write or read access). An example of EREW access policy is the producer-consumer. You may have thought CRCW was the simplest because it means access to memory without restriction. But this is the most difficult to implement and requires the most synchronization. The goal is to implement a synchronization process that maintains data integrity and satisfactory system performance. So its on the far end of the continuum.

CREW access policy allow multiple reads of the shared memory and exclusive writes. There are no restrictions on how many tasks can read the shared memory concurrently but only one task can write to the shared memory. Concurrent reads can occur while an exclusive write is taking place. With this access policy, each reading task may read a different value while another task is writing. This may be intended, it may not. ERCW access policy is direct reverse of CREW. Only one task can read the shared data but concurrent writes are allowed. Ahem...

Considering massive multicores, is this model too tired or too old or could it be America's next top model?