Parallel external memory
In computer science, a parallel external memory (PEM) model is a cache-aware, external-memory abstract machine.
≈ 5 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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. __TOC__ Let M=\{m_1,...,m_{d-1}\} be a vector of d-1 pivots sorted in increasing order. Let be an unordered set of N elements.
A d-way partition of is a set \Pi=\{A_1,...,A_d\} , where \cup_{i=1}^d A_i = A and A_i\cap A_j=\emptyset for 1\leq i . A_i is called the i-th bucket. The number of elements in A_i is greater than m_{i-1} and smaller than m_{i}^2 . In the following algorithm the input is partitioned into N/P-sized contiguous segments S_1,...,S_P in main memory.
The processor i primarily works on the segment S_i . The multiway partitioning algorithm ( PEM_DIST_SORT ) uses a PEM prefix sum algorithm to calculate the prefix sum with the optimal O\left(\frac{N}{PB} + \log P\right) I/O complexity. This algorithm simulates an optimal PRAM prefix sum algorithm. // Compute parallelly a d-way partition on the data segments S_i for each processor i in parallel do Read the vector of pivots into the cache.
Partition S_i into d buckets and let vector M_i=\{j_1^i,...,j_d^i\} be the number of items in each bucket. end for Run PEM prefix sum on the set of vectors \{M_1,...,M_P\} simultaneously. // Use the prefix sum vector to compute the final partition for each processor i in parallel do Write elements S_i into memory locations offset appropriately by M_{i-1} and M_{i} . end for Using the prefix sums stored in M_P the last processor P calculates the vector of bucket sizes and returns it. If the vector of 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 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. 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 Under the assumption that the input is stored in contiguous memory, PEMSELECT has an I/O complexity of: O\left(\frac{N}{PB} + \log (PB) \cdot \log(\frac{N}{P})\right) 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 for each processor in parallel do if M then d = M/B Load S_i in -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 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 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 end for The I/O complexity of PEMDISTSORT is: 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 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 f(N,P,d) = O\left ( \left \lceil \tfrac{N}{PB} \right \rceil \right ) and M the I/O complexity is then: O \left ( \frac{N}{PB} \log_{M/B} \frac{N}{B} \right ) | p \leq \frac {B^2 \log B \cdot \log^{O(1)} N}, M = B^{O(1)} |} Where \textrm{sort}_P(N) is the time it takes to sort items with processors in the PEM model.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1180384636 under CC BY-SA 4.0; modifications have been made.