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 ${\displaystyle A}$  of size ${\displaystyle N}$ which is bigger than ${\displaystyle k-1}$ other elements in ${\displaystyle A}$ .

PEM selection algorithm pseudocode

if ${\displaystyle N\leq P}$ then ${\displaystyle {\texttt {PRAMSORT}}(A,P)}$  return ${\displaystyle A[k]}$  end if for each processor i in parallel do //Find median of each ${\displaystyle S_{i}}$  ${\displaystyle m_{i}={\texttt {SELECT}}(S_{i},{\frac {N}{2P}})}$  end for // Sort medians ${\displaystyle {\texttt {PRAMSORT}}(\lbrace m_{1},\dots ,m_{2}\rbrace ,P)}$  // Partition around median of medians ${\displaystyle t={\texttt {PEMPARTITION}}(A,m_{P/2},P)}$  if ${\displaystyle k\leq t}$ then return ${\displaystyle {\texttt {PEMSELECT}}(A[1:t],P,k)}$  else return ${\displaystyle {\texttt {PEMSELECT}}(A[t+1:N],P,k-t)}$  end if

Template:collapse is not available for use in articles (see MOS:COLLAPSE).

Under the assumption that the input is stored in contiguous memory, PRAMSORT runs in ${\displaystyle O(\log N)}$ , and SELECT is a cache optimal single-processor selection algorithm, this algorithm has an I/O complexity of:

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

Distribution sort

...

Other algorithms

Algorithm	Time complexity	Space complexity