External sorting – Wikipedia

External sorting Describes sorting algorithms, which are designed for very large amounts of data. Algorithms that work on large amounts of data that do not fit in the main memory are generally referred to as external memory algorithms.
In the analysis of classic sorting algorithms (e.g. Quicksort), no memory hierarchy or access to data on different rapid data carriers is usually taken into account.
However, the structure and hierarchy of the memory and the handling of the algorithms with this is crucial for the performance when sorting large amounts of data.

after-content-x4

A common model for viewing external memory algorithms is the parallel disk model (PDM). ^[first]This has a main memory of the size

{displaystyle M}

$M$ And one or more external memory of unlimited size, the so -called disks. The data of the size to be sorted can be found on these

{displaystyle N}

$N$ Place. The number of disks is often used to simplify

{displaystyle D=1}

$D=1$ Suppose and referred to the simplified model as External Memory Model (EMM). Aggarwal and Vitter also originally presented the model with a single disk but several parallel writing read heads. ^[2]The main memory as well as the external memory have a block size

{displaystyle B}

$B$ . With an IO operation, can
one block per disk loaded into the main memory or returned to the external memory. The input size also becomes a better overview

{Displaystyle n = n/b}

${displaystyle n=N/B}$ as well as the size of the main storage

{displaystyle m=M/B}

${displaystyle m=M/B}$ indicated in blocks. In contrast to the analysis of classic sorting algorithms, the performance of an algorithm is not measured against the number of all operations, but only specified by the number of IO operations.

after-content-x4

For sorting in the PDM, a generally applicable barrier can be specified for the number of IO operations. ^[first]This is in the case of a single or more disks (

{displaystyle Dgeq 1}

${displaystyle Dgeq 1}$ ) given by:

{displaystyle Theta left({frac {N}{DB}}log _{M/B}{frac {N}{B}}right)=Theta left({frac {n}{D}}log _{m}nright)}

In practice is

{Displaystyle log _ {m} n}

${displaystyle log _{m}n}$ A little constant. For the atypical case

{Displaystyle Blog M = O (log n)}

${displaystyle Blog m=o(log n)}$ This barrier only applies to comparison -based procedures.

Merge Sort [ Edit | Edit the source text ]

The classic Merge Sort is based External Memory Merge Sort . ^[first]^[3]First of all, the algorithm for

{displaystyle D=1}

$D=1$ to be viewed as. Data segments are consisting of one after the other

{displaystyle m}

$m$ Blocks are loaded in the main memory, sorted there and written back into the external memory as a so -called run.
The

{displaystyle N/M}

${displaystyle N/M}$ Runs in the external memory are then available using a K-way merges

{Displaystyle log _ {m} n}

${displaystyle log _{m}n}$ Recursion levels summarized.

Simplified representation of the Merge Sorts . First the individual runs are sorted in the main memory, then the Runs are Gemerged.

for j = 1 to n/m
     Load the next data segment of size  ${displaystyle M}$ in the main memory
     Sorting data in the main memory
     Write sorted data as run   ${displaystyle r_{1,j}}$ on external memory
 end

for i=1 to  ${displaystyle lceil log _{m}nrceil }$ for j=1 to  ${displaystyle lceil |r_{i}|/(m)rceil }$ Upload the first blocks of the runs  ${displaystyle r_{i,(j-1)(m)+1}...r_{i,j(m)}}$ in Merge-Buffer
         while Merge-Buffer nicht leer
             Merge runs  ${displaystyle r_{i,(j-1)(m)+1}...r_{i,j(m)}}$ Write output buffer in external memory if full
             Charge the next block in main memory if a merge buffer is already completely mixed
         end
     end
 end

In order to use several parallel disks as efficiently as possible and to adhere to the barrier described above, in every IO step must

{displaystyle D}

$D$ Blocks are moved.
For the efficient writing of the blocks back to the disks, the size of the internal buffer in the main memory, which contains the mixed elements, is on

{displaystyle D}

$D$ Blocks expanded. In order to ensure a higher throughput even when reading, a Prefetching buffer is also added.
If the elements were cleverly distributed on the individual disks in the previous steps and a suitable prefetching strategy was chosen, a buffer size of

{displaystyle Theta (D)}

${displaystyle Theta (D)}$ Blocks.

Distribution Sort [ Edit | Edit the source text ]

Analogous to Merge Sort Is that too Distribution Sort A recursive algorithm. ^[first]^[3]The data should be after

{displaystyle S-1}

${displaystyle S-1}$ Partitionierungselementen in

{displaystyle S}

$S$ Buckets are divided. It applies that all elements are smaller within a bucket than any element in the following.
This partitioning is then repeated recursively for the individual buckets. If the goats are small enough to be completely loaded into the main memory, they are sorted there. The concentration of the sorted buckets thus forms the sorted order of the entire data.

The choice of the partitioning elements is crucial to maintain the same size as possible and thus ensure good performance. This can be done, for example, in a probabilistic way.
A small, random amount of elements is sorted and the partitioning elements are selected from it. The size of the amount is chosen so that the sorting of it for the number of IO operations is negligible and has no influence on the barrier.
With good partitioning, the depth of recursion is

{Displaystyle o (log _ {s} n)}

${displaystyle O(log _{S}n)}$ . Since a buffer in the main memory is required for each bucket, can

{displaystyle S}

$S$ through

{displaystyle Theta (m)}

${displaystyle Theta (m)}$ to be estimated.

In order to fulfill the barrier given above, only at each recursion level

{displaystyle Theta (n/D)}

${displaystyle Theta (n/D)}$ IO operations are executed. In order to efficiently load a bucket into the main memory, its blocks must have been distributed evenly on the various disks.
The blocks belonging to the various goats are either written together as a stripe from the output buffer in the main memory on the external memory or a stripe per bucket is created. In the case of a stripes per bucket, with the help of Randomized Cycling It is ensured that the next blocks of the different buckets have to be written on the most different disks. This variant will also Randomized Cycling Distribution Sort called.

Basically, operations for sorting take up a large part of the computing effort. ^[3]In recent years, the amounts of data on which are expected have increased steadily. ^[first]External memory algorithms are necessary to cope with these amounts of data. Efficient external sorting is of particular importance, since many external memory algorithms are based on sorting processes.

↑ ^a^b^c^d^{It is} Jeffrey Scott Vitter: Algorithms and data structures for external memory . In: Foundations and Trends in Theoretical Computer Science . 2nd year, No. 4 , 2008, S. 30–474 .
↑ Alok Aggarwal, Jeffrey Scott Vitter: The input/output complexity of sorting and related problems . In: Communications of the ACM . 31st year, No. 9 , 1988, S. 1116–1127 .
↑ ^a^b^c Donald Knuth: The Art of Programming, Vol. 3 (Sorting and Searching) . Addison-Wesley, 1973.

[vitter-1] {It is} Jeffrey Scott Vitter: Algorithms and data structures for external memory . In: Foundations and Trends in Theoretical Computer Science . 2nd year, No. 4 , 2008, S. 30–474 .

[aggarwal-2] Alok Aggarwal, Jeffrey Scott Vitter: The input/output complexity of sorting and related problems . In: Communications of the ACM . 31st year, No. 9 , 1988, S. 1116–1127 .

[knuth-3] Donald Knuth: The Art of Programming, Vol. 3 (Sorting and Searching) . Addison-Wesley, 1973.

External sorting – Wikipedia

Merge Sort [ Edit | Edit the source text ]

Distribution Sort [ Edit | Edit the source text ]

Recent Posts

Recent Comments

Archives

Categories

Meta