Parallel external memory: Difference between revisions

Revision as of 20:32, 21 January 2019

Revision as of 20:56, 21 January 2019

Line 20:

=== Selection ===

The [[selection problem]] is toabout findfinding the kthk-th smallest item in an unordered list <math>A</math> of size <math>N</math>.

{{Collapse|1=

The following code<ref name=":0" /> makes use of <code>PRAMSORT</code> which is a PRAM optimal sorting algorithm which runs in <math>O(\log N)</math>, and <code>SELECT</code>, which is a cache optimal single-processor selection algorithm.

'''if''' <math>N \leq P</math> '''then'''

<math>\texttt{PRAMSORT}(A,P)</math>

Line 56:

If <math>P = 1</math> the task is delegated to a cache-optimal single-processor sorting algorithm.

Otherwise the following algorithm<ref name=":0" /> is used:

// Sample <math>\tfrac{4N}{\sqrt{d}}</math> elements from <math>A</math>

'''for''' '''each''' processor <math>i</math> '''in parallel do'''

Line 88:

recursively call <math>\texttt{PEMDISTSORT}</math> on bucket <math>j</math>of size <math>\mathcal{B}[j]</math>

using <math>O \left( \left \lceil \tfrac{\mathcal{B}[j]}{N / P} \right \rceil \right)</math> processors responsible for elements in bucket <math>j</math>

'''end for'''|<code>PEMDISTSORT</code> pseudocode}}<br />The I/O complexity of <code>PEMDISTSORT</code> is:

'''end for'''

|<code>PEMDISTSORT</code> pseudocode}}<br />The I/O complexity of <code>PEMDISTSORT</code> is:

<math>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)</math>