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