www.wikidata.de-de.nina.az

Samplesort ist ein Sortieralgorithmus der 1970 von W D Frazer und A C McKellar in der wissenschaftlichen Publikation A S

Samplesort

Samplesort ist ein Sortieralgorithmus, der 1970 von W. D. Frazer und A. C. McKellar in der wissenschaftlichen Publikation Samplesort: A Sampling Approach to Minimal Storage Tree Sorting veröffentlicht wurde. Der Algorithmus arbeitet ähnlich wie Quicksort und verfolgt wie dieser das Teile-und-herrsche-Verfahren. Der Algorithmus teilt die Eingabesequenz in mehrere Teilsequenzen auf, die dann rekursiv sortiert werden.

Pseudocode Bearbeiten

Der folgende Pseudocode stellt die Arbeitsweise des Algorithmus grundlegend dar. Dabei enthält die zu sortierenden Daten, entspricht dem Oversamplingfaktor und der Anzahl der zu nutzenden Splitter. Die Anzahl der Splitter gibt an, in wie viele Teilsequenzen die Eingabedaten aufgeteilt werden (für entspricht der Algorithmus Quicksort), während sich durch einen großen Oversamplingfaktor die Größen der Buckets statistisch gesehen weniger unterscheiden. 

  // if average bucket size is below a threshold switch to e.g. quicksort  // select samples  // sort sample  // select splitters // classify elements

Die Wahl des richtigen Buckets in der Schleife kann für jedes Element mit binärer Suche in Zeit ausgeführt werden.

Der angegebene Pseudocode unterscheidet sich von der von Frazer und McKellar beschriebenen Ursprungsform. Im Pseudocode wird Samplesort rekursiv aufgerufen, um die erzeugten kleineren Teilmengen zu sortieren. Frazer und McKellar verwendeten dafür Quicksort, d. h. die Funktion Samplesort wird nur einmal aufgerufen.

Die Anzahl Vergleiche, die dieser Algorithmus durchführt, nähert sich für große Eingabesequenzen asymptotisch dem informationstheoretischen Optimum an und brauchte in den von Frazer und McKellar durchgeführten Experimenten mehr als 15 % weniger Vergleiche als Quicksort.

Oversampling Bearbeiten

Der Oversamplingfaktor gibt an, wie groß die Stichprobe zur Auswahl der Splitter größer ist, als die Anzahl der Splitter. Ziel ist es, die Verteilung der Eingabedaten möglichst gut anzunähern. Nach der Klassifikation enthält im Idealfall jeder Bucket genau Elemente, um die folgende Arbeit des Algorithmus gleichmäßig auf die Buckets aufzuteilen.

Nach der Wahl des Samples der Größe wird das Sample sortiert. Als Splitter, die als Bucketgrenzen verwendet werden, werden die Elemente in an den Stellen sowie und als linke und rechte Grenzen des linkesten und rechtesten Buckets verwendet.

Größe der Buckets Bearbeiten

Mit der Größe des Samples bzw. dem Oversamplingfaktor kann die erwartete Bucketgröße und insbesondere die Wahrscheinlichkeit dafür, dass ein Bucket eine gewisse Größe überschreitet, abgeschätzt werden. Für einen Oversamplingfaktor werden wir zeigen, dass mit einer Wahrscheinlichkeit von weniger als ein Bucket mehr als Elemente enthält.

Sei dafür die Eingabe bereits in sortierter Form. Damit ein Prozessor mehr als Elemente erhält, muss es eine Sequenz der Eingabe der Länge geben, aus der maximal Elemente für das Sample gewählt werden. Das wird wie folgt als Zufallsvariable dargestellt:

Daraus folgt:

Dabei bezeichnet die Wahrscheinlichkeit, dass weniger als Samples im Bucket liegen. Mithilfe der Chernoff-Ungleichung sieht man, dass

Samplesort auf Systemen mit verteiltem Speicher Bearbeiten

Arbeitsprinzip von parallelem Samplesort für Prozessoren und einem Oversamplingfaktor .

Samplesort wird oft in parallelen Systemen mit verteiltem Speicher verwendet, da es durch die variable Anzahl von Buckets im Gegensatz zum Beispiel zu Quicksort einfach an eine beliebige Anzahl Prozessoren angepasst werden kann. Die Eingabedaten liegen dabei verteilt auf Prozessoren vor, das heißt, jeder Prozessor hat Elemente gespeichert. Entsprechend werden ebenso viele Splitter ausgewählt, um für jeden Prozessor einen Bucket zu erzeugen.

Um die Splitter auszuwählen, ist es ausreichend, wenn jeder Prozessor aus seinen Eingabeelementen Elemente auswählt. Diese werden mit einem verteilten Sortieralgorithmus sortiert und an alle Prozessoren verteilt. Es entstehen Kosten von für das Sortieren der Elemente auf Prozessoren, sowie für das Verteilen der gewählten Splitter auf Prozessoren.

Mit den erhaltenen Splittern partitioniert jeder Prozessor die eigenen Eingabedaten in lokale Buckets. Die Zeit dafür beträgt mit binärer Suche . Anschließend verteilen die Prozessoren die Buckets an die jeweiligen Prozessoren mit Zeit , wobei der Größe des größten Buckets entspricht. Prozessor enthält entsprechend von allen Prozessoren die lokalen Buckets und sortiert diese lokal. Der Zeitbedarf für die lokale Sortierung von allen Prozessoren beträgt .

Wählt man wie im vorherigen Abschnitt beschrieben , so erhält man eine Gesamtlaufzeit von

Effiziente Implementierung von sequentiellem Samplesort Bearbeiten

Arbeitsprinzip von Super Scalar Sample Sort. (Animation) In jedem Schritt werden Zahlen, die verglichen werden, blau eingefärbt und Zahlen, auf die anderweitig lesend oder schreibend zugegriffen wird, werden rot eingefärbt.

Wie oben beschrieben klassifiziert der Algorithmus die Elemente anhand der gewählten Splitter und partitioniert diese entsprechend. Eine effiziente Implementierung wird im Paper Super Scalar Sample Sort beschrieben. Dort werden zwei Arrays der Größe genutzt: ein Array für die Eingabedaten, sowie ein temporäres Array. Entsprechend arbeitet Samplesort in diesem Fall nicht in-place. In jedem Rekurssionsschritt werden die Daten von einem zum anderen Array kopiert und währenddessen partitioniert. Falls die Daten nach dem letzten Rekursionsschritt im temporären Array vorliegen, so werden diese in das originale Array zurückkopiert. Die wesentlichen Schritte sind die Klassifikation der Elemente anhand der Splitter und die anschließende Partitionierung. Beides wird im Folgenden genauer erklärt.

Klassifikation der Elemente Bearbeiten

In einem vergleichsbasierten Sortieralgorithmus ist der performancekritische Teil die Klassifikation der Elemente, d. h. die Zuordnung von Elementen zu Buckets. Diese Zuordnung benötigt Schritte pro Element. Super Scalar Sample Sort nutzt einen balancierten Suchbaum, der implizit in einem Array gespeichert ist. Das heißt, die Wurzel befindet sich an Stelle 0, und der linke Nachfolger eines Elementes befindet sich in , der rechte Nachfolger in . Bei einem gegebenen Suchbaum und einem Element berechnet der Algorithmus den Index des entsprechenden Buckets wie folgt (der Ausdruck sei 1 falls und 0 andernfalls, sei eine Zweierpotenz):

Da die Anzahl der Buckets bei der Übersetzungszeit bekannt ist, kann die Schleife vom Compiler ausgerollt werden. Falls die Prozessorarchitektur es unterstützt, kann in der Schleife ganz auf bedingte Sprünge verzichtet werden und es treten keine fehlerhaften Sprungvorhersagen auf.

Partitionierung Bearbeiten

Zum effizienten Partitionieren muss der Algorithmus die Größen der Buckets vor dem Kopieren der Elemente kennen. In einer naiven Implementierung könnten alle Elemente klassifiziert werden, um die Bucketgrößen zu bestimmen. Anschließend könnten die Elemente an die richtige Stelle kopiert werden. So müsste der Bucket für jedes Element zweimal bestimmt werden (einmal für das Zählen der Elemente der Buckets und einmal zum Kopieren). Super Scalar Sample Sort vermeidet diese doppelte Klassifikation, indem das Ergebnis der Klassifikation in einem zusätzlichen Array (dem „Orakel“) zwischengespeichert werden. Dieses ordnet jedem Element den Bucketindex zu. Zuerst bestimmt Super Scalar Sample Sort die richtigen Werte von , indem jedes Element klassifiziert wird. Danach werden die Größen der Buckets bestimmt und jedes Element anhand von an die richtige Stelle kopiert. Der Speicherbedarf von Array beträgt bits, was im Vergleich zu den Eingabedaten nur wenig Speicher bedeutet.

Paralleler in-place-Samplesort für Systeme mit gemeinsamem Speicher Bearbeiten

Die oben gezeigte Samplesort-Implementierung arbeitet nicht in-place, da ein zweites Array der Größe benötigt wird. Effiziente Implementierungen von z. B. Quicksort arbeiten in-place und benötigen daher weniger Speicher. Samplesort kann allerdings auch in-place für parallele Systeme mit gemeinsamem Speicher implementiert werden. Im Folgenden wird eine solche Implementierung beschrieben. Zu beachten ist, dass der zusätzliche Speicherplatz des Algorithmus immer noch von abhängt, im Gegensatz zum oben erklärten Super Scalar Sample Sort aber nur zusätzlichen Speicherplatz benötigt. Eine modifizierte Variante des Algorithmus, der nur noch Speicherplatz unabhängig von benötigt, ist ebenfalls in beschrieben.

Der in-place Algorithmus kann in vier Phasen aufgeteilt werden:

  1. Sampling: Auswahl der Splitter.
  2. Lokale Klassifikation: Gruppieren der Eingabe in Blöcke, so dass alle Elemente eines Blockes zu einem Bucket gehören (allerdings muss nicht jeder Bucket zusammenhängend im Speicher liegen).
  3. Blockpermutation: Vertauschen der Blöcke, so dass diese global in der richtigen Reihenfolge liegen.
  4. Aufräumen: Kopieren der übrigen Elemente an die Kanten der Buckets.

Da durch diesen Algorithmus jedes Element zweimal gelesen und geschrieben werden muss (einmal bei der Klassifikation und einmal während der Blockpermutation) ergibt sich ein höherer Schreib- und Leseaufwand. Trotzdem ist der Algorithmus bis zu dreimal schneller als aktuelle in-place Wettbewerber und bis zu 1,5 mal schneller als andere aktuelle sequentielle Wettbewerber, einschließlich des oben beschrieben Super Scalar Sample Sort. Da das Sampling und die Auswahl der Splitter bereits oben (Pseudocode) beschrieben ist, folgen an dieser Stelle nur noch die detaillierten Erklärungen der drei anderen Phasen.

Lokale Klassifikation Bearbeiten

Das Eingabearray wird zuerst in (Anzahl der Prozessoren/Threads) Bereiche gleicher Größe aufgeteilt. Jeder Prozessor enthält einen solchen Bereich und teilt diesen weiter auf in Blöcke, die jeweils Elemente enthalten. Zusätzlich allokiert jeder Prozessor (Anzahl Buckets) Puffer, die ebenfalls Elemente speichern können. Jeder Prozessor verarbeitet anschließend seinen zugewiesenen Bereich und kopiert die Elemente in die entsprechenden allokierten Puffer. Falls ein Puffer voll ist, wird dessen Inhalt in den vom Prozessor verarbeiteten Bereich kopiert. Die dortigen Elemente, die dadurch überschrieben werden, sind bereits verarbeitet, da ansonsten kein Puffer voll sein könnte. Zur Auswahl der richtigen Buckets/Puffer siehe Klassifikation der Elemente. Nach dieser Phase enthält jeder Bereich mehrere Blöcke mit Elementen jeweils eines Buckets und darauffolgend leere Blöcke. Die übrigen Elemente sind noch in den Pufferblöcken. Zusätzlich speichert jeder Prozessor die Größe jedes Buckets.

Blockpermutation Bearbeiten

In dieser Phase werden die Blöcke im Eingabearray in die richtige Reihenfolge gebracht. Mithilfe einer Präfixsumme über die Größe der Buckets werden deren Grenzen bestimmt. Da in dieser Phase nur ganze Blöcke verschoben werden, werden die Grenzen auf ganze Blöcke aufgerundet. Die fehlenden Elemente befinden sich noch in den Pufferblöcken. Da die Größe des Eingabearrays nicht zwangsläufig durch die Blockgröße teilbar ist, müssen einige Elemente des letzten (nicht vollständigen) Blockes in einen Überlaufpuffer verschoben werden.

Bevor mit der Blockpermutation begonnen wird, müssen eventuell einige leere Blöcke an das Ende ihres Buckets verschoben werden. Anschließend wird für jeden Bucket ein Schreibpointer angelegt, der auf den Beginn der Buckets zeigt und ein Lesepointer , der auf den letzten nichtleeren Block im Bucket zeigt.

Um gegenseitige Blockierungen der Prozessoren zu vermeiden, verarbeitet jeder Prozessor anfangs einen eigenen (primären) Bucket . Außerdem erhält jeder Prozessor zwei Tauschpuffer, die jeweils genau einen Block speichern können. Falls beide Tauschpuffer leer sind, wird der Block an Stelle von in einen der Tauschpuffer platziert. Durch Klassifikation des ersten Elements im Puffer wird der Zielbucket dieses Blocks bestimmt und an Stelle kopiert. Um zu verhindern, dass ein dortiger Block überschrieben wird, muss dieser vorher in einen freien Tauschpuffer kopiert werden. Mit diesem Block im Tauschpuffer wird dann analog verfahren. Die Pointer und werden entsprechend angepasst.

Sind alle Blöcke des primären Buckets an der richtigen Stelle, werden die Blöcke des nächsten Buckets weiterverarbeitet, bis alle Blöcke ihren Zielbucket erreicht haben. Danach endet diese Phase.

Aufräumen Bearbeiten

Da nur ganze Blöcke in der Blockpermutationsphase verschoben wurden, können einige Elemente noch an Stelle außerhalb ihres Buckets liegen. Da es für alle Elemente noch genug Platz im ursprünglichen Array gibt, können die verbleibenden Elemente aus den Puffern an die freien Plätze kopiert werden. Zuletzt wird der Inhalt des Überlaufpuffers kopiert.

Literatur Bearbeiten

  • W. D. Frazer, A. C. McKellar: Samplesort: A Sampling Approach to Minimal Storage Tree Sorting. In: Journal of the ACM. Band 17, Nr. 3, Juli 1970, ISSN 0004-5411, S. 496–507.
  • Peter Sanders et al.: Vorlesung Parallele Algorithmen. Karlsruhe 2009, S. 75–80 (kit.edu [PDF; 2,1 MB]).

Erweiterungen für parallele Berechnungen:

Einzelnachweise Bearbeiten

  1. ↑ Peter Sanders, Sebastian Winkel: Super Scalar Sample Sort. In: Algorithms – ESA 2004 (= Lecture Notes in Computer Science). Springer, Berlin, Heidelberg 2004, ISBN 3-540-23025-4, S. 784–796, doi:10.1007/978-3-540-30140-0_69.
  2. W. D. Frazer, A. C. McKellar: Samplesort: A Sampling Approach to Minimal Storage Tree Sorting. In: Journal of the ACM (JACM). Band 17, Nr. 3, 1. Juli 1970, ISSN 0004-5411, S. 496–507, doi:10.1145/321592.321600 (acm.org [abgerufen am 22. März 2018]).
  3. Guy E. Blelloch, Charles E. Leiserson, Bruce M. Maggs, C. Greg Plaxton, Stephen J. Smith: A comparison of sorting algorithms for the connection machine CM-2. ACM, 1991, ISBN 0-89791-438-4, S. 3–16, doi:10.1145/113379.113380 (acm.org [abgerufen am 23. März 2018]).
  4. Alexandros V. Gerbessiotis, Leslie G. Valiant: Direct Bulk-Synchronous Parallel Algorithms. In: JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING. Band 22, 1992, S. 22––251 (psu.edu [abgerufen am 1. April 2018]).
  5. Jonathan M. D. Hill, Bill McColl, Dan C. Stefanescu, Mark W. Goudreau, Kevin Lang: BSPlib: The BSP Programming Library. 1998 (psu.edu [abgerufen am 1. April 2018]).
  6. William L. Hightower, Jan F. Prins, John H. Reif: Implementations of randomized sorting on large parallel machines. ACM, 1992, ISBN 0-89791-483-X, S. 158–167, doi:10.1145/140901.140918 (acm.org [abgerufen am 1. April 2018]).
  7. ↑ Michael Axtmann, Sascha Witt, Daniel Ferizovic, Peter Sanders: In-Place Parallel Super Scalar Samplesort (IPSSSSo). In: 25th Annual European Symposium on Algorithms (ESA 2017) (= Leibniz International Proceedings in Informatics (LIPIcs)). Band 87. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl 2017, ISBN 978-3-95977-049-1, S. 9:1–9:14, doi:10.4230/LIPIcs.ESA.2017.9 (dagstuhl.de [abgerufen am 30. März 2018]).
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Samplesort ist ein Sortieralgorithmus der 1970 von W D Frazer und A C McKellar in der wissenschaftlichen Publikation Samplesort A Sampling Approach to Minimal Storage Tree Sorting veroffentlicht wurde Der Algorithmus arbeitet ahnlich wie Quicksort und verfolgt wie dieser das Teile und herrsche Verfahren Der Algorithmus teilt die Eingabesequenz in mehrere Teilsequenzen auf die dann rekursiv sortiert werden Inhaltsverzeichnis 1 Pseudocode 2 Oversampling 2 1 Grosse der Buckets 3 Samplesort auf Systemen mit verteiltem Speicher 4 Effiziente Implementierung von sequentiellem Samplesort 4 1 Klassifikation der Elemente 4 2 Partitionierung 5 Paralleler in place Samplesort fur Systeme mit gemeinsamem Speicher 5 1 Lokale Klassifikation 5 2 Blockpermutation 5 3 Aufraumen 6 Literatur 7 EinzelnachweisePseudocode BearbeitenDer folgende Pseudocode stellt die Arbeitsweise des Algorithmus grundlegend dar 1 Dabei enthalt A displaystyle A nbsp die zu sortierenden Daten k displaystyle k nbsp entspricht dem Oversamplingfaktor und p displaystyle p nbsp der Anzahl der zu nutzenden Splitter Die Anzahl der Splitter gibt an in wie viele Teilsequenzen die Eingabedaten aufgeteilt werden fur p 2 displaystyle p 2 nbsp entspricht der Algorithmus Quicksort wahrend sich durch einen grossen Oversamplingfaktor die Grossen der Buckets statistisch gesehen weniger unterscheiden sampleSort A 1 n k p displaystyle text sampleSort A 1 n k p nbsp if n k lt threshold then smallSort A displaystyle text if n k lt text threshold then smallSort A nbsp if average bucket size is below a threshold switch to e g quicksort select S S 1 S p k 1 randomly from A displaystyle text select S S 1 dots S p k 1 text randomly from A nbsp select samples sort S displaystyle text sort S nbsp sort sample s 0 s 1 s p 1 s p S k S 2 k S p 1 k displaystyle s 0 s 1 dots s p 1 s p leftarrow infty S k S 2k dots S p 1 k infty nbsp select splitters classify elements for each a A displaystyle text for each a in A nbsp find j such that s j 1 lt a s j displaystyle text find j text such that s j 1 lt a leq s j nbsp place a in bucket b j displaystyle text place a text in bucket b j nbsp return concatenate sampleSort b 1 sampleSort b k displaystyle text return concatenate text sampleSort b 1 dots text sampleSort b k nbsp Die Wahl des richtigen Buckets in der Schleife kann fur jedes Element mit binarer Suche in Zeit O log p displaystyle mathcal O log p nbsp ausgefuhrt werden Der angegebene Pseudocode unterscheidet sich von der von Frazer und McKellar beschriebenen Ursprungsform 2 Im Pseudocode wird Samplesort rekursiv aufgerufen um die erzeugten kleineren Teilmengen zu sortieren Frazer und McKellar verwendeten dafur Quicksort d h die Funktion Samplesort wird nur einmal aufgerufen Die Anzahl Vergleiche die dieser Algorithmus durchfuhrt nahert sich fur grosse Eingabesequenzen asymptotisch dem informationstheoretischen Optimum log 2 n displaystyle log 2 n nbsp an und brauchte in den von Frazer und McKellar durchgefuhrten Experimenten mehr als 15 weniger Vergleiche als Quicksort Oversampling BearbeitenDer Oversamplingfaktor gibt an wie gross die Stichprobe zur Auswahl der Splitter grosser ist als die Anzahl der Splitter Ziel ist es die Verteilung der Eingabedaten moglichst gut anzunahern Nach der Klassifikation enthalt im Idealfall jeder Bucket genau n p displaystyle n p nbsp Elemente um die folgende Arbeit des Algorithmus gleichmassig auf die Buckets aufzuteilen Nach der Wahl des Samples S displaystyle S nbsp der Grosse p k 1 displaystyle p cdot k 1 nbsp wird das Sample sortiert Als Splitter die als Bucketgrenzen verwendet werden werden die Elemente in S displaystyle S nbsp an den Stellen k 2 k 3 k p 1 k displaystyle k 2k 3k dots p 1 k nbsp sowie displaystyle infty nbsp und displaystyle infty nbsp als linke und rechte Grenzen des linkesten und rechtesten Buckets verwendet Grosse der Buckets Bearbeiten Mit der Grosse des Samples bzw dem Oversamplingfaktor kann die erwartete Bucketgrosse und insbesondere die Wahrscheinlichkeit dafur dass ein Bucket eine gewisse Grosse uberschreitet abgeschatzt werden Fur einen Oversamplingfaktor k 8 log n ϵ 2 displaystyle k in Theta frac log n epsilon 2 nbsp werden wir zeigen dass mit einer Wahrscheinlichkeit von weniger als 1 n displaystyle 1 n nbsp ein Bucket mehr als 1 ϵ n p displaystyle 1 epsilon n p nbsp Elemente enthalt Sei dafur e 1 e n displaystyle e 1 dots e n nbsp die Eingabe bereits in sortierter Form Damit ein Prozessor mehr als 1 ϵ n p displaystyle 1 epsilon n p nbsp Elemente erhalt muss es eine Sequenz der Eingabe der Lange 1 ϵ n p displaystyle 1 epsilon n p nbsp geben aus der maximal k displaystyle k nbsp Elemente fur das Sample gewahlt werden Das wird wie folgt als Zufallsvariable dargestellt X i 1 falls s i e j e j 1 ϵ n p 0 sonst displaystyle X i begin cases 1 amp text falls s i in e j dots e j 1 epsilon n p 0 amp text sonst end cases nbsp X i 0 k p 1 X i displaystyle X sum i 0 k cdot p 1 X i nbsp Daraus folgt E X i P X i 1 1 ϵ p displaystyle mathbb E X i mathbb P X i 1 frac 1 epsilon p nbsp P X lt k P X lt 1 ϵ 2 k P X lt 1 ϵ E X displaystyle mathbb P X lt k approx mathbb P X lt 1 epsilon 2 k mathbb P X lt 1 epsilon mathbb E X nbsp Dabei bezeichnet P X lt k displaystyle mathbb P X lt k nbsp die Wahrscheinlichkeit dass weniger als k displaystyle k nbsp Samples im Bucket j displaystyle j nbsp liegen Mithilfe der Chernoff Ungleichung sieht man dass n P X lt k n exp ϵ 2 k 2 n 1 n 2 displaystyle n mathbb P X lt k leq n exp frac epsilon 2 k 2 leq n frac 1 n 2 nbsp fur k 4 ϵ 2 ln n displaystyle k geq frac 4 epsilon 2 ln n nbsp Samplesort auf Systemen mit verteiltem Speicher Bearbeiten nbsp Arbeitsprinzip von parallelem Samplesort fur p 3 displaystyle p 3 nbsp Prozessoren und einem Oversamplingfaktor k 3 displaystyle k 3 nbsp Samplesort wird oft in parallelen Systemen mit verteiltem Speicher verwendet 3 4 5 6 da es durch die variable Anzahl von Buckets im Gegensatz zum Beispiel zu Quicksort einfach an eine beliebige Anzahl Prozessoren angepasst werden kann Die Eingabedaten liegen dabei verteilt auf p displaystyle p nbsp Prozessoren vor das heisst jeder Prozessor hat n p displaystyle n p nbsp Elemente gespeichert Entsprechend werden ebenso viele Splitter ausgewahlt um fur jeden Prozessor einen Bucket zu erzeugen Um die Splitter auszuwahlen ist es ausreichend wenn jeder Prozessor aus seinen Eingabeelementen k displaystyle k nbsp Elemente auswahlt Diese werden mit einem verteilten Sortieralgorithmus sortiert und an alle Prozessoren verteilt Es entstehen Kosten von T sort k p p displaystyle T text sort kp p nbsp fur das Sortieren der k p displaystyle kp nbsp Elemente auf p displaystyle p nbsp Prozessoren sowie T allgather p p displaystyle T text allgather p p nbsp fur das Verteilen der p displaystyle p nbsp gewahlten Splitter auf p displaystyle p nbsp Prozessoren Mit den erhaltenen Splittern partitioniert jeder Prozessor die eigenen Eingabedaten in lokale Buckets Die Zeit dafur betragt mit binarer Suche O n p log p displaystyle mathcal O n p log p nbsp Anschliessend verteilen die Prozessoren die Buckets an die jeweiligen Prozessoren mit Zeit T all to all N p displaystyle T text all to all N p nbsp wobei N displaystyle N nbsp der Grosse des grossten Buckets entspricht Prozessor i displaystyle i nbsp enthalt entsprechend von allen Prozessoren die lokalen Buckets b i displaystyle b i nbsp und sortiert diese lokal Der Zeitbedarf fur die lokale Sortierung von allen Prozessoren betragt T localsort N displaystyle T text localsort N nbsp Wahlt man wie im vorherigen Abschnitt beschrieben k 8 log n ϵ 2 displaystyle k in Theta frac log n epsilon 2 nbsp so erhalt man eine Gesamtlaufzeit von T n p T sort O p log n ϵ 2 p T allgather p p O n p log p T all to all 1 ϵ n p p T localsort 1 ϵ n p displaystyle T n p T text sort mathcal O frac p log n epsilon 2 p T text allgather p p mathcal O n p log p T text all to all 1 epsilon n p p T text localsort 1 epsilon n p nbsp Effiziente Implementierung von sequentiellem Samplesort Bearbeiten nbsp Arbeitsprinzip von Super Scalar Sample Sort Animation In jedem Schritt werden Zahlen die verglichen werden blau eingefarbt und Zahlen auf die anderweitig lesend oder schreibend zugegriffen wird werden rot eingefarbt Wie oben beschrieben klassifiziert der Algorithmus die Elemente anhand der gewahlten Splitter und partitioniert diese entsprechend Eine effiziente Implementierung wird im Paper Super Scalar Sample Sort 1 beschrieben Dort werden zwei Arrays der Grosse n displaystyle n nbsp genutzt ein Array fur die Eingabedaten sowie ein temporares Array Entsprechend arbeitet Samplesort in diesem Fall nicht in place In jedem Rekurssionsschritt werden die Daten von einem zum anderen Array kopiert und wahrenddessen partitioniert Falls die Daten nach dem letzten Rekursionsschritt im temporaren Array vorliegen so werden diese in das originale Array zuruckkopiert Die wesentlichen Schritte sind die Klassifikation der Elemente anhand der Splitter und die anschliessende Partitionierung Beides wird im Folgenden genauer erklart Klassifikation der Elemente Bearbeiten In einem vergleichsbasierten Sortieralgorithmus ist der performancekritische Teil die Klassifikation der Elemente d h die Zuordnung von Elementen zu Buckets Diese Zuordnung benotigt O log p displaystyle mathcal O log p nbsp Schritte pro Element Super Scalar Sample Sort nutzt einen balancierten Suchbaum der implizit in einem Array t displaystyle t nbsp gespeichert ist Das heisst die Wurzel befindet sich an Stelle 0 und der linke Nachfolger eines Elementes t i displaystyle t i nbsp befindet sich in t 2 i displaystyle t 2i nbsp der rechte Nachfolger in t 2 i 1 displaystyle t 2i 1 nbsp Bei einem gegebenen Suchbaum t displaystyle t nbsp und einem Element a displaystyle a nbsp berechnet der Algorithmus den Index des entsprechenden Buckets j displaystyle j nbsp wie folgt der Ausdruck a gt t j displaystyle a gt t j nbsp sei 1 falls a gt t j displaystyle a gt t j nbsp und 0 andernfalls p displaystyle p nbsp sei eine Zweierpotenz j 1 displaystyle j leftarrow 1 nbsp repeat log 2 p times displaystyle text repeat log 2 p text times nbsp j 2 j a gt t j displaystyle j leftarrow 2j a gt t j nbsp j j p 1 displaystyle j leftarrow j p 1 nbsp Da die Anzahl der Buckets p displaystyle p nbsp bei der Ubersetzungszeit bekannt ist kann die Schleife vom Compiler ausgerollt werden Falls die Prozessorarchitektur es unterstutzt kann in der Schleife ganz auf bedingte Sprunge verzichtet werden und es treten keine fehlerhaften Sprungvorhersagen auf Partitionierung Bearbeiten Zum effizienten Partitionieren muss der Algorithmus die Grossen der Buckets vor dem Kopieren der Elemente kennen In einer naiven Implementierung konnten alle Elemente klassifiziert werden um die Bucketgrossen zu bestimmen Anschliessend konnten die Elemente an die richtige Stelle kopiert werden So musste der Bucket fur jedes Element zweimal bestimmt werden einmal fur das Zahlen der Elemente der Buckets und einmal zum Kopieren Super Scalar Sample Sort vermeidet diese doppelte Klassifikation indem das Ergebnis der Klassifikation in einem zusatzlichen Array o displaystyle o nbsp dem Orakel zwischengespeichert werden Dieses ordnet jedem Element a i displaystyle a i nbsp den Bucketindex o i displaystyle o i nbsp zu Zuerst bestimmt Super Scalar Sample Sort die richtigen Werte von o displaystyle o nbsp indem jedes Element klassifiziert wird Danach werden die Grossen der Buckets bestimmt und jedes Element anhand von o displaystyle o nbsp an die richtige Stelle kopiert Der Speicherbedarf von Array o displaystyle o nbsp betragt n log p displaystyle n log p nbsp bits was im Vergleich zu den Eingabedaten nur wenig Speicher bedeutet Paralleler in place Samplesort fur Systeme mit gemeinsamem Speicher BearbeitenDie oben gezeigte Samplesort Implementierung arbeitet nicht in place da ein zweites Array der Grosse n displaystyle n nbsp benotigt wird Effiziente Implementierungen von z B Quicksort arbeiten in place und benotigen daher weniger Speicher Samplesort kann allerdings auch in place fur parallele Systeme mit gemeinsamem Speicher implementiert werden 7 Im Folgenden wird eine solche Implementierung beschrieben Zu beachten ist dass der zusatzliche Speicherplatz des Algorithmus immer noch von n displaystyle n nbsp abhangt im Gegensatz zum oben erklarten Super Scalar Sample Sort aber nur o n displaystyle mathcal o n nbsp zusatzlichen Speicherplatz benotigt Eine modifizierte Variante des Algorithmus der nur noch Speicherplatz unabhangig von n displaystyle n nbsp benotigt ist ebenfalls in 7 beschrieben Der in place Algorithmus kann in vier Phasen aufgeteilt werden Sampling Auswahl der Splitter Lokale Klassifikation Gruppieren der Eingabe in Blocke so dass alle Elemente eines Blockes zu einem Bucket gehoren allerdings muss nicht jeder Bucket zusammenhangend im Speicher liegen Blockpermutation Vertauschen der Blocke so dass diese global in der richtigen Reihenfolge liegen Aufraumen Kopieren der ubrigen Elemente an die Kanten der Buckets Da durch diesen Algorithmus jedes Element zweimal gelesen und geschrieben werden muss einmal bei der Klassifikation und einmal wahrend der Blockpermutation ergibt sich ein hoherer Schreib und Leseaufwand Trotzdem ist der Algorithmus bis zu dreimal schneller als aktuelle in place Wettbewerber und bis zu 1 5 mal schneller als andere aktuelle sequentielle Wettbewerber einschliesslich des oben beschrieben Super Scalar Sample Sort Da das Sampling und die Auswahl der Splitter bereits oben Pseudocode beschrieben ist folgen an dieser Stelle nur noch die detaillierten Erklarungen der drei anderen Phasen Lokale Klassifikation Bearbeiten Das Eingabearray wird zuerst in t displaystyle t nbsp Anzahl der Prozessoren Threads Bereiche gleicher Grosse aufgeteilt Jeder Prozessor enthalt einen solchen Bereich und teilt diesen weiter auf in Blocke die jeweils b displaystyle b nbsp Elemente enthalten Zusatzlich allokiert jeder Prozessor p displaystyle p nbsp Anzahl Buckets Puffer die ebenfalls b displaystyle b nbsp Elemente speichern konnen Jeder Prozessor verarbeitet anschliessend seinen zugewiesenen Bereich und kopiert die Elemente in die entsprechenden allokierten Puffer Falls ein Puffer voll ist wird dessen Inhalt in den vom Prozessor verarbeiteten Bereich kopiert Die dortigen b displaystyle b nbsp Elemente die dadurch uberschrieben werden sind bereits verarbeitet da ansonsten kein Puffer voll sein konnte Zur Auswahl der richtigen Buckets Puffer siehe Klassifikation der Elemente Nach dieser Phase enthalt jeder Bereich mehrere Blocke mit Elementen jeweils eines Buckets und darauffolgend leere Blocke Die ubrigen Elemente sind noch in den Pufferblocken Zusatzlich speichert jeder Prozessor die Grosse jedes Buckets Blockpermutation Bearbeiten In dieser Phase werden die Blocke im Eingabearray in die richtige Reihenfolge gebracht Mithilfe einer Prafixsumme uber die Grosse der Buckets werden deren Grenzen bestimmt Da in dieser Phase nur ganze Blocke verschoben werden werden die Grenzen auf ganze Blocke aufgerundet Die fehlenden Elemente befinden sich noch in den Pufferblocken Da die Grosse des Eingabearrays nicht zwangslaufig durch die Blockgrosse teilbar ist mussen einige Elemente des letzten nicht vollstandigen Blockes in einen Uberlaufpuffer verschoben werden Bevor mit der Blockpermutation begonnen wird mussen eventuell einige leere Blocke an das Ende ihres Buckets verschoben werden Anschliessend wird fur jeden Bucket b i displaystyle b i nbsp ein Schreibpointer w i displaystyle w i nbsp angelegt der auf den Beginn der Buckets zeigt und ein Lesepointer r i displaystyle r i nbsp der auf den letzten nichtleeren Block im Bucket b i displaystyle b i nbsp zeigt Um gegenseitige Blockierungen der Prozessoren zu vermeiden verarbeitet jeder Prozessor anfangs einen eigenen primaren Bucket b prim displaystyle b text prim nbsp Ausserdem erhalt jeder Prozessor zwei Tauschpuffer die jeweils genau einen Block speichern konnen Falls beide Tauschpuffer leer sind wird der Block an Stelle von r prim displaystyle r text prim nbsp in einen der Tauschpuffer platziert Durch Klassifikation des ersten Elements im Puffer wird der Zielbucket b dest displaystyle b text dest nbsp dieses Blocks bestimmt und an Stelle w dest displaystyle w text dest nbsp kopiert Um zu verhindern dass ein dortiger Block uberschrieben wird muss dieser vorher in einen freien Tauschpuffer kopiert werden Mit diesem Block im Tauschpuffer wird dann analog verfahren Die Pointer r prim displaystyle r text prim nbsp und w dest displaystyle w text dest nbsp werden entsprechend angepasst Sind alle Blocke des primaren Buckets an der richtigen Stelle werden die Blocke des nachsten Buckets weiterverarbeitet bis alle Blocke ihren Zielbucket erreicht haben Danach endet diese Phase Aufraumen Bearbeiten Da nur ganze Blocke in der Blockpermutationsphase verschoben wurden konnen einige Elemente noch an Stelle ausserhalb ihres Buckets liegen Da es fur alle Elemente noch genug Platz im ursprunglichen Array gibt konnen die verbleibenden Elemente aus den Puffern an die freien Platze kopiert werden Zuletzt wird der Inhalt des Uberlaufpuffers kopiert Literatur BearbeitenW D Frazer A C McKellar Samplesort A Sampling Approach to Minimal Storage Tree Sorting In Journal of the ACM Band 17 Nr 3 Juli 1970 ISSN 0004 5411 S 496 507 Peter Sanders et al Vorlesung Parallele Algorithmen Karlsruhe 2009 S 75 80 kit edu PDF 2 1 MB Erweiterungen fur parallele Berechnungen ohio state edu Memento vom 8 Juni 2011 im Internet Archive PDF citeseer ist psu edu citeseerx ist psu edu Verwendung auf der GPU PDF 869 kB Einzelnachweise Bearbeiten a b Peter Sanders Sebastian Winkel Super Scalar Sample Sort In Algorithms ESA 2004 Lecture Notes in Computer Science Springer Berlin Heidelberg 2004 ISBN 3 540 23025 4 S 784 796 doi 10 1007 978 3 540 30140 0 69 W D Frazer A C McKellar Samplesort A Sampling Approach to Minimal Storage Tree Sorting In Journal of the ACM JACM Band 17 Nr 3 1 Juli 1970 ISSN 0004 5411 S 496 507 doi 10 1145 321592 321600 acm org abgerufen am 22 Marz 2018 Guy E Blelloch Charles E Leiserson Bruce M Maggs C Greg Plaxton Stephen J Smith A comparison of sorting algorithms for the connection machine CM 2 ACM 1991 ISBN 0 89791 438 4 S 3 16 doi 10 1145 113379 113380 acm org abgerufen am 23 Marz 2018 Alexandros V Gerbessiotis Leslie G Valiant Direct Bulk Synchronous Parallel Algorithms In JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING Band 22 1992 S 22 251 psu edu abgerufen am 1 April 2018 Jonathan M D Hill Bill McColl Dan C Stefanescu Mark W Goudreau Kevin Lang BSPlib The BSP Programming Library 1998 psu edu abgerufen am 1 April 2018 William L Hightower Jan F Prins John H Reif Implementations of randomized sorting on large parallel machines ACM 1992 ISBN 0 89791 483 X S 158 167 doi 10 1145 140901 140918 acm org abgerufen am 1 April 2018 a b Michael Axtmann Sascha Witt Daniel Ferizovic Peter Sanders In Place Parallel Super Scalar Samplesort IPSSSSo In 25th Annual European Symposium on Algorithms ESA 2017 Leibniz International Proceedings in Informatics LIPIcs Band 87 Schloss Dagstuhl Leibniz Zentrum fuer Informatik Dagstuhl 2017 ISBN 978 3 95977 049 1 S 9 1 9 14 doi 10 4230 LIPIcs ESA 2017 9 dagstuhl de abgerufen am 30 Marz 2018 Abgerufen von https de wikipedia org w index php title Samplesort amp oldid 239493880