Parallel external memory

Parallel external memory (Model)

In computer science, a parallel external memory (PEM) model is a cache-aware, external-memory abstract machine. 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.

Model

...

Read / Write conflicts

...

Complexity measure

...

Examples

Prefixsum

...

Multiway partitioning

...

Selection

The selection problem is to find an item in an unordered list $A$ of size $N$which is bigger than $k-1$ other elements in $A$.

PEMSELECT algorithm pseudocode

The code makes use of PRAMSORT which is a PRAM optimal sorting algorithm which runs in $O(\log N)$, and SELECT, which is a cache optimal single-processor selection algorithm. if $N\leq P$then ${\texttt {PRAMSORT}}(A,P)$ return $A[k]$ end if for each processor i in parallel do //Find median of each $S_{i}$ $m_{i}={\texttt {SELECT}}(S_{i},{\frac {N}{2P}})$ end for // Sort medians ${\texttt {PRAMSORT}}(\lbrace m_{1},\dots ,m_{2}\rbrace ,P)$ // Partition around median of medians $t={\texttt {PEMPARTITION}}(A,m_{P/2},P)$ if $k\leq t$then return ${\texttt {PEMSELECT}}(A[1:t],P,k)$ else return ${\texttt {PEMSELECT}}(A[t+1:N],P,k-t)$ end if

Under the assumption that the input is stored in contiguous memory, PEMSELECT has an I/O complexity of:

$O({\frac {N}{PB}}+\log PB\cdot \log({\frac {N}{P}}))$

Distribution sort

...

Other algorithms

Algorithm	Description	I/O complexity	Space complexity
PEM Mergesort	Sorts a list of items	$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)}$	$O(N)$