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 about finding the k-th smallest item in an unordered list ${\displaystyle A}$  of size ${\displaystyle N}$ . The following code^[1] 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 ${\displaystyle 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, 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^[1] 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

The I/O complexity of PEMDISTSORT is:

${\displaystyle O\left(\left\lceil {\frac {N}{PB}}\right\rceil \left(\log _{d}P+\log _{M/B}{\frac {N}{PB}}\right)+f(N,P,d)\cdot \log _{d}P\right)}$ 

where

${\displaystyle f(N,P,d)=O\left(\log {\frac {PB}{\sqrt {d}}}\log {\frac {N}{P}}+\left\lceil {\frac {\sqrt {d}}{B}}\log P+{\sqrt {d}}\log B\right\rceil \right)}$ 

If the number of processors is chosen that ${\displaystyle f(N,P,d)=O\left(\left\lceil {\tfrac {N}{PB}}\right\rceil \right)}$ and ${\displaystyle M<B^{O(1)}}$  the I/O complexity is then:

${\displaystyle O\left({\frac {N}{PB}}\log _{M/B}{\frac {N}{B}}\right)}$ 

Other PEM algorithms

PEM Algorithm	I/O complexity	Constraints
Mergesort[1]	${\displaystyle O\left({\frac {N}{PB}}\log _{\frac {M}{B}}{\frac {N}{B}}\right)={\textrm {sort}}_{P}(N)}$	${\displaystyle P\leq {\frac {N}{B^{2}}},M=B^{O(1)}}$
List ranking[2]	${\displaystyle O\left({\textrm {sort}}_{P}(N)\right)}$	${\displaystyle P\leq {\frac {N/B^{2}}{\log B\cdot \log ^{O(1)}N}},M=B^{O(1)}}$
Euler tour[2]	${\displaystyle O\left({\textrm {sort}}_{P}(N)\right)}$	${\displaystyle P\leq {\frac {N}{B^{2}}},M=B^{O(1)}}$
Expression tree evaluation[2]	${\displaystyle O\left({\textrm {sort}}_{P}(N)\right)}$	${\displaystyle P\leq {\frac {N}{B^{2}\log B\cdot \log ^{O(1)}N}},M=B^{O(1)}}$
Finding a MST[2]	${\displaystyle O\left({\textrm {sort}}_{P}(|V|)+{\textrm {sort}}_{P}(|E|)\log {\tfrac {|V|}{pB}}\right)}$	${\displaystyle p\leq {\frac {|V|+|E|}{B^{2}\log B\cdot \log ^{O(1)}N}},M=B^{O(1)}}$

Where ${\displaystyle {\textrm {sort}}_{P}(N)}$ is the time it takes to sort ${\displaystyle N}$ items with ${\displaystyle P}$ processors in the PEM model.

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.
2. Arge, Lars; Goodrich, Michael T.; Sitchinava, Nodari (2010). "Parallel external memory graph algorithms". 2010 IEEE International Symposium on Parallel & Distributed Processing (IPDPS). IEEE. doi:10.1109/ipdps.2010.5470440. ISBN 9781424464425.