Parallel external memory

In computer science, a parallel external memory (PEM) model is a cache-aware, external-memory abstract machine.[1] It is the parallel-computing analogy to the single-processor external memory (EM) model. In a similar way, it is the cache-aware analogy to the parallel random-access machine (PRAM). The PEM model consists of a number of processors, together with their respective private caches and a shared main memory.

Read/write conflicts

In the PEM model, there is no direct communication network between the P processors. The processors have to communicate indirectly over the main memory. If multiple processors try to access the same block in main memory concurrently read/write conflicts[1] occur. Like in the PRAM model, three different variations of this problem are considered:

  • Concurrent Read Concurrent Write (CRCW): The same block in main memory can be read and written by multiple processors concurrently.
  • Concurrent Read Exclusive Write (CREW): The same block in main memory can be read by multiple processors concurrently. Only one processor can write to a block at a time.
  • Exclusive Read Exclusive Write (EREW): The same block in main memory cannot be read or written by multiple processors concurrently. Only one processor can access a block at a time.

Comparison to other models

Model Multi-core Cache-aware
Random-access machine (RAM) No No
Parallel random-access machine (PRAM) Yes No
External memory (EM) No Yes
Parallel external memory (PEM) Yes Yes

References

^ Jump up to:a b c d e f g h i j k l Arge, Lars; Goodrich, Michael T.; Nelson, Michael; Sitchinava, Nodari (2008). “Fundamental parallel algorithms for private-cache chip multiprocessors”. Proceedings of the Twentieth Annual Symposium on Parallelism in Algorithms and Architectures – SPAA ’08. New York, New York, USA: ACM Press: 197. doi:10.1145/1378533.1378573. ISBN 9781595939739.

  1. ^ Jump up to:ab c d Arge, Lars; Goodrich, Michael T.; Sitchinava, Nodari (2010). “Parallel external memory graph algorithms”. 2010 IEEE International Symposium on Parallel & Distributed Processing (IPDPS). IEEE: 1–11. doi:10.1109/ipdps.2010.5470440. ISBN 9781424464425.

Ofer Abarbanel – Executive Profile

Ofer Abarbanel online library

Ofer Abarbanel online library

Ofer Abarbanel online library

Ofer Abarbanel online library