Content deleted Content added
No edit summary |
|||
Line 1:
= Parallel external memory (Model) =
In computer science, a '''parallel external memory (PEM) model''' is a [[Cache-aware model|cache-aware]], external-memory [[abstract machine]].<ref name=":0">{{Cite journal|last=Arge|first=Lars|last2=Goodrich|first2=Michael T.|last3=Nelson|first3=Michael|last4=Sitchinava|first4=Nodari|date=2008|title=Fundamental parallel algorithms for private-cache chip multiprocessors|url=http://dx.doi.org/10.1145/1378533.1378573|journal=Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures - SPAA '08|___location=New York, New York, USA|publisher=ACM Press|doi=10.1145/1378533.1378573|isbn=9781595939739}}</ref> It is the parallel-computing analogy to the single-processor [[External memory algorithm|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.
== Model ==
Line 54:
== Other algorithms ==
{| class="wikitable"
|+
!Algorithm
!Description
!
!Space complexity
|-
!PEM Mergesort<ref name=":0" />
|Sorts a list of items
|<math>O\left(\frac{N}{PB} \log_{\frac{M}{B}} \frac{N}{B}\right) \textrm{ if } \; P \leq \frac{N}{B^2}, M = B^{O(1)}</math>
|<math>O(N)</math>
|-
!
|
|
|
|-
!
|
|
| |||