Parallel external memory

Parallel external memory (Model)

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.

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

PEMSELECT algorithm pseudocode

The code makes use of PRAMSORT which is a PRAM optimal sorting algorithm which runs in ${\displaystyle O(\log N)}$ , and SELECT, which is a cache optimal single-processor selection algorithm. 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, PEMSELECT has an I/O complexity of:

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

Distribution sort

Distribution sort partitions an input list ${\displaystyle A}$ of size ${\displaystyle N}$ into ${\displaystyle d}$ disjoint buckets of similar size. Every bucket is then sorted recursively and the results are combined into a fully sorted list.

If ${\displaystyle P=1}$ the task is delegated to a cache-optimal single-processor sorting algorithm.

Otherwise the following algorithm is used:

// Sample ${\displaystyle {\tfrac {4N}{\sqrt {d}}}}$ elements from ${\displaystyle A}$ 
for each processor ${\displaystyle i}$ in parallel do
  if ${\displaystyle M<|S_{i}|}$ then
    ${\displaystyle d=M/B}$ 
    Load ${\displaystyle S_{i}}$ in ${\displaystyle M}$ -sized pages and sort pages individually
  else
    ${\displaystyle d=|S_{i}|}$ 
    Load and sort ${\displaystyle S_{i}}$ as single page
  end if
  Pick every ${\displaystyle {\sqrt {d}}/4}$ 'th element from each sorted memory page into contiguous vector ${\displaystyle R^{i}}$ of samples
end for 

in parallel do
  Combine vectors ${\displaystyle R^{1}\dots R^{P}}$ into a single contiguous vector ${\displaystyle {\mathcal {R}}}$ 
  Make ${\displaystyle {\sqrt {d}}}$ copies of ${\displaystyle {\mathcal {R}}}$ : ${\displaystyle {\mathcal {R}}_{1}\dots {\mathcal {R}}_{\sqrt {d}}}$ 
end do

// Find ${\displaystyle {\sqrt {d}}}$ pivots ${\displaystyle {\mathcal {M}}[j]}$ 
for ${\displaystyle j=1}$ to ${\displaystyle {\sqrt {d}}}$ in parallel do
  ${\displaystyle {\mathcal {M}}[j]={\texttt {PEMSELECT}}({\mathcal {R}}_{i},{\tfrac {P}{\sqrt {d}}},{\tfrac {j\cdot 4N}{d}})}$ 
end for

Pack pivots in contiguous array ${\displaystyle {\mathcal {M}}}$ 

// Partition ${\displaystyle A}$ around pivots into buckets ${\displaystyle {\mathcal {B}}}$ 
${\displaystyle {\mathcal {B}}={\texttt {PEMMULTIPARTITION}}(A[1:N],{\mathcal {M}},{\sqrt {d}},P)}$ 

// Recursively sort buckets
for ${\displaystyle j=1}$ to ${\displaystyle {\sqrt {d}}+1}$ in parallel do
  recursively call ${\displaystyle {\texttt {PEMDISTSORT}}}$ on bucket ${\displaystyle j}$ of size ${\displaystyle {\mathcal {B}}[j]}$ 
  using ${\displaystyle O\left(\left\lceil {\tfrac {{\mathcal {B}}[j]}{N/P}}\right\rceil \right)}$ processors responsible for elements in bucket ${\displaystyle j}$ 
end for

PEMDISTSORT pseudocode
Lorem Ipsum

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

Other algorithms

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

See also

• ...

References

1. 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. doi:10.1145/1378533.1378573. ISBN 9781595939739.