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}$ .

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

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