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

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:

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

Distribution sort

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

PEMDISTSORT pseudocode

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

Otherwise the following algorithm is used:

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

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

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

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

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

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