Parallel external memory

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.

The PEM model is a combination of the EM model and the PRAM model. The PEM model is a computation model which consists of ${\displaystyle P}$ processors and a two-level memory hierarchy. This memory hierarchy consists of a large external memory (main memory) of size ${\displaystyle N}$ and ${\displaystyle P}$ small internal memories (caches). The processors share the main memory. Each cache is exclusive to a single processor. A processor can't access another’s cache. The caches have a size ${\displaystyle M}$ which is partitioned in blocks of size ${\displaystyle B}$. The processors can only perform operations on data which are in their cache. The data can be transferred between the main memory and the cache in blocks of size ${\displaystyle B}$.

The complexity measure of the PEM model is the I/O complexity, which determines the number of parallel blocks transfers between the main memory and the cache. During a parallel block transfer each processor can transfer a block. So if ${\displaystyle P}$ processors load parallelly a data block of size ${\displaystyle B}$ form the main memory into their caches, it is considered as an I/O complexity of ${\displaystyle O(1)}$ not ${\displaystyle O(P)}$. A program in the PEM model should minimize the data transfer between main memory and caches and operate as much as possible on the data in the caches.

In the PEM model, there is no direct communication network between the P processors. The processors have to communicate indirectly over the main memory. If multiple processors try to access the same block in main memory concurrently read/write conflicts occur. Like in the PRAM model, three different variations of this problem are considered:

The following two algorithms solve the CREW and EREW problem if ${\displaystyle P\leq B}$ processors write to the same block simultaneously. A first approach is to serialize the write operations. Only one processor after the other writes to the block. This results in a total of ${\displaystyle P}$ parallel block transfers. A second approach needs ${\displaystyle O(\log(P))}$ parallel block transfers and an additional block for each processor. The main idea is to schedule the write operations in a binary tree fashion and gradually combine the data into a single block. In the first round ${\displaystyle P}$ processors combine their blocks into ${\displaystyle P/2}$ blocks. Then ${\displaystyle P/2}$ processors combine the ${\displaystyle P/2}$ blocks into ${\displaystyle P/4}$. This procedure is continued until all the data is combined in one block.

Let ${\displaystyle M=\{m_{1},...,m_{d-1}\}}$ be a vector of d-1 pivots sorted in increasing order. Let A be an unordered set of N elements. A d-way partition of A is a set ${\displaystyle \Pi =\{A_{1},...,A_{d}\}}$ , where ${\displaystyle \cup _{i=1}^{d}A_{i}=A}$ and ${\displaystyle A_{i}\cap A_{j}=\emptyset }$ for ${\displaystyle 1\leq i<j\leq d}$. ${\displaystyle A_{i}}$ is called the i-th bucket. The number of elements in ${\displaystyle A_{i}}$ is greater than ${\displaystyle m_{i-1}}$ and smaller than ${\displaystyle m_{i}^{2}}$. In the following algorithm the input is partitioned into N/P-sized contiguous segments ${\displaystyle S_{1},...,S_{P}}$ in main memory. The processor i primarily works on the segment ${\displaystyle S_{i}}$. The multiway partitioning algorithm (PEM_DIST_SORT) uses a PEM prefix sum algorithm to calculate the prefix sum with the optimal ${\displaystyle O\left({\frac {N}{PB}}+\log P\right)}$ I/O complexity. This algorithm simulates an optimal PRAM prefix sum algorithm.

If the vector of ${\displaystyle d=O\left({\frac {M}{B}}\right)}$ pivots M and the input set A are located in contiguous memory, then the d-way partitioning problem can be solved in the PEM model with ${\displaystyle O\left({\frac {N}{PB}}+\left\lceil {\frac {d}{B}}\right\rceil >\log(P)+d\log(B)\right)}$ I/O complexity. The content of the final buckets have to be located in contiguous memory.

The selection problem is about finding the k-th smallest item in an unordered list A of size N. The following 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.