Parallel external memory: Difference between revisions

Revision as of 17:39, 21 January 2019

Revision as of 17:47, 21 January 2019

Line 22:

The selection problem is to find an item in an unordered list <math>A</math> of size <math>N</math>which is bigger than <math>k-1</math>other elements in <math>A</math>.

{{Collapse|1=

The code 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.

&nbsp;

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

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

Line 45:

'''end if'''

&nbsp;

|2=PEM selection<code>PEMSELECT</code> algorithm pseudocode}}

Under the assumption that the input is stored in contiguous memory, <code>PRAMSORTPEMSELECT</code> runs in <math>O(\log N)</math>, and <code>SELECT</code> is a cache optimal single-processor selection algorithm, this algorithm has an I/O complexity of:

<math>O(\frac{N}{PB} + \log PB \cdot \log(\frac{N}{P}))</math><br />