1 Paralleles Sortieren (bitones Sortieren, Hyperquicksort, Regular Sampling) von Ferdinand Davertzhofen und Michael Stolte

1

Paralleles Sortieren

(bitones Sortieren, Hyperquicksort, Regular Sampling)

von Ferdinand Davertzhofen und Michael Stolte

Ferdinand Davertzhofen

Schriftart:Times New Roman (Serifen!)Farben:nur Schwarz, Rot und Grün(Hyperlinks: blau)Schriftgrößen:44pt für Hauptüberschriften40pt für Seitenüberschriften24pt für Text20pt für kleinen Text

2

Gliederung

1. Bitones Sortieren1.1 Bitone Sequenzen1.2 Der Algorithmus von Batcher1.3 Hardwarespezifische Adaptionen

2. Quicksort basiertes Sortieren2.1 Sequenzieller Quicksort2.2 Paralleler Quicksort2.3 Hyperquicksort2.4 Regular Sampling

3. Zusammenfassung und Fazit

Teil 1

Teil 2

3

1

2

3

4

5

6

7

8

Tal

Gipfel

A

B

C

D

E

F

G

H

Gipfel

Tal

A

B

C

D

E

F

G

H

Gipfel 1

Tal 1

Gipfel 2

Tal 2

Definition:Eine bitone Sequenz ist eine Folge a1,a2,…,an von beliebigen Elementen, deren erster Teil a0,…,ai aufsteigend und zweiter Teil ai,…,an absteigend sortiert ist, oder sich die Elemente durch eine zyklische Verschiebung so anordnen lassen, dass obige Bedingung gilt.

Beispiele: 8, 5, 2, 1, 3, 4, 6, 7 oder C, B, A, E, H, G, F, D.

1.1 Bitone Sequenzen

4

Gliederung




Teil 1

Teil 2

5

• 1968 von Kenneth E. Batcher

• divide & conquer

• Input: unsortierte Liste von Elementenoder bitone Sequenz

• Sortieren durch „compare-exchange“-Prinzip:

Elementpaar

Komparator

Reihenfolge prüfen

ggf. Elemente austauschen

sortiertes Elementpaar

1.2 Der Algorithmus von Batcher

6

• 1968 von Kenneth E. Batcher


• Input: unsortierte Liste von Elementenoder bitone Sequenz

• Sortieren durch „compare-exchange“-Prinzip:

Elementpaar Komparatortypen:

Komparator

Reihenfolge prüfen

ggf. Elemente austauschen

sortiertes Elementpaar


+a

b

min{a,b}

max{a,b}

-a

b

max{a,b}

min{a,b}

7

Phase 1: (unsortierte Liste bitone Sequenz) [optional]

1. Unsortierte Liste der Länge n = Liste von n/2 bitonen Sequenzen der Länge 2

2. Sortieren von je 2 bitonen Sequenzen; eine aufsteigend, die benachbarte absteigend bitone Sequenz der Länge 4

3. Rekursiv für alle n/2 bitonen Sequenzen bis eine einzige bitone Sequenz der Länge n erreicht ist


H

G

F

E

D

C

B

A

H

G

F

E

D

C

B

A

H

G

F

E

D

C

B

A

H

G

F

E

D

C

B

A

Tal

Gipfel

8

Phase 2: (bitone Sequenz sortierte Liste)

Rekursives Aufteilen der bitonen Sequenz a0,a1,a2,…,an-2,an-1 in zwei bitone Sequenzen der Länge :

und

durch „compare-exchange“-Vorgänge.


2

n

),min(,),,min(),,min( 1.1110222

naaaaaa nnn

),max(,),,max(),,max( 1.1110222

naaaaaa nnn

H

G

F

E

D

C

B

A

Tal

H

G

F

E

D

C

B

A

Gipfel

H

G

F

E

D

C

B

A

H

G

F

E

D

C

B

A

9

Rekursionsschema des Algortihmus (Mischen von n Elementen):


BitonesMischenvon n/2

Elementen

BitonesMischenvon n/2

Elementen

+

+

+

+

a0

a1

an/2 - 2

an/2 - 1

an/2

an/2 + 1

an-2

an-1

10

C

D

B

H

E

G

F

A

C

D

H

B

G

E

A

F

C

H

B

D

G

A

F

E

C

D

+

E

G

-

F

A

+

B

H

-

C

H

+

D

B

+

G

A

-

E

F

-

C

B

+

H

D

+

G

F

-

A

E

-

B

C

D

H

G

F

E

A

B

G

+

C

F

+

D

E

+

H

A

+

B

G

C

F

D

E

A

H

Hier ist aus der Punktwolke die bitone Sequenz geworden.

B

D

+

C

A

+

G

E

+

F

H

+

B

D

A

C

E

G

F

H

B

A

+

D

C

+

E

F

+

G

H

+

E

A

B

C

D

E

F

G

H

Ablauf der Ausführung:


11

Komplexität (1): Ermittlung der benötigten Rekursionsebenen durch Induktion in 2 Schritten.

Sei g(k) die Anzahl der benötigten Ebenen für das Sortieren einer bitonen Sequenz mit n = 2k Elementen und gelte

g(1) = 1, g(2) = 2, …

So ist g(k) = 1 + g( k–1 ) = k

Sei h(k) die Anzahl der benötigten Ebenen für das Sortieren von n = 2k unsortierten Elementen und gelte

h(1) = 1, h(2) = 3, …

So ist h(k) = h( k-1 ) + g(k) =


2

)1( kk

12

Komplexität (1): Ermittlung der benötigten Rekursionsebenen durch Induktion in 2 Schritten.

Sei g(k) die Anzahl der benötigten Ebenen für das Sortieren einer bitonen Sequenz mit n = 2k Elementen und gelte

g(1) = 1, g(2) = 2, …

So ist g(k) = 1 + g( k–1 ) = k

Sei h(k) die Anzahl der benötigten Ebenen für das Sortieren von n = 2k unsortierten Elementen und gelte

h(1) = 1, h(2) = 3, …

So ist h(k) = h( k-1 ) + g(k) =


2

)1( kk

Am vorherigen Beispiel:

g(3) = 1+g(2) = 1 + 2 = 3

Am vorherigen Beispiel:

h(3) = h(2)+g(3) = 3 + 3 = 6

13

Komplexität (2):

Zu vernachlässigen: = 2k - 1 Vergleichsoperationen je Ebene

Da diese parallel ausgeführt werden.

Der zeitliche Aufwand bleibt bei

also Komplexität von Θ(log2n)


2

n

2

)1(loglog

2

)1(

nnkk

Kosten:

Θ(p log2n)

Kostenoptimalität:

auch bei n = p nicht gegeben. [da > Θ(n log n)]

14

Gliederung




Teil 1

Teil 2

15

Im Shuffle-Exchange Netzwerk (1)(1971 von Harold S. Stone)

Die Eigenschaften von Shuffle-Exchange Netzwerkenermöglichen es, identische Verbindungen zwischen einzelnen Prozessoren auf allen Rekursionsebenen zu nutzen.

Geringerer Platzbedarf + Geringere Komplexität = geringere Kosten für die Hardware

Unterschied zu Batcher:Nicht die Kommunikationsleitungen zwischen den Prozessoren können sich mit jedem Schritt ändern, sondern der eingesetzte Komparatortyp.

1.3 Hardwarespezifische Adaptionen

16

Im Shuffle-Exchange Netzwerk (1)(1971 von Harold S. Stone)

Die Eigenschaften von Shuffle-Exchange Netzwerkenermöglichen es, identische Verbindungen zwischen einzelnen Prozessoren auf allen Rekursionsebenen zu nutzen.

Geringerer Platzbedarf + Geringere Komplexität = geringere Kosten für die Hardware

Unterschied zu Batcher:Nicht die Kommunikationsleitungen zwischen den Prozessoren können sich mit jedem Schritt ändern, sondern der eingesetzte Komparatortyp.


17

Im Shuffle-Exchange Netzwerk (2)


C

D

B

H

E

G

F

A

C

D

H

B

G

E

A

F

C

G

D

E

H

A

B

F

C

D

+

E

G

-

F

A

+

B

H

-

C

G

D

E

H

A

B

F

C

H

+

G

A

-

D

B

+

E

F

-

C

H

G

A

B

D

F

E

C

B

+

H

D

+

G

F

-

A

E

-

B

C

D

H

G

F

E

A

B

G

+

C

F

+

D

E

+

H

A

+


B

G

C

F

D

E

A

H

B

D

+

G

E

+

C

A

+

F

H

+

B

D

E

G

A

C

F

H

B

A

+

D

C

+

E

F

+

G

H

+

A

B

C

D

E

F

G

H

18

Im Shuffle-Exchange Netzwerk (3)

Komplexität:

Anzahl Ebenen wie bei Batcher

(Vergleichsoperationen sind auch hier zu vernachlässigen)

Zusätzlich: „shuffle“-Schritte für Datenverschiebungen

„shuffle“-Schritte für die Bestimmung der Maskenvektoren

also auch hier Komplexität von Θ(log2n)und Kosten von Θ(p log2n) [= nicht kostenoptimal]


2

)1( kk

)1(loglog nn

1log2 n

19

Im 2-dimensionalen Gitternetzwerk (1)(1977 von C.D. Thompson und H.T. Kung)

„compare-exchange“

[ hier: „Zusammenbringen und Neuverteilen“ ]

Das Zusammenbringen von Elementen hat das Ziel, Elemente an dieselbe Position zu bringen, um diese dort vergleichen zu können. Danach werden die Elemente entsprechend des Vergleichsergebnisses neu verteilt.

Einsatz einer Indexfunktion zur effizienten Zuweisung von Listenelementen an das Gitternetzwerk


20

Im 2-dimensionalen Gitternetzwerk (2)


1

5

7

6

9

11

15

14

16

13

10

12

1

8

4

2

3

5

6

7

8

4

3

2

16

13

12

10

9

11

14

15

1

4

3

2

8

5

6

7

9

11

12

10

16

13

14

15

1

2

3

4

6

5

8

7

9

10

12

11

14

13

16

15

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

5

7

6

11

9

14

15

16

13

10

12

8

4

3

2

1

5

7

6

15

14

9

11

16

10

13

12

2

4

3

8

1

5

9

6

15

14

7

11

2

4

13

12

16

10

3

8

5

1

9

6

15

14

11

7

2

4

12

13

10

16

3

8

6

9

1

5

7

14

11

15

2

12

4

13

8

16

3

10

9

6

5

1

14

7

11

15

2

12

4

13

16

8

10

3


Phase 1 Phase 2 Phase 3 Phase 4

Zusammenbringen:

Es werden diejenigen Elemente mit einander verglichen, deren Index-Bitfolgen sich in dem am wenigsten signifikanten Bit unterscheiden.

Neuverteilen:

In welche Richtung die Bewegung beim Neuverteilen abläuft, gibt die Indexfunktion vor.

21

Im 2-dimensionalen Gitternetzwerk (3)

Komplexität:(ohne Herleitung)

Für Datenbewegungen:

Für Vergleichsoperationen:

Der erste Term dominiert, also betragen die Kosten

Da das Sortieren in 2-dimensionalen Gitternetzwerken einen Aufwand für Datenbewegungen von im günstigsten Fall benötigt, ist der Algorithmus für diese Architektur kostenoptimal. [ Im Allgemeinen Fall jedoch nicht! ]


)( N

)(log2 N

)( Np

)( N

22

Gliederung




Teil 1

Teil 2

23

• 1960 von C.A.R. Hoare


• Schnellster bekannter allgemeiner Sortieralgorithmus [ im günstigsten Fall sowie im Mittel Θ(n log n) ]

• Aufteilung der zu sortierenden Liste mittels eines Pivotelements

• Ein optimales Pivotelement wäre der Median der Liste

2.1 Sequenzieller Quicksort

A1 W A2

1Position l-1 l+1 n

24

Gliederung




Teil 1

Teil 2

25

• = „Naiver Ansatz“

• Trotz echtem Median als Pivotelement:1. Ebene: n-1Vergleiche von nur einem Prozessor2. Ebene: n-3 Vergleiche von nur 2 Prozessoren3. Ebene: n-7 Vergleiche von nur 4 Prozessoren

…

2.2 Paralleler Quicksort

Index-Stack

14 67

14 67

35 6714 34

Schritt 1: (Teil-)Liste holen

35

Schritt 2: Listezerlegen

Schritt 3: EineTeilliste

zurücklegen Schritt 4:Andere Teillisteerneut zerlegen

26

Timeout &

Spielerwechsel…

27

Gliederung




Teil 1

Teil 2

28

• B. A. Wager, 1987

• Gleichzeitige Nutzung aller Prozessoren von Beginn an Hyperquicksort

• Netzwerktopologie: Hypercube– 2d Prozessoren in einem Würfel der Dimension d– Kommunikationsverbindung zwischen

Prozessoren, die sich um ein Bit unterscheiden

2.3 Hyperquicksort

29

• Sortiereigenschaft in Multiprozessornetzwerk:

1. Jede lokale Folge eines Prozessors ist sortiert und2. Das letzte Element von Pi ist kleiner als das erste

Element von Pi+1.

• Generell: zwei Phasen– Phase 1: lokales Sortieren 1. Bedingung

erfüllt– Phase 2: Iteratives Vorgehen für immer kleinere

Teilfolgen

2.3 Hyperquicksort

30

1

7

5

3

0

6

4

2

2.3 HyperquicksortZerlegen eines d-dimensionale Hypercubes in zwei Hypercubes der Dimension d-1

1

7

5

3

0

6

4

2

d = 3 d = 2

31

Phase 2:

• Zunächst Betrachten des gesamten Hypercubes

• In jedem Iterationsschritt den Hypercube teilen und lokale Folgen sortieren,

– Sodass alle Elemente des unteren Hypercubes kleiner als sind als alle Elemente des oberen Hypercubes ist.

• Nach d Iterationen: 2d Hypercubes mit je einem Prozessor 2. Bedingung erfüllt

2.3 Hyperquicksort

32

2.3 Hyperquicksort

Beispiel: Zahlenfolge mit 32 Elementen in einem 2-Dimensionalen Hypercube

d = 2

1

3

0

2

33

30 5 17 12 1 25 22 14 8 19 10 27 2 24 16 20 7 13 32 31 4 23 21 3 29 26 28 6 9 11 15 18

30 5 17 12 1 25 22 14

29 26 28 6 9 11 15 187 13 32 31 4 23 21 3

8 19 10 27 2 24 16 200p

3p2p

1pSchritt 1

1 5 12 14 17 22 25 30

6 9 11 15 18 26 28 293 4 7 13 21 23 31 32

2 8 10 16 19 20 24 270p

3p2p

1pSchritt 2

2.3 Hyperquicksort1. Phase: Lokales Sortieren

34

2.3 Hyperquicksort2. Phase: Erste Iteration:

Schritt 2

1 5 12 14 17 3 4 7 13

19 20 24 27 18 26 28 2922 25 30 21 23 31 32

2 8 10 16 6 9 11 150p

3p2p

1p

1 3 4 5 7 12 13 14 17

18 19 20 24 26 27 28 2921 22 23 25 30 31 32

2 6 8 9 10 11 15 160p

3p2p

1p

Schritt 3

Dimension d-1 !

1 5 12 14 17 22 25 30

3 4 7 13 21 23 31 32

2 8 10 16 19 20 24 270p

3p2p

1p

6 9 11 15 18 26 28 29

Schritt 1

35

2.3 Hyperquicksort2. Phase: Zweite Iteration:

Schritt 2

1 3 4 5 7 2 6

30 31 32 26 27 28 2921 22 23 25 18 19 20 24

12 13 14 17 8 9 10 11 15 160p

3p2p

1p

Schritt 3

1 2 3 4 5 6 7

26 27 28 29 30 31 3218 19 20 21 22 23 24 25

8 9 10 11 12 13 14 15 16 170p

3p2p

1p

Dimension d-1 !

Schritt 1

1 3 4 5 7 12 13 14 17

18 19 20 24 26 27 28 2921 22 23 25 30 31 32

2 6 8 9 10 11 15 160p

3p2p

1p

36

Quicksort

2.3 Hyperquicksort

)log( pn

pn

)(log2 p

)(log pn

)( pnVersenden der Teilfolgen

Teilen der lokalen Folge

Versenden des Pivotelemente (Broadcast)

)( pnSortieren mittels Mischen

Aufwand:

37

Gesamtaufwand

2.3 Hyperquicksort

)log()(log)log( 2 pp pn

pn

pn

)log()log()log( 2 pnppn pn Kosten

Für ist der zweite Term ).log( nnnnp log

Für ist Hyperquicksort kostenoptimal.nnp log

38

Gliederung




Teil 1

Teil 2

39

• Li et Al., 1992

• Weitere Bezeichnungen:

– Sortieren durch Regular Sampling

– Sortieren durch Zerlegen des Wertebereichs

– Sample-Sort

• Vorgehen an einem konkreten Beispiel

2.4 Regular Sampling

40


2 3 7 8 12 16 20 24 26 1 6 9 10 15 13 14 17 27 4 5 11 18 19 21 22 23 25

Positionen: 1, (n/p2) +1, (2n/p2)+1, ..., (p-1)(n/p2)+1

8 18Pivotelemente:

1 2 4 8 10 17 18 20 22Sortierte regular

Samples: 2/)1(,...,2/2,2/ ppppppp

p1 p2 p3

12 7 3 20 8 16 24 2 26 1 13 6 17 15 10 14 9 27 4 21 11 22 23 19 25 18 5Aufteilen

2 3 7 8 12 16 20 24 26 1 6 9 10 15 13 14 17 27 4 5 11 18 19 21 22 23 25Lokales Sortieren

Regular Samples: 2 8 20 1 10 17 4 18 22

Ausgewählter Prozessor

41


2 3 7 8 12 16 20 24 26 1 6 9 10 15 13 14 17 27 4 5 11 18 19 21 22 23 25Teilen

2 3 7 8 1 6 4 5 12 16 9 10 15 13 14 17 11 18 20 24 26 27 19 21 22 23 25

Versenden der Teilfolgen

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27Lokales Sortieren

p1 p2 p3

42

Quicksort


)log( pn

pn

)( 2p

Sortieren der Teilfolgen durch Mischen

Auswahl und Broadcast der Pivotelemente

Sortieren der Samples

Versenden der Regular Samples

Versenden der Teilfolgen[Quinn]

)log()log( 222 pppp

)()(log log pp p

p

)log()log( 22 pnpppn

)log( ppn

Aufwand:

43

Gesamtaufwand


Für

Kosten

)loglogloglog( 2 pnpppn pn

pn

)loglogloglog( 3 ppnpnppnn

3pn ist der Algorithmus kostenoptimal,da erster Term dominiert !

44

Gliederung




Teil 1

Teil 2

45

3 Zusammenfassung und Fazit

• Bitones Sortieren unpraktikabel– „relativ“ schnell bis

• Hyperquicksort im Mittel schnell, hängt jedoch von geschickter Wahl des Pivotelements ab

– Kostenoptimal für Prozessoren

• Für Regular Sampling lässt sich der schlechteste Fall errechnen

– Kostenoptimal für bis Prozessoren

pn 2

3pn

nnp log

46

Noch Fragen ?

47

Feierabend

Für weitere Fragen sind wir unter

[email protected] (Ferdinand – 1. Teil)

und

[email protected] (Michael – 2. Teil)

zu erreichen.

mailto:[email protected]

mailto:[email protected]

48

Tippfehler Seminararbeiten:

Bei der Erstellung des Foliensatzes sind wir auf je zwei Tippfehler in unseren Seminararbeiten gestoßen.

Als Hilfe für die 5-Pkt. Kandidaten und um inhaltlichen Missverständnissen vorzubeugen haben wir daher die folgenden Folien angehängt, die auf die relevanten Stellen hinweisen.

49

Tippfehler Seminararbeiten (1):

Ferdinand:

50


Ferdinand:

51


Michael:

52


Michael:

Documents

1 Paralleles Sortieren (bitones Sortieren, Hyperquicksort, Regular Sampling) von Ferdinand Davertzhofen und Michael Stolte