Parallel Quicksort - Versionsgeschichte

Phantsom: /* growthexperiments-addlink-summary-summary:2|1|0 */

2024-09-01T19:59:02Z

Linkvorschlag-Funktion: 2 Links hinzugefügt.

← Nächstältere Version		Version vom 1. September 2024, 21:59 Uhr
Zeile 17:		Zeile 17:
	Die Reihenfolge bei der Allokation von Prozessoren an Untermengen wird dynamisch angepasst. Prozessor 1 partitioniert die Menge der Elemente mit Index <math>(1,n)</math>. Die erste entstandene Untermenge, <math>(1, k_{1} - 1)</math>, verarbeitet wieder Prozessor 1 und die zweite, <math>(k_{1} +1, n)</math>, Prozessor 2. Die Menge der Elemente <math>(k_1 + 1, n)</math> ist o. B. d. A. die kleinere von beiden. Daher ist es plausibler, dass diese von Prozessor 2 schneller partitioniert wird. Prozessor 2 fordert also früher als Prozessor 1 für seine Untermengen einen neuen Prozessor an. Infolgedessen verarbeitet Prozessor 2 die eine erhaltene Untermenge, während Prozessor 3 die andere. Wenn Prozessor 1 einen neuen Prozessor anfordert, bekommt er Prozessor 4, weil dieser zurzeit frei ist.		Die Reihenfolge bei der Allokation von Prozessoren an Untermengen wird dynamisch angepasst. Prozessor 1 partitioniert die Menge der Elemente mit Index <math>(1,n)</math>. Die erste entstandene Untermenge, <math>(1, k_{1} - 1)</math>, verarbeitet wieder Prozessor 1 und die zweite, <math>(k_{1} +1, n)</math>, Prozessor 2. Die Menge der Elemente <math>(k_1 + 1, n)</math> ist o. B. d. A. die kleinere von beiden. Daher ist es plausibler, dass diese von Prozessor 2 schneller partitioniert wird. Prozessor 2 fordert also früher als Prozessor 1 für seine Untermengen einen neuen Prozessor an. Infolgedessen verarbeitet Prozessor 2 die eine erhaltene Untermenge, während Prozessor 3 die andere. Wenn Prozessor 1 einen neuen Prozessor anfordert, bekommt er Prozessor 4, weil dieser zurzeit frei ist.

	Das folgende Pseudocode skizziert eine Implementierung von Parallel Quicksort. <math>M</math> bezeichnet die maximale Größe des Array, welcher effizienter mit einem sequentiellen Sortieralgorithmus, z. B. [[Insertionsort]], zu sortieren ist.		Das folgende [[Pseudocode]] skizziert eine Implementierung von Parallel Quicksort. <math>M</math> bezeichnet die maximale Größe des Array, welcher effizienter mit einem sequentiellen Sortieralgorithmus, z. B. [[Insertionsort]], zu sortieren ist.
	<syntaxhighlight lang="c">		<syntaxhighlight lang="c">
	PROCEDURE QUICKSORT (L,U);		PROCEDURE QUICKSORT (L,U);
Zeile 37:		Zeile 37:
	Dieser Ansatz erreicht eine niedrigere Beschleunigung gegenüber dem sequentiellen Quicksort<ref name=":0">{{Literatur \|Autor=Quinn, Michael J. (Michael Jay) \|Titel=Instructor's manual to accompany Designing efficient algorithms for parallel computers \|Verlag=McGraw-Hill Book Co \|Datum=1987 \|ISBN=0-07-051072-5}}</ref>.		Dieser Ansatz erreicht eine niedrigere Beschleunigung gegenüber dem sequentiellen Quicksort<ref name=":0">{{Literatur \|Autor=Quinn, Michael J. (Michael Jay) \|Titel=Instructor's manual to accompany Designing efficient algorithms for parallel computers \|Verlag=McGraw-Hill Book Co \|Datum=1987 \|ISBN=0-07-051072-5}}</ref>.

	Um eine <math>n</math>-elementige Menge mit einem Pivotelement aus der gleichen Menge zu partitionieren, braucht man <math>n-1</math> Vergleiche. Es sei angenommen, dass ein Vergleich eine Zeiteinheit braucht. Weiterhin, sei die ursprüngliche Größe des Arrays <math>n=2^k-1</math>, die Anzahl an Prozessoren <math>p=2^m</math> mit <math>m<k</math> und das ausgewählte Pivotelement immer der wahre Median von der zu partitionierenden Untermenge.		Um eine <math>n</math>-elementige Menge mit einem [[Pivotelement]] aus der gleichen Menge zu partitionieren, braucht man <math>n-1</math> Vergleiche. Es sei angenommen, dass ein Vergleich eine Zeiteinheit braucht. Weiterhin, sei die ursprüngliche Größe des Arrays <math>n=2^k-1</math>, die Anzahl an Prozessoren <math>p=2^m</math> mit <math>m<k</math> und das ausgewählte Pivotelement immer der wahre Median von der zu partitionierenden Untermenge.

	Unter diesen Annahmen kann die Anzahl der Vergleiche des sequentiellen Algorithmus durch die folgende Rekurrenzrelation bestimmt werden:		Unter diesen Annahmen kann die Anzahl der Vergleiche des sequentiellen Algorithmus durch die folgende Rekurrenzrelation bestimmt werden:

Oschoett: /* Laufzeit */ Typo

2024-07-04T06:30:45Z

Laufzeit: Typo

← Nächstältere Version		Version vom 4. Juli 2024, 08:30 Uhr
Zeile 57:		Zeile 57:
	<math>C_1 = (n+1) \log{p} - 2 (p -1 )</math>		<math>C_1 = (n+1) \log{p} - 2 (p -1 )</math>

	In dem zweiten Abschnitt gibt es mehr Untermengen als Prozessoren verfügbar. Wenn es angenommen wird, dass jeder Prozessor ~~gleichviele~~ Vergleiche durchführt, ist die Laufzeit die Anzahl der Vergleiche dividiert durch <math>p</math>. Daher folgt:		In dem zweiten Abschnitt gibt es mehr Untermengen als Prozessoren verfügbar. Wenn es angenommen wird, dass jeder Prozessor gleich viele Vergleiche durchführt, ist die Laufzeit die Anzahl der Vergleiche dividiert durch <math>p</math>. Daher folgt:

	<math>C_2(n) = T(n) - C_1(n)		<math>C_2(n) = T(n) - C_1(n)

Squasher: Interwikilink gem. Richtlinie unerwünscht, daher entfernt bzw. angepasst

2024-01-03T08:44:39Z

Interwikilink gem. Richtlinie unerwünscht, daher entfernt bzw. angepasst

← Nächstältere Version		Version vom 3. Januar 2024, 10:44 Uhr
Zeile 75:		Zeile 75:

	=== Arbeitsweise ===		=== Arbeitsweise ===
	Der Algorithmus wird in drei Schritten ausgeführt. Erstens wird die ursprüngliche Menge <math>S</math> von <math>n</math> Elementen in <math>p</math> Blöcken aufgeteilt, sodass jeder Block <math>\lceil n/p \rceil</math> Elemente hat, außer der letzte, welcher weniger als <math>\lceil n/p \rceil </math> Elemente haben kann. Jedem Prozessor wird einen Block zugewiesen, d. h. Prozessor <math>i</math> verarbeitet Block <math>i</math>. Ein Pivotelement <math>a</math> wird auswählt und jedem Prozessor mit einem [[~~:en:Broadcast (parallel pattern)\|~~Parallel Broadcasting]] herausgeschickt.		Der Algorithmus wird in drei Schritten ausgeführt. Erstens wird die ursprüngliche Menge <math>S</math> von <math>n</math> Elementen in <math>p</math> Blöcken aufgeteilt, sodass jeder Block <math>\lceil n/p \rceil</math> Elemente hat, außer der letzte, welcher weniger als <math>\lceil n/p \rceil </math> Elemente haben kann. Jedem Prozessor wird einen Block zugewiesen, d. h. Prozessor <math>i</math> verarbeitet Block <math>i</math>. Ein Pivotelement <math>a</math> wird auswählt und jedem Prozessor mit einem [[Parallel Broadcasting]] herausgeschickt.

	In dem zweiten Schritt markiert jeder Prozessor alle Elemente aus seinem Block mit entweder 0 oder 1, abhängig davon, ob das Element kleiner oder größer als das Pivotelement <math>a</math> ist. Mit einem parallelen [[Präfixsumme#Parallele Berechnung\|Präfix Algorithmus]] kann der Rank von jedem Element innerhalb der Gruppe 0 bzw. Gruppe 1 berechnet werden. Die Idee ist, alle Elemente aus allen Blöcken, die mit "0" markiert wurden, vor alle "1"-Elemente aller Blöcken in einem weiteren Array <math>B</math> zu speichern. Der Index vom Element in <math>B</math> wird anhand seines Ranks und der Nummer seines Blocks berechnet. So hat man alle Elemente aus der ursprünglichen Menge <math>S</math> in zwei Teile aufgeteilt – die Menge <math>S_1</math> mit allen "0"-Elementen und <math>S_2</math> mit allen "1"-Elementen.		In dem zweiten Schritt markiert jeder Prozessor alle Elemente aus seinem Block mit entweder 0 oder 1, abhängig davon, ob das Element kleiner oder größer als das Pivotelement <math>a</math> ist. Mit einem parallelen [[Präfixsumme#Parallele Berechnung\|Präfix Algorithmus]] kann der Rank von jedem Element innerhalb der Gruppe 0 bzw. Gruppe 1 berechnet werden. Die Idee ist, alle Elemente aus allen Blöcken, die mit "0" markiert wurden, vor alle "1"-Elemente aller Blöcken in einem weiteren Array <math>B</math> zu speichern. Der Index vom Element in <math>B</math> wird anhand seines Ranks und der Nummer seines Blocks berechnet. So hat man alle Elemente aus der ursprünglichen Menge <math>S</math> in zwei Teile aufgeteilt – die Menge <math>S_1</math> mit allen "0"-Elementen und <math>S_2</math> mit allen "1"-Elementen.
Zeile 85:		Zeile 85:
	Die Laufzeit von dem Algorithmus hängt von der Wahl des Pivotelements. Eine Möglichkeit ist, ein zufälliges Element als Pivot zu nehmen.		Die Laufzeit von dem Algorithmus hängt von der Wahl des Pivotelements. Eine Möglichkeit ist, ein zufälliges Element als Pivot zu nehmen.

	Annehmend, kann ein Prozessor eine zufällige ganze Zahl <math>k</math> von dem Bereich <math>\{1,2,.., n\}</math> in konstante Zeit generieren, dann entspricht die Partitionierung mit Pivotelement – das Element mit Index <math>k</math>, einem Random [[Binäre Suche\|Binary Search]]. Die Analyse<ref>{{Literatur \|Autor=Luc Devroye \|Titel=A note on the height of binary search trees \|Sammelwerk=Journal of the ACM \|Band=33 \|Nummer=3 \|Datum=1986-05-01 \|ISSN=0004-5411 \|Seiten=489–498 \|DOI=10.1145/5925.5930}}</ref> besagt, dass für die Höhe, <math>H_n</math>, von einem [[~~:en:Random binary tree\|~~Random-Binary-Search-Tree]] mit <math>n</math> Elementen, gilt <math> \lim_{n \to \infty} (H_n \ln n) = 4.31107... </math>. Daher liegt die Tiefe der Rekursion bei <math>O( \log n)</math>. Das Pivotelement muss zusätzlich noch verschickt werden. Dies erfolgt in <math>O( \log p )</math><ref>{{Literatur \|Autor=Vishkin, U. \|Titel=Synchronous parallel computation - a survey. \|Verlag=Courant Institute of Mathematical Sciences, New York University \|Datum=1983-04 \|OCLC=1085604497}}</ref>. Jeder Prozessor muss dann die Elemente in seinem Block markieren, die Präfix Summe muss berechnet werden<ref>{{Literatur \|Autor=Richard Cole, Uzi Vishkin \|Titel=Approximate and exact parallel scheduling with applications to list, tree and graph problems \|Sammelwerk=27th Annual Symposium on Foundations of Computer Science (sfcs 1986) \|Verlag=IEEE \|Datum=1986 \|ISBN=0-8186-0740-8 \|DOI=10.1109/sfcs.1986.10}}</ref> und die Elemente verschoben werden. Dies braucht gesamt <math>O(n/p + \log p)</math>. Anschließend berechnet man die Gesamtlaufzeit für diesen Fall, diese ist <math>O((n/p)+\log p ) \log n )</math> erwartet.		Annehmend, kann ein Prozessor eine zufällige ganze Zahl <math>k</math> von dem Bereich <math>\{1,2,.., n\}</math> in konstante Zeit generieren, dann entspricht die Partitionierung mit Pivotelement – das Element mit Index <math>k</math>, einem Random [[Binäre Suche\|Binary Search]]. Die Analyse<ref>{{Literatur \|Autor=Luc Devroye \|Titel=A note on the height of binary search trees \|Sammelwerk=Journal of the ACM \|Band=33 \|Nummer=3 \|Datum=1986-05-01 \|ISSN=0004-5411 \|Seiten=489–498 \|DOI=10.1145/5925.5930}}</ref> besagt, dass für die Höhe, <math>H_n</math>, von einem [[Random-Binary-Search-Tree]] mit <math>n</math> Elementen, gilt <math> \lim_{n \to \infty} (H_n \ln n) = 4.31107... </math>. Daher liegt die Tiefe der Rekursion bei <math>O( \log n)</math>. Das Pivotelement muss zusätzlich noch verschickt werden. Dies erfolgt in <math>O( \log p )</math><ref>{{Literatur \|Autor=Vishkin, U. \|Titel=Synchronous parallel computation - a survey. \|Verlag=Courant Institute of Mathematical Sciences, New York University \|Datum=1983-04 \|OCLC=1085604497}}</ref>. Jeder Prozessor muss dann die Elemente in seinem Block markieren, die Präfix Summe muss berechnet werden<ref>{{Literatur \|Autor=Richard Cole, Uzi Vishkin \|Titel=Approximate and exact parallel scheduling with applications to list, tree and graph problems \|Sammelwerk=27th Annual Symposium on Foundations of Computer Science (sfcs 1986) \|Verlag=IEEE \|Datum=1986 \|ISBN=0-8186-0740-8 \|DOI=10.1109/sfcs.1986.10}}</ref> und die Elemente verschoben werden. Dies braucht gesamt <math>O(n/p + \log p)</math>. Anschließend berechnet man die Gesamtlaufzeit für diesen Fall, diese ist <math>O((n/p)+\log p ) \log n )</math> erwartet.

	In dem Fall, dass das Pivotelement nicht zufällig gewählt wurde, hängt die Laufzeit des Algorithmus von der Rekursionstiefe und damit auch von dem Verhältnis der Größen <math>S_1</math> und <math>S_2</math> ab. Die Rekursionstiefe vom Algorithmus kann auf <math>O( \log n )</math> begrenzt werden, wenn <math>S_1</math> und <math>S_2</math> ungefähr gleich sind. Dies kann gewährleistet werden, indem die Auswahl des Pivotelements mit dem Parallel Median Finding Algorithm von Akl auf eine EREW PRAM in <math>O(\log \log n)</math> Zeit<ref>Akl, S. G. "Parallel Selection in O(log log n) Time Using O(n/log log n) Processors." ''Technical Report 88-221, Department of Computing and Information Science, Queen's University, Kingston, Ontario'' (1988).</ref> erfolgt. Das Markieren, die Präfix Summe und das Verschieben der Elemente erfolgt analog zu dem anderen Fall. Mit dem [[Brent-Verfahren]] kann folglich der Algorithmus in <math>O((n/p + \log p + \log \log n) \log n)</math> deterministisch implementiert werden.		In dem Fall, dass das Pivotelement nicht zufällig gewählt wurde, hängt die Laufzeit des Algorithmus von der Rekursionstiefe und damit auch von dem Verhältnis der Größen <math>S_1</math> und <math>S_2</math> ab. Die Rekursionstiefe vom Algorithmus kann auf <math>O( \log n )</math> begrenzt werden, wenn <math>S_1</math> und <math>S_2</math> ungefähr gleich sind. Dies kann gewährleistet werden, indem die Auswahl des Pivotelements mit dem Parallel Median Finding Algorithm von Akl auf eine EREW PRAM in <math>O(\log \log n)</math> Zeit<ref>Akl, S. G. "Parallel Selection in O(log log n) Time Using O(n/log log n) Processors." ''Technical Report 88-221, Department of Computing and Information Science, Queen's University, Kingston, Ontario'' (1988).</ref> erfolgt. Das Markieren, die Präfix Summe und das Verschieben der Elemente erfolgt analog zu dem anderen Fall. Mit dem [[Brent-Verfahren]] kann folglich der Algorithmus in <math>O((n/p + \log p + \log \log n) \log n)</math> deterministisch implementiert werden.

93.202.155.94: Index ist maskulin

2023-06-11T10:40:19Z

Index ist maskulin

← Nächstältere Version		Version vom 11. Juni 2023, 12:40 Uhr
Zeile 77:		Zeile 77:
	Der Algorithmus wird in drei Schritten ausgeführt. Erstens wird die ursprüngliche Menge <math>S</math> von <math>n</math> Elementen in <math>p</math> Blöcken aufgeteilt, sodass jeder Block <math>\lceil n/p \rceil</math> Elemente hat, außer der letzte, welcher weniger als <math>\lceil n/p \rceil </math> Elemente haben kann. Jedem Prozessor wird einen Block zugewiesen, d. h. Prozessor <math>i</math> verarbeitet Block <math>i</math>. Ein Pivotelement <math>a</math> wird auswählt und jedem Prozessor mit einem [[:en:Broadcast (parallel pattern)\|Parallel Broadcasting]] herausgeschickt.		Der Algorithmus wird in drei Schritten ausgeführt. Erstens wird die ursprüngliche Menge <math>S</math> von <math>n</math> Elementen in <math>p</math> Blöcken aufgeteilt, sodass jeder Block <math>\lceil n/p \rceil</math> Elemente hat, außer der letzte, welcher weniger als <math>\lceil n/p \rceil </math> Elemente haben kann. Jedem Prozessor wird einen Block zugewiesen, d. h. Prozessor <math>i</math> verarbeitet Block <math>i</math>. Ein Pivotelement <math>a</math> wird auswählt und jedem Prozessor mit einem [[:en:Broadcast (parallel pattern)\|Parallel Broadcasting]] herausgeschickt.

	In dem zweiten Schritt markiert jeder Prozessor alle Elemente aus seinem Block mit entweder 0 oder 1, abhängig davon, ob das Element kleiner oder größer als das Pivotelement <math>a</math> ist. Mit einem parallelen [[Präfixsumme#Parallele Berechnung\|Präfix Algorithmus]] kann der Rank von jedem Element innerhalb der Gruppe 0 bzw. Gruppe 1 berechnet werden. Die Idee ist, alle Elemente aus allen Blöcken, die mit "0" markiert wurden, vor alle "1"-Elemente aller Blöcken in einem weiteren Array <math>B</math> zu speichern. ~~Das~~ Index vom Element in <math>B</math> wird anhand seines Ranks und der Nummer seines Blocks berechnet. So hat man alle Elemente aus der ursprünglichen Menge <math>S</math> in zwei Teile aufgeteilt – die Menge <math>S_1</math> mit allen "0"-Elementen und <math>S_2</math> mit allen "1"-Elementen.		In dem zweiten Schritt markiert jeder Prozessor alle Elemente aus seinem Block mit entweder 0 oder 1, abhängig davon, ob das Element kleiner oder größer als das Pivotelement <math>a</math> ist. Mit einem parallelen [[Präfixsumme#Parallele Berechnung\|Präfix Algorithmus]] kann der Rank von jedem Element innerhalb der Gruppe 0 bzw. Gruppe 1 berechnet werden. Die Idee ist, alle Elemente aus allen Blöcken, die mit "0" markiert wurden, vor alle "1"-Elemente aller Blöcken in einem weiteren Array <math>B</math> zu speichern. Der Index vom Element in <math>B</math> wird anhand seines Ranks und der Nummer seines Blocks berechnet. So hat man alle Elemente aus der ursprünglichen Menge <math>S</math> in zwei Teile aufgeteilt – die Menge <math>S_1</math> mit allen "0"-Elementen und <math>S_2</math> mit allen "1"-Elementen.

	Der dritte Schritt besteht aus der Überprüfung der Länge von <math>S_1</math> und <math>S_2</math> und wenn diese mehr als ein Element enthalten, folgt ein rekursiver Aufruf von Schritt eins auf beide.		Der dritte Schritt besteht aus der Überprüfung der Länge von <math>S_1</math> und <math>S_2</math> und wenn diese mehr als ein Element enthalten, folgt ein rekursiver Aufruf von Schritt eins auf beide.

Schaebibuxe: /* Parallelisierung von Quicksort auf EREW PRAM */

2022-11-05T19:16:28Z

Parallelisierung von Quicksort auf EREW PRAM

← Nächstältere Version		Version vom 5. November 2022, 21:16 Uhr
Zeile 72:		Zeile 72:
	== Parallelisierung von Quicksort auf EREW PRAM ==		== Parallelisierung von Quicksort auf EREW PRAM ==

	Im Jahr 1991, stellen Zhang und Nageswara eine Möglichkeit für die Parallelisierung von Quicksort auf einer [[Parallel Random Access Machine\|EREW PRAM]] vor<ref name=":2">{{Literatur \|Autor=Weixiong Zhang, Nageswara S. V. Rao \|Titel=Optimal parallel quicksort on EREW PRAM \|Sammelwerk=BIT \|Band=31 \|Nummer=1 \|Datum=1991-03 \|ISSN=0006-3835 \|Seiten=69–74 \|DOI=10.1007/bf01952784}}</ref>. Der Algorithmus sortiert <math>n</math> Elemente mit <math>p</math> Prozessoren in <math>O((n/p)+\log p ) \log n )</math> erwartete Laufzeit und in <math>O((n/p + \log p + \log \log n) \log n)</math> deterministische Laufzeit mit <math>O(n)</math> an Speicherbedarf. In dem Fall, dass <math>p = O(n/ \log n)</math> ist, dann sind die Kosten optimal in Bezug auf das Produkt von der Zeit und Anzahl von Prozessoren.		Im Jahr 1991, stellen Zhang und Nageswara eine Möglichkeit für die Parallelisierung von Quicksort auf einer [[Parallel Random Access Machine\|EREW PRAM]] vor<ref name=":2">{{Literatur \|Autor=Weixiong Zhang, Nageswara S. V. Rao \|Titel=Optimal parallel quicksort on EREW PRAM \|Sammelwerk=BIT \|Band=31 \|Nummer=1 \|Datum=1991-03 \|ISSN=0006-3835 \|Seiten=69–74 \|DOI=10.1007/bf01952784}}</ref>. Der Algorithmus sortiert <math>n</math> Elemente mit <math>p</math> Prozessoren in <math>O((n/p+\log p ) \log n )</math> erwartete Laufzeit und in <math>O((n/p + \log p + \log \log n) \log n)</math> deterministische Laufzeit mit <math>O(n)</math> an Speicherbedarf. In dem Fall, dass <math>p = O(n/ \log n)</math> ist, dann sind die Kosten optimal in Bezug auf das Produkt von der Zeit und Anzahl von Prozessoren.

	=== Arbeitsweise ===		=== Arbeitsweise ===

TuxedoMask2002: Rechtschreibfehler korrigiert, umgangssprachliche Formulierungen gegen Hochdeutsch ersetzt.

2021-06-10T07:03:12Z

Rechtschreibfehler korrigiert, umgangssprachliche Formulierungen gegen Hochdeutsch ersetzt.

← Nächstältere Version		Version vom 10. Juni 2021, 09:03 Uhr
Zeile 93:		Zeile 93:

	=== Arbeitsweise ===		=== Arbeitsweise ===
	Zuerst ~~kommt~~ ~~die~~ ~~Wahl~~ ~~des Pivotelements~~. Dieses ist der Median ~~von mehrere~~ Elementen aus dem Array. Die Partitionierungsphase fängt mit der Aufteilung der Elemente in ~~kleineren~~ Gruppen ~~oder~~ Chunks an. ~~Dann~~ ~~bekommt~~ jeder Thread zwei Chunks zur Verarbeitung. ~~Wenn~~ es ~~weniger~~ Chunks ~~gibt, sodass~~ diese ~~Bedienung~~ ~~erfüllt~~ ~~werden kann~~, werden weniger Threads, als ~~erwünscht,~~ benutzt. Jeder Thread sortiert seine Elemente, sodass in ~~dem~~ linken Chunk nur Elemente kleiner als das Pivotelement liegen ~~und~~ bzw. nur größere ~~in dem~~ rechten. Dann reserviert ~~parallel~~ jeder Thread Platz für seine zwei Chunks. Die ~~linke~~ Chunks ~~von~~ ~~jedem~~ ~~Thread~~ ~~kommen~~ am Anfang ~~vom~~ ~~Array~~ ~~und~~ die ~~rechte~~ Chunks am Ende. Damit ist die Partitionierung ~~fertig~~.		Zuerst wird das Pivotelement gewählt. Dieses ist der Median mehrerer Elementen aus dem Array. Die Partitionierungsphase fängt mit der Aufteilung der Elemente in kleinere Gruppen, auch Chunks genannt, an. Anschließend erhält jeder Thread zwei Chunks zur Verarbeitung. Existieren nicht genügend Chunks um diese Bedingung zu erfüllen, werden weniger Threads als angefordert benutzt. Jeder Thread sortiert seine Elemente, sodass in seinem linken Chunk nur Elemente kleiner als das Pivotelement liegen bzw. nur größere im rechten. Dann reserviert jeder Thread parallel Platz für seine zwei Chunks. Die linken Chunks jedes Threads werden an den Anfang dieses Arrays geschrieben, die rechten Chunks am Ende. Damit ist die Partitionierung beendet.

	=== Balancierte Lastverteilung ===		=== Balancierte Lastverteilung ===

Crazy1880: Vorlagen-fix (OCLC)

2020-04-13T08:57:18Z

Vorlagen-fix (OCLC)

← Nächstältere Version		Version vom 13. April 2020, 10:57 Uhr
Zeile 17:		Zeile 17:
	Die Reihenfolge bei der Allokation von Prozessoren an Untermengen wird dynamisch angepasst. Prozessor 1 partitioniert die Menge der Elemente mit Index <math>(1,n)</math>. Die erste entstandene Untermenge, <math>(1, k_{1} - 1)</math>, verarbeitet wieder Prozessor 1 und die zweite, <math>(k_{1} +1, n)</math>, Prozessor 2. Die Menge der Elemente <math>(k_1 + 1, n)</math> ist o. B. d. A. die kleinere von beiden. Daher ist es plausibler, dass diese von Prozessor 2 schneller partitioniert wird. Prozessor 2 fordert also früher als Prozessor 1 für seine Untermengen einen neuen Prozessor an. Infolgedessen verarbeitet Prozessor 2 die eine erhaltene Untermenge, während Prozessor 3 die andere. Wenn Prozessor 1 einen neuen Prozessor anfordert, bekommt er Prozessor 4, weil dieser zurzeit frei ist.		Die Reihenfolge bei der Allokation von Prozessoren an Untermengen wird dynamisch angepasst. Prozessor 1 partitioniert die Menge der Elemente mit Index <math>(1,n)</math>. Die erste entstandene Untermenge, <math>(1, k_{1} - 1)</math>, verarbeitet wieder Prozessor 1 und die zweite, <math>(k_{1} +1, n)</math>, Prozessor 2. Die Menge der Elemente <math>(k_1 + 1, n)</math> ist o. B. d. A. die kleinere von beiden. Daher ist es plausibler, dass diese von Prozessor 2 schneller partitioniert wird. Prozessor 2 fordert also früher als Prozessor 1 für seine Untermengen einen neuen Prozessor an. Infolgedessen verarbeitet Prozessor 2 die eine erhaltene Untermenge, während Prozessor 3 die andere. Wenn Prozessor 1 einen neuen Prozessor anfordert, bekommt er Prozessor 4, weil dieser zurzeit frei ist.

	Das folgende Pseudocode skizziert eine Implementierung von Parallel Quicksort. <math>M</math> bezeichnet die maximale Größe des Array, welcher effizienter mit einem sequentiellen Sortieralgorithmus, z. B. [[Insertionsort]], zu sortieren ist.		Das folgende Pseudocode skizziert eine Implementierung von Parallel Quicksort. <math>M</math> bezeichnet die maximale Größe des Array, welcher effizienter mit einem sequentiellen Sortieralgorithmus, z. B. [[Insertionsort]], zu sortieren ist.
	<syntaxhighlight lang="c">		<syntaxhighlight lang="c">
	PROCEDURE QUICKSORT (L,U);		PROCEDURE QUICKSORT (L,U);
Zeile 85:		Zeile 85:
	Die Laufzeit von dem Algorithmus hängt von der Wahl des Pivotelements. Eine Möglichkeit ist, ein zufälliges Element als Pivot zu nehmen.		Die Laufzeit von dem Algorithmus hängt von der Wahl des Pivotelements. Eine Möglichkeit ist, ein zufälliges Element als Pivot zu nehmen.

	Annehmend, kann ein Prozessor eine zufällige ganze Zahl <math>k</math> von dem Bereich <math>\{1,2,.., n\}</math> in konstante Zeit generieren, dann entspricht die Partitionierung mit Pivotelement – das Element mit Index <math>k</math>, einem Random [[Binäre Suche\|Binary Search]]. Die Analyse<ref>{{Literatur \|Autor=Luc Devroye \|Titel=A note on the height of binary search trees \|Sammelwerk=Journal of the ACM \|Band=33 \|Nummer=3 \|Datum=1986-05-01 \|ISSN=0004-5411 \|Seiten=489–498 \|DOI=10.1145/5925.5930}}</ref> besagt, dass für die Höhe, <math>H_n</math>, von einem [[:en:Random binary tree\|Random-Binary-Search-Tree]] mit <math>n</math> Elementen, gilt <math> \lim_{n \to \infty} (H_n \ln n) = 4.31107... </math>. Daher liegt die Tiefe der Rekursion bei <math>O( \log n)</math>. Das Pivotelement muss zusätzlich noch verschickt werden. Dies erfolgt in <math>O( \log p )</math><ref>{{Literatur \|Autor=Vishkin, U. \|Titel=Synchronous parallel computation - a survey. \|Verlag=Courant Institute of Mathematical Sciences, New York University \|Datum=1983-04 \|~~Online~~=~~http://worldcat.org/oclc/~~1085604497 ~~\|Abruf=2020-02-15~~}}</ref>. Jeder Prozessor muss dann die Elemente in seinem Block markieren, die Präfix Summe muss berechnet werden<ref>{{Literatur \|Autor=Richard Cole, Uzi Vishkin \|Titel=Approximate and exact parallel scheduling with applications to list, tree and graph problems \|Sammelwerk=27th Annual Symposium on Foundations of Computer Science (sfcs 1986) \|Verlag=IEEE \|Datum=1986 \|ISBN=0-8186-0740-8 \|DOI=10.1109/sfcs.1986.10}}</ref> und die Elemente verschoben werden. Dies braucht gesamt <math>O(n/p + \log p)</math>. Anschließend berechnet man die Gesamtlaufzeit für diesen Fall, diese ist <math>O((n/p)+\log p ) \log n )</math> erwartet.		Annehmend, kann ein Prozessor eine zufällige ganze Zahl <math>k</math> von dem Bereich <math>\{1,2,.., n\}</math> in konstante Zeit generieren, dann entspricht die Partitionierung mit Pivotelement – das Element mit Index <math>k</math>, einem Random [[Binäre Suche\|Binary Search]]. Die Analyse<ref>{{Literatur \|Autor=Luc Devroye \|Titel=A note on the height of binary search trees \|Sammelwerk=Journal of the ACM \|Band=33 \|Nummer=3 \|Datum=1986-05-01 \|ISSN=0004-5411 \|Seiten=489–498 \|DOI=10.1145/5925.5930}}</ref> besagt, dass für die Höhe, <math>H_n</math>, von einem [[:en:Random binary tree\|Random-Binary-Search-Tree]] mit <math>n</math> Elementen, gilt <math> \lim_{n \to \infty} (H_n \ln n) = 4.31107... </math>. Daher liegt die Tiefe der Rekursion bei <math>O( \log n)</math>. Das Pivotelement muss zusätzlich noch verschickt werden. Dies erfolgt in <math>O( \log p )</math><ref>{{Literatur \|Autor=Vishkin, U. \|Titel=Synchronous parallel computation - a survey. \|Verlag=Courant Institute of Mathematical Sciences, New York University \|Datum=1983-04 \|OCLC=1085604497}}</ref>. Jeder Prozessor muss dann die Elemente in seinem Block markieren, die Präfix Summe muss berechnet werden<ref>{{Literatur \|Autor=Richard Cole, Uzi Vishkin \|Titel=Approximate and exact parallel scheduling with applications to list, tree and graph problems \|Sammelwerk=27th Annual Symposium on Foundations of Computer Science (sfcs 1986) \|Verlag=IEEE \|Datum=1986 \|ISBN=0-8186-0740-8 \|DOI=10.1109/sfcs.1986.10}}</ref> und die Elemente verschoben werden. Dies braucht gesamt <math>O(n/p + \log p)</math>. Anschließend berechnet man die Gesamtlaufzeit für diesen Fall, diese ist <math>O((n/p)+\log p ) \log n )</math> erwartet.

	In dem Fall, dass das Pivotelement nicht zufällig gewählt wurde, hängt die Laufzeit des Algorithmus von der Rekursionstiefe und damit auch von dem Verhältnis der Größen <math>S_1</math> und <math>S_2</math> ab. Die Rekursionstiefe vom Algorithmus kann auf <math>O( \log n )</math> begrenzt werden, wenn <math>S_1</math> und <math>S_2</math> ungefähr gleich sind. Dies kann gewährleistet werden, indem die Auswahl des Pivotelements mit dem Parallel Median Finding Algorithm von Akl auf eine EREW PRAM in <math>O(\log \log n)</math> Zeit<ref>Akl, S. G. "Parallel Selection in O(log log n) Time Using O(n/log log n) Processors." ''Technical Report 88-221, Department of Computing and Information Science, Queen's University, Kingston, Ontario'' (1988).</ref> erfolgt. Das Markieren, die Präfix Summe und das Verschieben der Elemente erfolgt analog zu dem anderen Fall. Mit dem [[Brent-Verfahren]] kann folglich der Algorithmus in <math>O((n/p + \log p + \log \log n) \log n)</math> deterministisch implementiert werden.		In dem Fall, dass das Pivotelement nicht zufällig gewählt wurde, hängt die Laufzeit des Algorithmus von der Rekursionstiefe und damit auch von dem Verhältnis der Größen <math>S_1</math> und <math>S_2</math> ab. Die Rekursionstiefe vom Algorithmus kann auf <math>O( \log n )</math> begrenzt werden, wenn <math>S_1</math> und <math>S_2</math> ungefähr gleich sind. Dies kann gewährleistet werden, indem die Auswahl des Pivotelements mit dem Parallel Median Finding Algorithm von Akl auf eine EREW PRAM in <math>O(\log \log n)</math> Zeit<ref>Akl, S. G. "Parallel Selection in O(log log n) Time Using O(n/log log n) Processors." ''Technical Report 88-221, Department of Computing and Information Science, Queen's University, Kingston, Ontario'' (1988).</ref> erfolgt. Das Markieren, die Präfix Summe und das Verschieben der Elemente erfolgt analog zu dem anderen Fall. Mit dem [[Brent-Verfahren]] kann folglich der Algorithmus in <math>O((n/p + \log p + \log \log n) \log n)</math> deterministisch implementiert werden.

	== Implementierung von Quicksort in MCSTL ==		== Implementierung von Quicksort in MCSTL ==
	Eine parallele Implementierung für Quicksort ist in der MCSTL Bibliothek<ref>{{Literatur \|Autor=Putze, Felix. \|Titel=MCSTL: the multi-core standard template library \|Verlag=ACM \|Datum=2007 \|~~Online~~=~~http://worldcat.org/oclc/~~854741854 ~~\|Abruf=2020-02-16~~}}</ref> zu finden. Die zwei Funktionen <math>parallel\_sort\_qsb</math> und <math>parallel\_sort\_qs</math> stehen zur Verfügung. Der Hauptunterschied bei <math>parallel\_sort\_qs</math> liegt bei der durch [[Work stealing]] realisierten balancierten Lastverteilung. Bei beiden Funktionen ist die Pivotwahl <!-- und Arbeitsverteilung -->von einem Prozessor und die Partitionierung parallel von mehreren Prozessoren durchgeführt. Die gewünschte Anzahl von Threads, die benutzt werden müssen, wird als Parameter an dem Algorithmus gegeben.		Eine parallele Implementierung für Quicksort ist in der MCSTL Bibliothek<ref>{{Literatur \|Autor=Putze, Felix. \|Titel=MCSTL: the multi-core standard template library \|Verlag=ACM \|Datum=2007 \|OCLC=854741854}}</ref> zu finden. Die zwei Funktionen <math>parallel\_sort\_qsb</math> und <math>parallel\_sort\_qs</math> stehen zur Verfügung. Der Hauptunterschied bei <math>parallel\_sort\_qs</math> liegt bei der durch [[Work stealing]] realisierten balancierten Lastverteilung. Bei beiden Funktionen ist die Pivotwahl <!-- und Arbeitsverteilung -->von einem Prozessor und die Partitionierung parallel von mehreren Prozessoren durchgeführt. Die gewünschte Anzahl von Threads, die benutzt werden müssen, wird als Parameter an dem Algorithmus gegeben.

	=== Arbeitsweise ===		=== Arbeitsweise ===

Krd am 4. April 2020 um 17:14 Uhr

2020-04-04T17:14:53Z

← Nächstältere Version		Version vom 4. April 2020, 19:14 Uhr
Zeile 1:		Zeile 1:
	{{QS-Antrag\|25. Februar 2020\|2=''Wikifizieren'' [[Benutzer:Lutheraner\|Lutheraner]] ([[Benutzer Diskussion:Lutheraner\|Diskussion]]) 16:33, 25. Feb. 2020 (CET)}}
	'''Parallel Quicksort''' beschreibt Parallelisierungen des sequentiellen Algorithmus [[Quicksort]], welcher auf dem [[Teile-und-herrsche-Verfahren\|Teile-und-Herrsche-Prinzip]] basiert.		'''Parallel Quicksort''' beschreibt Parallelisierungen des sequentiellen Algorithmus [[Quicksort]], welcher auf dem [[Teile-und-herrsche-Verfahren\|Teile-und-Herrsche-Prinzip]] basiert.

Snookerado: Vorlagenfix

2020-02-29T20:48:40Z

Vorlagenfix

← Nächstältere Version		Version vom 29. Februar 2020, 22:48 Uhr
Zeile 4:		Zeile 4:
	Wie Quicksort teilt Parallel Quicksort eine Menge von Elementen mithilfe eines Pivotelements in zwei Teilmengen auf, sodass die Elemente in der einen Teilmenge kleiner als das Pivot sind und die Elemente in der anderen Teilmenge größer oder gleich dem Pivot sind. Danach werden die neuen Mengen wieder jeweils in Teilmengen unterteilt.		Wie Quicksort teilt Parallel Quicksort eine Menge von Elementen mithilfe eines Pivotelements in zwei Teilmengen auf, sodass die Elemente in der einen Teilmenge kleiner als das Pivot sind und die Elemente in der anderen Teilmenge größer oder gleich dem Pivot sind. Danach werden die neuen Mengen wieder jeweils in Teilmengen unterteilt.

	Dieses Vorgehen kann auf verschiedene Arten parallel implementiert werden. Zum einen können mehrere Mengen von jeweils einem Prozess in neue Teilmengen aufgeteilt werden<ref name=":1">{{Literatur \|Autor=D.J. Evans, R.C Dunbar \|Titel=The parallel quicksort algorithm part i–run time analysis \|Sammelwerk=International Journal of Computer Mathematics \|Band=12 \|Nummer=1 \|Datum=1982-01 \|ISSN=0020-7160 ~~\|DOI=10.1080/00207168208803323~~ \|Seiten=19–55 \|~~Online~~=~~http://dx.doi.org/~~10.1080/00207168208803323 ~~\|Abruf=2020-02-15~~}}</ref>. Dies hat den Nachteil, dass der erste Rekursionslevel nicht parallelisiert ist und der Speedup gegenüber Quicksort auf <math>O(\log n)</math> begrenzt ist. Zum anderen können mehrere Prozesse zusammen arbeiten und gemeinsam eine einzelne Menge aufteilen. Dieser Ansatz hat sich in der Praxis als effizienter erwiesen. Parallel Quicksort kann im PRAM Modell mit einer Laufzeit von <math>O((n/p + \log p + \log \log n)\log n)</math> implementiert werden<ref name=":2" />.		Dieses Vorgehen kann auf verschiedene Arten parallel implementiert werden. Zum einen können mehrere Mengen von jeweils einem Prozess in neue Teilmengen aufgeteilt werden<ref name=":1">{{Literatur \|Autor=D.J. Evans, R.C Dunbar \|Titel=The parallel quicksort algorithm part i–run time analysis \|Sammelwerk=International Journal of Computer Mathematics \|Band=12 \|Nummer=1 \|Datum=1982-01 \|ISSN=0020-7160 \|Seiten=19–55 \|DOI=10.1080/00207168208803323}}</ref>. Dies hat den Nachteil, dass der erste Rekursionslevel nicht parallelisiert ist und der Speedup gegenüber Quicksort auf <math>O(\log n)</math> begrenzt ist. Zum anderen können mehrere Prozesse zusammen arbeiten und gemeinsam eine einzelne Menge aufteilen. Dieser Ansatz hat sich in der Praxis als effizienter erwiesen. Parallel Quicksort kann im PRAM Modell mit einer Laufzeit von <math>O((n/p + \log p + \log \log n)\log n)</math> implementiert werden<ref name=":2" />.

	== Naiver Ansatz ==		== Naiver Ansatz ==
Zeile 13:		Zeile 13:
	Es ist dabei möglich, dass manche Prozessoren schneller mit der Partitionierung seiner Untermenge fertig sind, im Vergleich zu anderen. Eine Warteschlange kann dazu benutzt werden, wo die Zeiger auf noch nicht partitionierte Untermengen gespeichert werden. Bei der Entfernung von der Warteschlange sind die größeren Untermengen bevorzugt, da diese neue kleinere Untermengen erzeugen, die wiederum in die Warteschlange kommen. Das Ziel dabei ist, möglichst viele Untermengen zu haben, und dabei die Prozessoren dauerhaft besetzt zu halten.		Es ist dabei möglich, dass manche Prozessoren schneller mit der Partitionierung seiner Untermenge fertig sind, im Vergleich zu anderen. Eine Warteschlange kann dazu benutzt werden, wo die Zeiger auf noch nicht partitionierte Untermengen gespeichert werden. Bei der Entfernung von der Warteschlange sind die größeren Untermengen bevorzugt, da diese neue kleinere Untermengen erzeugen, die wiederum in die Warteschlange kommen. Das Ziel dabei ist, möglichst viele Untermengen zu haben, und dabei die Prozessoren dauerhaft besetzt zu halten.

	[[Datei:Allokation von Prozessoren.svg\|mini\|Allokation von Prozessoren bei der Ausführung von Parallel Quicksort\|~~alternativtext~~=~~\|350x350px~~]]		[[Datei:Allokation von Prozessoren.svg\|mini\|350x350px\|Allokation von Prozessoren bei der Ausführung von Parallel Quicksort\|alt=]]

	==== Allokation von Prozessoren ====		==== Allokation von Prozessoren ====
	Die Reihenfolge bei der Allokation von Prozessoren an Untermengen wird dynamisch angepasst. Prozessor 1 partitioniert die Menge der Elemente mit Index <math>(1,n)</math>. Die erste entstandene Untermenge, <math>(1, k_{1} - 1)</math>, verarbeitet wieder Prozessor 1 und die zweite, <math>(k_{1} +1, n)</math>, Prozessor 2. Die Menge der Elemente <math>(k_1 + 1, n)</math> ist o. B. d. A. die kleinere von beiden. Daher ist es plausibler, dass diese von Prozessor 2 schneller partitioniert wird. Prozessor 2 fordert also früher als Prozessor 1 für seine Untermengen einen neuen Prozessor an. Infolgedessen verarbeitet Prozessor 2 die eine erhaltene Untermenge, während Prozessor 3 die andere. Wenn Prozessor 1 einen neuen Prozessor anfordert, bekommt er Prozessor 4, weil dieser zurzeit frei ist.		Die Reihenfolge bei der Allokation von Prozessoren an Untermengen wird dynamisch angepasst. Prozessor 1 partitioniert die Menge der Elemente mit Index <math>(1,n)</math>. Die erste entstandene Untermenge, <math>(1, k_{1} - 1)</math>, verarbeitet wieder Prozessor 1 und die zweite, <math>(k_{1} +1, n)</math>, Prozessor 2. Die Menge der Elemente <math>(k_1 + 1, n)</math> ist o. B. d. A. die kleinere von beiden. Daher ist es plausibler, dass diese von Prozessor 2 schneller partitioniert wird. Prozessor 2 fordert also früher als Prozessor 1 für seine Untermengen einen neuen Prozessor an. Infolgedessen verarbeitet Prozessor 2 die eine erhaltene Untermenge, während Prozessor 3 die andere. Wenn Prozessor 1 einen neuen Prozessor anfordert, bekommt er Prozessor 4, weil dieser zurzeit frei ist.

	Das folgende Pseudocode skizziert eine Implementierung von Parallel Quicksort. <math>M</math> bezeichnet die maximale Größe des Array, welcher effizienter mit einem sequentiellen Sortieralgorithmus, z. B. [[Insertionsort]], zu sortieren ist. <syntaxhighlight lang="c">		Das folgende Pseudocode skizziert eine Implementierung von Parallel Quicksort. <math>M</math> bezeichnet die maximale Größe des Array, welcher effizienter mit einem sequentiellen Sortieralgorithmus, z. B. [[Insertionsort]], zu sortieren ist.
			<syntaxhighlight lang="c">
	PROCEDURE QUICKSORT (L,U);		PROCEDURE QUICKSORT (L,U);
	IF U-L > M THEN;		IF U-L > M THEN;
Zeile 35:		Zeile 36:

	=== Laufzeit ===		=== Laufzeit ===
	Dieser Ansatz erreicht eine niedrigere Beschleunigung gegenüber dem sequentiellen Quicksort<ref name=":0">{{Literatur \|Autor=Quinn, Michael J. (Michael Jay) \|Titel=Instructor's manual to accompany Designing efficient algorithms for parallel computers \|Verlag=McGraw-Hill Book Co \|Datum=1987 \|ISBN=0-07-051072-5 ~~\|Online=http://worldcat.org/oclc/53588516 \|Abruf=2020-02-16~~}}</ref>.		Dieser Ansatz erreicht eine niedrigere Beschleunigung gegenüber dem sequentiellen Quicksort<ref name=":0">{{Literatur \|Autor=Quinn, Michael J. (Michael Jay) \|Titel=Instructor's manual to accompany Designing efficient algorithms for parallel computers \|Verlag=McGraw-Hill Book Co \|Datum=1987 \|ISBN=0-07-051072-5}}</ref>.

	Um eine <math>n</math>-elementige Menge mit einem Pivotelement aus der gleichen Menge zu partitionieren, braucht man <math>n-1</math> Vergleiche. Es sei angenommen, dass ein Vergleich eine Zeiteinheit braucht. Weiterhin, sei die ursprüngliche Größe des Arrays <math>n=2^k-1</math>, die Anzahl an Prozessoren <math>p=2^m</math> mit <math>m<k</math> und das ausgewählte Pivotelement immer der wahre Median von der zu partitionierenden Untermenge.		Um eine <math>n</math>-elementige Menge mit einem Pivotelement aus der gleichen Menge zu partitionieren, braucht man <math>n-1</math> Vergleiche. Es sei angenommen, dass ein Vergleich eine Zeiteinheit braucht. Weiterhin, sei die ursprüngliche Größe des Arrays <math>n=2^k-1</math>, die Anzahl an Prozessoren <math>p=2^m</math> mit <math>m<k</math> und das ausgewählte Pivotelement immer der wahre Median von der zu partitionierenden Untermenge.
Zeile 72:		Zeile 73:
	== Parallelisierung von Quicksort auf EREW PRAM ==		== Parallelisierung von Quicksort auf EREW PRAM ==

	Im Jahr 1991, stellen Zhang und Nageswara eine Möglichkeit für die Parallelisierung von Quicksort auf einer [[Parallel Random Access Machine\|EREW PRAM]] vor<ref name=":2">{{Literatur \|Autor=Weixiong Zhang, Nageswara S. V. Rao \|Titel=Optimal parallel quicksort on EREW PRAM \|Sammelwerk=BIT \|Band=31 \|Nummer=1 \|Datum=1991-03 \|ISSN=0006-3835 ~~\|DOI=10.1007/bf01952784~~ \|Seiten=69–74 \|~~Online~~=~~http://dx.doi.org/~~10.1007/bf01952784 ~~\|Abruf=2020-02-15~~}}</ref>. Der Algorithmus sortiert <math>n</math> Elemente mit <math>p</math> Prozessoren in <math>O((n/p)+\log p ) \log n )</math> erwartete Laufzeit und in <math>O((n/p + \log p + \log \log n) \log n)</math> deterministische Laufzeit mit <math>O(n)</math> an Speicherbedarf. In dem Fall, dass <math>p = O(n/ \log n)</math> ist, dann sind die Kosten optimal in Bezug auf das Produkt von der Zeit und Anzahl von Prozessoren.		Im Jahr 1991, stellen Zhang und Nageswara eine Möglichkeit für die Parallelisierung von Quicksort auf einer [[Parallel Random Access Machine\|EREW PRAM]] vor<ref name=":2">{{Literatur \|Autor=Weixiong Zhang, Nageswara S. V. Rao \|Titel=Optimal parallel quicksort on EREW PRAM \|Sammelwerk=BIT \|Band=31 \|Nummer=1 \|Datum=1991-03 \|ISSN=0006-3835 \|Seiten=69–74 \|DOI=10.1007/bf01952784}}</ref>. Der Algorithmus sortiert <math>n</math> Elemente mit <math>p</math> Prozessoren in <math>O((n/p)+\log p ) \log n )</math> erwartete Laufzeit und in <math>O((n/p + \log p + \log \log n) \log n)</math> deterministische Laufzeit mit <math>O(n)</math> an Speicherbedarf. In dem Fall, dass <math>p = O(n/ \log n)</math> ist, dann sind die Kosten optimal in Bezug auf das Produkt von der Zeit und Anzahl von Prozessoren.

	=== Arbeitsweise ===		=== Arbeitsweise ===
Zeile 85:		Zeile 86:
	Die Laufzeit von dem Algorithmus hängt von der Wahl des Pivotelements. Eine Möglichkeit ist, ein zufälliges Element als Pivot zu nehmen.		Die Laufzeit von dem Algorithmus hängt von der Wahl des Pivotelements. Eine Möglichkeit ist, ein zufälliges Element als Pivot zu nehmen.

	Annehmend, kann ein Prozessor eine zufällige ganze Zahl <math>k</math> von dem Bereich <math>\{1,2,.., n\}</math> in konstante Zeit generieren, dann entspricht die Partitionierung mit Pivotelement – das Element mit Index <math>k</math>, einem Random [[Binäre Suche\|Binary Search]]. Die Analyse<ref>{{Literatur \|Autor=Luc Devroye \|Titel=A note on the height of binary search trees \|Sammelwerk=Journal of the ACM \|Band=33 \|Nummer=3 \|Datum=1986-05-01 \|ISSN=0004-5411 ~~\|DOI=10.1145/5925.5930~~ \|Seiten=489–498 \|~~Online~~=~~http://dx.doi.org/~~10.1145/5925.5930 ~~\|Abruf=2020-02-15~~}}</ref> besagt, dass für die Höhe, <math>H_n</math>, von einem [[:en:Random binary tree\|Random-Binary-Search-Tree]] mit <math>n</math> Elementen, gilt <math> \lim_{n \to \infty} (H_n \ln n) = 4.31107... </math>. Daher liegt die Tiefe der Rekursion bei <math>O( \log n)</math>. Das Pivotelement muss zusätzlich noch verschickt werden. Dies erfolgt in <math>O( \log p )</math><ref>{{Literatur \|Autor=Vishkin, U. \|Titel=Synchronous parallel computation - a survey. \|Verlag=Courant Institute of Mathematical Sciences, New York University \|Datum=1983-04 \|Online=http://worldcat.org/oclc/1085604497 \|Abruf=2020-02-15}}</ref>. Jeder Prozessor muss dann die Elemente in seinem Block markieren, die Präfix Summe muss berechnet werden<ref>{{Literatur \|Autor=Richard Cole, Uzi Vishkin \|Titel=Approximate and exact parallel scheduling with applications to list, tree and graph problems \|Sammelwerk=27th Annual Symposium on Foundations of Computer Science (sfcs 1986) \|Verlag=IEEE \|Datum=1986~~-10~~ \|ISBN=0-8186-0740-8 \|DOI=10.1109/sfcs.1986.10 ~~\|Online=http://dx.doi.org/10.1109/sfcs.1986.10 \|Abruf=2020-02-15~~}}</ref> und die Elemente verschoben werden. Dies braucht gesamt <math>O(n/p + \log p)</math>. Anschließend berechnet man die Gesamtlaufzeit für diesen Fall, diese ist <math>O((n/p)+\log p ) \log n )</math> erwartet.		Annehmend, kann ein Prozessor eine zufällige ganze Zahl <math>k</math> von dem Bereich <math>\{1,2,.., n\}</math> in konstante Zeit generieren, dann entspricht die Partitionierung mit Pivotelement – das Element mit Index <math>k</math>, einem Random [[Binäre Suche\|Binary Search]]. Die Analyse<ref>{{Literatur \|Autor=Luc Devroye \|Titel=A note on the height of binary search trees \|Sammelwerk=Journal of the ACM \|Band=33 \|Nummer=3 \|Datum=1986-05-01 \|ISSN=0004-5411 \|Seiten=489–498 \|DOI=10.1145/5925.5930}}</ref> besagt, dass für die Höhe, <math>H_n</math>, von einem [[:en:Random binary tree\|Random-Binary-Search-Tree]] mit <math>n</math> Elementen, gilt <math> \lim_{n \to \infty} (H_n \ln n) = 4.31107... </math>. Daher liegt die Tiefe der Rekursion bei <math>O( \log n)</math>. Das Pivotelement muss zusätzlich noch verschickt werden. Dies erfolgt in <math>O( \log p )</math><ref>{{Literatur \|Autor=Vishkin, U. \|Titel=Synchronous parallel computation - a survey. \|Verlag=Courant Institute of Mathematical Sciences, New York University \|Datum=1983-04 \|Online=http://worldcat.org/oclc/1085604497 \|Abruf=2020-02-15}}</ref>. Jeder Prozessor muss dann die Elemente in seinem Block markieren, die Präfix Summe muss berechnet werden<ref>{{Literatur \|Autor=Richard Cole, Uzi Vishkin \|Titel=Approximate and exact parallel scheduling with applications to list, tree and graph problems \|Sammelwerk=27th Annual Symposium on Foundations of Computer Science (sfcs 1986) \|Verlag=IEEE \|Datum=1986 \|ISBN=0-8186-0740-8 \|DOI=10.1109/sfcs.1986.10}}</ref> und die Elemente verschoben werden. Dies braucht gesamt <math>O(n/p + \log p)</math>. Anschließend berechnet man die Gesamtlaufzeit für diesen Fall, diese ist <math>O((n/p)+\log p ) \log n )</math> erwartet.

	In dem Fall, dass das Pivotelement nicht zufällig gewählt wurde, hängt die Laufzeit des Algorithmus von der Rekursionstiefe und damit auch von dem Verhältnis der Größen <math>S_1</math> und <math>S_2</math> ab. Die Rekursionstiefe vom Algorithmus kann auf <math>O( \log n )</math> begrenzt werden, wenn <math>S_1</math> und <math>S_2</math> ungefähr gleich sind. Dies kann gewährleistet werden, indem die Auswahl des Pivotelements mit dem Parallel Median Finding Algorithm von Akl auf eine EREW PRAM in <math>O(\log \log n)</math> Zeit<ref>Akl, S. G. "Parallel Selection in O(log log n) Time Using O(n/log log n) Processors." ''Technical Report 88-221, Department of Computing and Information Science, Queen's University, Kingston, Ontario'' (1988).</ref> erfolgt. Das Markieren, die Präfix Summe und das Verschieben der Elemente erfolgt analog zu dem anderen Fall. Mit dem [[Brent-Verfahren]] kann folglich der Algorithmus in <math>O((n/p + \log p + \log \log n) \log n)</math> deterministisch implementiert werden.		In dem Fall, dass das Pivotelement nicht zufällig gewählt wurde, hängt die Laufzeit des Algorithmus von der Rekursionstiefe und damit auch von dem Verhältnis der Größen <math>S_1</math> und <math>S_2</math> ab. Die Rekursionstiefe vom Algorithmus kann auf <math>O( \log n )</math> begrenzt werden, wenn <math>S_1</math> und <math>S_2</math> ungefähr gleich sind. Dies kann gewährleistet werden, indem die Auswahl des Pivotelements mit dem Parallel Median Finding Algorithm von Akl auf eine EREW PRAM in <math>O(\log \log n)</math> Zeit<ref>Akl, S. G. "Parallel Selection in O(log log n) Time Using O(n/log log n) Processors." ''Technical Report 88-221, Department of Computing and Information Science, Queen's University, Kingston, Ontario'' (1988).</ref> erfolgt. Das Markieren, die Präfix Summe und das Verschieben der Elemente erfolgt analog zu dem anderen Fall. Mit dem [[Brent-Verfahren]] kann folglich der Algorithmus in <math>O((n/p + \log p + \log \log n) \log n)</math> deterministisch implementiert werden.
Zeile 93:		Zeile 94:

	=== Arbeitsweise ===		=== Arbeitsweise ===
	Zuerst kommt die Wahl des Pivotelements. Dieses ist der Median von mehrere Elementen aus dem Array. Die Partitionierungsphase fängt mit der Aufteilung der Elemente in kleineren Gruppen oder Chunks an. Dann bekommt jeder Thread zwei Chunks zur Verarbeitung. Wenn es weniger Chunks gibt, sodass diese Bedienung erfüllt werden kann, werden weniger Threads, als erwünscht, benutzt. Jeder Thread sortiert seine Elemente, sodass in dem linken Chunk nur Elemente kleiner als das Pivotelement liegen und bzw. nur größere in dem rechten. Dann reserviert parallel jeder Thread Platz für seine zwei Chunks. Die linke Chunks von jedem Thread kommen am Anfang vom Array und die rechte Chunks am Ende. Damit ist die Partitionierung fertig.		Zuerst kommt die Wahl des Pivotelements. Dieses ist der Median von mehrere Elementen aus dem Array. Die Partitionierungsphase fängt mit der Aufteilung der Elemente in kleineren Gruppen oder Chunks an. Dann bekommt jeder Thread zwei Chunks zur Verarbeitung. Wenn es weniger Chunks gibt, sodass diese Bedienung erfüllt werden kann, werden weniger Threads, als erwünscht, benutzt. Jeder Thread sortiert seine Elemente, sodass in dem linken Chunk nur Elemente kleiner als das Pivotelement liegen und bzw. nur größere in dem rechten. Dann reserviert parallel jeder Thread Platz für seine zwei Chunks. Die linke Chunks von jedem Thread kommen am Anfang vom Array und die rechte Chunks am Ende. Damit ist die Partitionierung fertig.

	=== Balancierte Lastverteilung ===		=== Balancierte Lastverteilung ===

Südseeküste: link

2020-02-25T19:10:24Z

link

← Nächstältere Version		Version vom 25. Februar 2020, 21:10 Uhr
Zeile 1:		Zeile 1:
	{{QS-Antrag\|25. Februar 2020\|2=''Wikifizieren'' [[Benutzer:Lutheraner\|Lutheraner]] ([[Benutzer Diskussion:Lutheraner\|Diskussion]]) 16:33, 25. Feb. 2020 (CET)}}		{{QS-Antrag\|25. Februar 2020\|2=''Wikifizieren'' [[Benutzer:Lutheraner\|Lutheraner]] ([[Benutzer Diskussion:Lutheraner\|Diskussion]]) 16:33, 25. Feb. 2020 (CET)}}
	'''Parallel Quicksort''' beschreibt Parallelisierungen des sequentiellen Algorithmus [[Quicksort]], welcher auf dem Teile-und-Herrsche-Prinzip basiert.		'''Parallel Quicksort''' beschreibt Parallelisierungen des sequentiellen Algorithmus [[Quicksort]], welcher auf dem [[Teile-und-herrsche-Verfahren\|Teile-und-Herrsche-Prinzip]] basiert.

	Wie Quicksort teilt Parallel Quicksort eine Menge von Elementen mithilfe eines Pivotelements in zwei Teilmengen auf, sodass die Elemente in der einen Teilmenge kleiner als das Pivot sind und die Elemente in der anderen Teilmenge größer oder gleich dem Pivot sind. Danach werden die neuen Mengen wieder jeweils in Teilmengen unterteilt.		Wie Quicksort teilt Parallel Quicksort eine Menge von Elementen mithilfe eines Pivotelements in zwei Teilmengen auf, sodass die Elemente in der einen Teilmenge kleiner als das Pivot sind und die Elemente in der anderen Teilmenge größer oder gleich dem Pivot sind. Danach werden die neuen Mengen wieder jeweils in Teilmengen unterteilt.