Parallel Random-access Machine - Read/write Conflicts

Read/write Conflicts

Read/write conflicts in accessing the same shared memory location simultaneously are resolved by one of the following strategies:

  1. Exclusive read exclusive write (EREW)—every memory cell can be read or written to by only one processor at a time
  2. Concurrent read exclusive write (CREW)—multiple processors can read a memory cell but only one can write at a time
  3. Exclusive read concurrent write (ERCW)—never considered
  4. Concurrent read concurrent write (CRCW)—multiple processors can read and write. A CRCW PRAM is sometimes called a concurrent random-access machine.

Here, E and C stand for 'exclusive' and 'concurrent' respectively. The read causes no discrepancies while the concurrent write is further defined as:

Common—all processors write the same value; otherwise is illegal
Arbitrary—only one arbitrary attempt is successful, others retire
Priority—processor rank indicates who gets to write
Another kind of array reduction operation like SUM, Logical AND or MAX.

Several simplifying assumptions are made while considering the development of algorithms for PRAM. They are:

  1. There is no limit on the number of processors in the machine.
  2. Any memory location is uniformly accessible from any processor.
  3. There is no limit on the amount of shared memory in the system.
  4. Resource contention is absent.
  5. The programs written on these machines are, in general, of type MIMD. Certain special cases such as SIMD may also be handled in such a framework.

These kinds of algorithms are useful for understanding the exploitation of concurrency, dividing the original problem into similar sub-problems and solving them in parallel.

Read more about this topic:  Parallel Random-access Machine

Famous quotes containing the words read, write and/or conflicts:

    “Philosophy ... does not talk, but write, or, when it comes personally before an audience, lecture or read; and therefore it must be read to-morrow, or a thousand years hence. But the talker must naturally be attended to at once; he does not talk on without an audience; the winds do not long bear the sound of his voice.”
    —Henry David Thoreau (1817–1862)

    “Nine-tenths of the value of a sense of humor in writing is not in the things it makes one write but in the things it keeps one from writing. It is especially valuable in this respect in serious writing, and no one without a sense of humor should ever write seriously. For without knowing what is funny, one is constantly in danger of being funny without knowing it.”
    —Robert Benchley (1889–1945)

    “They [parents] can help the children work out schedules for homework, play, and television that minimize the conflicts involved in what to do first. They can offer moral support and encouragement to persist, to try again, to struggle for understanding and mastery. And they can share a child’s pleasure in mastery and accomplishment. But they must not do the job for the children.”
    —Dorothy H. Cohen (20th century)