Benutzer:ParAlgMergeSort/sandbox/Parallel merge sort deutsch

Paralleler Mergesort

Bearbeiten

Mergesort lässt sich aufgrund des Teile-und-herrsche Ansatzes gut parallelisieren. Verschiedene parallele Varianten wurden in der Vergangenheit entwickelt. Manche sind stark verwandt mit der hier vorgestellten sequentiellen Variante, während andere eine grundlegend verschiedene Struktur besitzen und das K-Wege-Mischen verwenden.

Mergesort mit parallelen Rekursionsaufrufen

Bearbeiten

Der sequentielle Mergesort kann in zwei Phasen beschrieben werden, die Teilen-Phase und die anschließende Misch-Phase. Die Erste besteht aus vielen rekursiven Aufrufen, die immer wieder den gleichen Aufteilungsprozess durchführen, bis die Teilsequenzen trivial sortiert sind (mit einem oder keinem Element). Ein intuitiver Ansatz ist es, diese rekursiven Aufrufe zu parallelisieren.[1] Der folgende Pseudocode beschreibt den klassischen Mergesort Algorithmus mit paralleler Rekursion unter Verwendung der Schlüsselwörter fork and join.

// Sort elements lo through hi (exclusive) of array A.
algorithm mergesort(A, lo, hi) is
    if lo+1 < hi then  // Two or more elements.
        mid := ⌊(lo + hi) / 2⌋
        fork mergesort(A, lo, mid)
        mergesort(A, mid, hi)
        join
        merge(A, lo, mid, hi)

Dieser Algorithmus ist die triviale Modifikation des sequentiellen Algorithmus und ist noch nicht optimal. Sein Speedup ist dementsprechend auch nicht beeindruckend. Er hat einen Spann von  , was nur eine Verbesserung um den Faktor   ist im Vergleich zur sequentiellen Version (siehe auch Introduction to Algorithms). Dies liegt hauptsächlich an der sequentiellen Mischmethode, welche der Flaschenhals in der parallelen Ausführung ist.

Mergesort mit paralleler Mischmethode

Bearbeiten

Ein besserer Parallelismus kann durch eine parallele Mischmethode erreicht werden. Cormen et al. präsentieren eine binäre Variante, welche zwei sortierte Teilsequenzen in eine sortierte Ausgabesequenz mischt. Eine ausführlichere Beschreibung findet sich hier. [1]

In der längeren der beiden Sequenzen (falls ungleich lang) wird das Element des mittleren Indexes ausgewählt. Seine Position in der anderen Sequenz wird auf die Weise bestimmt, dass die Sequenz sortiert bliebe, wenn dieses Element an bestimmten Stelle eingefügt werden würde. So weiß man wie viele Elemente insgesamt kleiner sind als das Pivot Element und die finale Position des Pivots kann in der Ausgabesequenz berechnet werden. Für die so erzeugten Teilfolgen der kleineren und größeren Elemente wird die Mischmethode wieder parallel ausgeführt, bis der Basisfall der Rekursion erreicht ist.

Der folgende Pseudocode illustriert die modifizierte parallele Mischmethode (aus Cormen et al.).

/**
 * A: Input array
 * B: Output array
 * lo: lower bound
 * hi: upper bound
 * off: offset
 */
algorithm parallelMergesort(A, lo, hi, B, off) is
    len := hi - lo + 1
    if len == 1 then
        B[off] := A[lo]
    else let T[1..len] be a new array
        mid := ⌊(lo + hi) / 2⌋ 
        mid' := mid - lo + 1
        fork parallelMergesort(A, lo, mid, T, 1)
        parallelMergesort(A, mid + 1, hi, T, mid' + 1) 
        join 
        parallelMerge(T, 1, mid', mid' + 1, len, B, off)

Um eine Rekurrenzrelation für den Worst Case zu erhalten müssen die rekursiven Aufrufe von parallelMergesort aufgrund der parallelen Ausführung nur einmal aufgeführt werden. Man erhält

 .

Die Lösung dieser Rekurrenz ist

 .

Dieser Algorithmus erreicht eine Parallelisierbarkeit von  , was um einiges besser ist als der Parallelismus des vorherigen Algorithmus. Solch ein Sortieralgorithmus kann, wenn er mit einem schnellen stabilen sequentiellen Sortieralgorithmus und einer sequentiellen Mischmethode als Basisfall für das Mischen von zwei kleinen Sequenzen ausgestattet ist gut in der Praxis funktionieren.[2]

Paralleler Mehrwege-Mergesort

Bearbeiten

Es wirkt unnatürlich, Mergesort Algorithmen auf binäre Mischmethoden zu beschränken, da oftmals mehr als zwei Prozessoren zur Verfügung stehen. Ein besserer Ansatz wäre es, ein K-Wege-Mischen zu realisieren. Diese Generalisierung mischt   sortierte Sequenzen zu einer sortierten Sequenz und ist dementsprechend eine Generalisierung des binären Mischens. Diese Misch-Variante eignet sich gut zur Beschreibung eines Sortieralgorithmus auf einem PRAM.[3][4]

Grundidee

Bearbeiten
 
Der parallele Mehrwege-Mergesort Algorithmus auf vier Prozessoren   bis  .

Gegeben sei eine Folge von   Elementen. Ziel ist es, diese Sequenz mit   verfügbaren Prozessoren zu sortieren. Die Elemente sind dabei gleich auf alle Prozessoren aufgeteilt und werden zunächst lokal mit einem sequentiellen Sortieralgorithmus vorsortiert. Dementsprechend bestehen die Daten nun aus sortierten Folgen   der Länge  . Der Einfachheit halber sei   eine Vielfaches von  , so dass für   gilt:  . Jede dieser Sequenzen wird wiederum in   Teilsequenzen   partitioniert, indem für   die Trennelemente   mit globalem Rang   bestimmt werden. Die korrespondierenden Indizes werden in jeder Folge   mit binärer Sucher ermittelt, sodass die Folgen anhand der Indizes aufgeteilt werden könne. Formal definiert gilt somit  .

Nun werden die Elemente von  dem Prozessor   zugeteilt. Dies sind alle Elemente vom globalen Rang   bis zum Rang  , die über die   verteilt sind. So erhält erhält jeder Prozessor eine Folge von sortierten Sequenzen. Aus der Tatsache, dass der Rang   der Trennelemente   global gewählt wurde, ergeben sich zwei wichtige Eigenschaften: Zunächst sind die Trennelemente so gewählt, dass jeder Prozessor nach der Zuteilung der neuen Daten immer noch mit   Elementen betraut ist. Der Algorithmus besitzt also eine perfekte Lastverteilung. Außerdem sind alle Elemente des Prozessors   kleiner oder gleich der Elemente des Prozessors  . Wenn nun jeder Prozessor ein p-Wege-Mischen lokal durchführt, sind aufgrund dieser Eigenschaft die Elemente global sortiert. Somit müssen die Ergebnisse nur in der Reihenfolge der Prozessoren zusammengesetzt werden.

Trennelementbestimmung

Bearbeiten

In der einfachsten Form sind   sortierte Folgen   gleichverteilt auf   Prozessoren sowie ein Rang   gegeben. Gesucht ist nun ein Trennelement   mit globalem Rang   in der Vereinigung der Folgen. Damit kann jede Folge   an einem Index   in zwei Teile aufgeteilt werden: Der untere Teil besteht nur aus Elementen, die kleiner   sind, während der obere Teil alle Elemente enthält, welche größer oder gleich als   sind.

Der hier vorgestellte sequentielle Algorithmus gibt die Indizes der Trennungen zurück, also die Indizes  in den Folgen  , sodass   einen global kleineren Rang als   hat und   ist.[5]

algorithm msSelect(S : Array of sorted Sequences [S_1,..,S_p], k : int) is
    for i = 1 to p do 
	(l_i, r_i) = (0, |S_i|-1)
	
    while there exists i: l_i < r_i do
	//pick Pivot Element in S_j[l_j],..,S_j[r_j], chose random j uniformly
	v := pickPivot(S, l, r)
	for i = 1 to p do 
	    m_i = binarySearch(v, S_i[l_i, r_i]) //sequentially
	if m_1 + ... + m_p >= k then //m_1+ ... + m_p is the global rank of v
	    r := m  //vector assignment
	else
	    l := m 
	
    return l

Für die Komplexitätsanalyse wurde das PRAM-Modell gewählt. Die p-fache Ausführung der binarySearch Methode hat eine Laufzeit in  , falls die Daten über alle   Prozessoren gleichverteilt anliegen. Die erwartete Rekursionstiefe beträgt wie im Quickselect Algorithmus  . Somit ist die gesamte erwartete Laufzeit  .

Angewandt auf den parallelen Mehrwege-Mergesort muss die msSelect Methode parallel ausgeführt werden, um alle Trennelemente vom Rang   gleichzeitig zu finden. Dies kann anschließend verwendet werden, um jede Folge in   Teile zu zerschneiden. Es ergibt sich die gleiche Gesamtlaufzeit  .

Pseudocode

Bearbeiten

Hier ist der komplette Pseudocode für den parallelen Mehrwege-Mergesort. Dabei wird eine Barriere-Synchronisation vor und nach der Trennelementbestimmung angenommen, sodass jeder Prozessor seine Trennelemente und die Partitionierung seiner Sequenz richtig berechnen kann.

/**
 * d: Unsorted Array of Elements
 * n: Number of Elements
 * p: Number of Processors
 * return Sorted Array
 */
algorithm parallelMultiwayMergesort(d : Array, n : int, p : int) is
    o := new Array[0, n]                         // the output array
    for i = 1 to p do in parallel                // each processor in parallel
        S_i := d[(i-1) * n/p, i * n/p] 	         // Sequence of length n/p
	sort(S_i)                                // sort locally
        synch
	v_i := msSelect([S_1,...,S_p], i * n/p)          // element with global rank i * n/p
        synch
	(S_i,1 ,..., S_i,p) := sequence_partitioning(si, v_1, ..., v_p) // split s_i into subsequences
	    
	o[(i-1) * n/p, i * n/p] := kWayMerge(s_1,i, ..., s_p,i)  // merge and assign to output array
	
    return o

Zunächst sortiert jeder Prozessor die zugewiesenen   Elemente lokal mit einem vergleichsbasiertem Sortieralgorithmus der Komplexität  . Anschließend können die Trennelemente in Zeit   bestimmt werden. Schließlich müssen jede Gruppe von   Teilstücken gleichzeitig von jedem Prozessor zusammen gemischt werden. Dies hat eine Laufzeit von  , indem ein sequentieller k-Wege Mischalgorithmus verwendet wird. Somit ergibt sich eine Gesamtlaufzeit von

 .

Praktische Anpassung und Anwendung

Bearbeiten

Der Mehrwege-Mergesort Algorithmus ist durch seine hohe Parallelität, was den Einsatz vieler Prozessoren ermöglicht, sehr skalierbar. Dies macht den Algorithmus zu einem brauchbaren Kandidaten für das Sortieren großer Datenmengen, wie sie beispielsweise in Computer-Clustern verarbeitet werden. Da der Speicher in solchen Systemen in der Regel keine limitierende Ressource darstellt, ist der Nachteil der Speicherkomplexität von Mergesort vernachlässigbar. Allerdings werden in solchen Systemen andere Faktoren wichtig, die bei der Modellierung auf einer PRAM nicht berücksichtigt werden. Hier sind unter anderem die folgenden Aspekte zu berücksichtigen: Die Speicherhierarchie, wenn die Daten nicht in den Cache der Prozessoren passen, oder der Kommunikationsaufwand beim Datenaustausch zwischen den Prozessoren, der zu einem Engpass werden könnte, wenn auf die Daten nicht mehr über den gemeinsamen Speicher zugegriffen werden kann.

Sanders et al. haben in ihrem Paper einen bulk synchronous parallel-Algorithmus für einen mehrstufigen Mehrwege-Mergesort vorgestellt, der   Prozessoren in   Gruppen der Größe   unterteilt. Alle Prozessoren sortieren zuerst lokal. Im Gegensatz zu einem einstufigen Mehrwege-Mergesort werden diese Sequenzen dann in   Teile aufgeteilt und den entsprechenden Prozessorgruppen zugeordnet. Diese Schritte werden innerhalb dieser Gruppen rekursiv wiederholt. So wird die Kommunikation reduziert und insbesondere Probleme mit vielen kleinen Nachrichten vermieden. Die hierarchische Struktur des zugrundeliegenden realen Netzwerks (z.B. Racks, Cluster,...) kann zur Definition der Prozessorgruppen verwendet werden.[6]

Weitere Varianten

Bearbeiten

Mergesort war einer der ersten Sortieralgorithmen, bei dem ein optimaler Speedup erreicht wurde, wobei Richard Cole einen cleveren Subsampling-Algorithmus verwendete, um die O(1)-Zusammenführung sicherzustellen.[7] Andere ausgeklügelte parallele Sortieralgorithmen können die gleichen oder bessere Zeitschranken mit einer niedrigeren Konstante erreichen. David Powers beschrieb beispielsweise 1991 einen parallelisierten Quicksort (und einen verwandten Radixsort), der durch implizite Partitionierung in   Zeit auf einer CRCW-Parallel Random Access Machine (PRAM) mit   Prozessoren arbeiten kann.[8] Powers zeigt ferner, dass eine Pipeline-Version von Batchers Bitonic Mergesort in   Zeit auf einem Butterfly-Sortiernetzwerk in der Praxis schneller ist als sein   Sortieralgorithmus auf einer PRAM, und er bietet eine detaillierte Diskussion der versteckten Overheads beim Vergleich, bei der Radix- und der Parallelsortierung.[9]

  1. a b Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford: Introduction to algorithms. Third edition Auflage. MIT Press, Cambridge, Mass. 2009, ISBN 978-0-262-27083-0 (worldcat.org [abgerufen am 6. März 2020]).
  2. Victor J. Duvanenko "Parallel Merge Sort" Dr. Dobb's Journal & blog[1] and GitHub repo C++ implementation [2]
  3. Peter Sanders, Johannes Singler. 2008. Lecture Parallel algorithms Last visited 05.02.2020. http://algo2.iti.kit.edu/sanders/courses/paralg08/singler.pdf
  4. Practical Massively Parallel Sorting | Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures. In: dl.acm.org. Abgerufen am 28. Februar 2020 (englisch, 10.1145/2755573.2755595).
  5. Peter Sanders. 2019. Lecture Parallel algorithms Last visited 05.02.2020. http://algo2.iti.kit.edu/sanders/courses/paralg19/vorlesung.pdf
  6. Practical Massively Parallel Sorting | Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures. In: dl.acm.org. Abgerufen am 28. Februar 2020 (englisch, 10.1145/2755573.2755595).
  7. Richard Cole: Parallel Merge Sort. In: SIAM Journal on Computing. Band 17, Nr. 4, August 1988, ISSN 0097-5397, S. 770–785, doi:10.1137/0217049 (siam.org [abgerufen am 6. März 2020]).
  8. Powers, David M. W. Parallelized Quicksort and Radixsort with Optimal Speedup, Proceedings of International Conference on Parallel Computing Technologies. Novosibirsk. 1991.
  9. David M. W. Powers, Parallel Unification: Practical Complexity, Australasian Computer Architecture Workshop, Flinders University, January 1995