1

GraphalgorithmenSeminar parallele Programmierung SS 2003

Bernd Kruthoff und Jochen Olejnik

2

Gliederung

1. Motivation

2. Verbundene Komponenten

- Hirschbergs Algorithmus

3. Minimal Spannender Baum

- Kruskals Algorithmus

- Sollins Algorithmus

4. Kürzeste Pfade von einem Knoten ausgehend

- Moores Algorithmus

5. Zusammenfassung

3

1. Motivation

• Probleme der Praxis werden komplexer

• Lassen sich häufig durch Graphen darstellen

• Herkömmliche Algorithmen stoßen an Grenzen

• Lösung: Parallelisierung bekannter Algorithmen

4

3 mögliche Ansätze:

A. Suchalgorithmen• durch Breiten- bzw. Tiefensuche durch den kompletten Graphen

Verbundene Komponenten

• Finden aller verbundenen Komponenten in einem ungerichteten Graphen

5

Verbundene Komponenten

B. Transitive Hülle• Grundlage: Adjazenzmatrix• Bestimmen der transitiven Hülle durch Plus-Min-

Multiplikationen

• Plus-Min-Multiplikation ist Matrixmultiplikation bei der Skalamultiplikationen durch Additionen und Additionen durch Minimumoperationen ersetzt werden

• => Strukturanalogie zur Matrixmultiplikation:• => Laufzeit: für eine Plus-Min-Multiplikation

nlog

nlog

• => für log n Plus-Min-Multiplikationen n2log

6

C. Hirschbergs Algorithmus• Grundidee: Knoten zu Knotengruppen zusammenfassen bis kein

weiteres Zusammenfassen mehr möglich ist• Jeder Knoten gehört zu genau einer Knotengruppe• Knotengruppen werden durch Wurzel (hier: kleinstes Element)

identifiziertDer Algorithmus:1. Schritt: Zu jedem Knoten wird die angrenzenden Knotengruppe

mit der kleinsten Wurzel gesucht2. Schritt: Verbinden der Wurzeln der in Schritt 1 gefundenen

Knotengruppen3. Schritt: Die in Schritt 2 gefundenen Knotengruppen werden zu

einer Knotengruppe zusammengefasst• Endet, wenn es in Schritt 1 keine angrenzende Knotengruppe mehr

gibt

7

Ein Beispiel:

1

5

1110

6

2

387

94

Knoten 1 2 3 4 5 6 7 8 9 10 11Knoten-gruppe

1 2 3 4 5 6 7 8 9 10 11

Die Ausgangssituation:

8

Beispiel: 1. Iteration

1. Schritt: Zu jedem Knoten wird die angrenzende Knotengruppe mit der kleinsten Wurzel gesucht

1

5

1110

6

2

387

94

1

5

1110

6

2

387

94

9

Beispiel: 1. Iteration

2. Schritt: Verbinden der Wurzeln der in Schritt 1 gefundenen Knotengruppen

1

5

1110

6

2

387

94

10

Beispiel: 1. Iteration1

5

1110

6

2

387

94

1

5

1110

6

2

387

94

3. Schritt: Die in Schritt 2 gefundenen Knotengruppen werden zu einer Knotengruppe zusammengefasst

11

Beispiel: 1. Iteration Ergebnis

1

5

1110

6

2

387

94

Knoten 1 2 3 4 5 6 7 8 9 10 11

Knoten-gruppe

1 2 2 1 5 2 1 2 2 5 5

12

Beispiel: 2. Iteration

1. Schritt: Zu jedem Knoten wird die angrenzenden Knotengruppe mit kleinster Wurzel gesucht

1

5

1110

6

2

387

94

1

5

1110

6

2

387

94

1

5

1110

6

2

387

94

Letzte Iteration:

Startgraph:

13

Beispiel: 2. Iteration

2. Schritt: Verbinden der Wurzeln der in Schritt 1 gefundenen Knotengruppen

1

5

1110

6

2

387

94

1

5

1110

6

2

387

94

14

Beispiel: 2. Iteration

3. Schritt: Die in Schritt 2 gefundenen Knotengruppen werden zu einer Knotengruppe zusammengefasst

1

5

1110

6

2

387

94

1

5

1110

6

2

387

94

15

Beispiel: 2. Iteration Ergebnis

1

5

1110

6

2

387

94

Knoten 1 2 3 4 5 6 7 8 9 10 11

Knoten-gruppe

1 1 1 1 5 1 1 1 1 5 5

16

Komplexität• Der Algorithmus benötigt Iterationen weil sich die Anzahl

der Knotengruppen mit jeder Iteration mindestens halbiert

• Es werden n2 Prozessoren benötigt, weil maximal n benachbarte Knotengruppen pro Knoten verglichen werden müssen.

• => Gesamtkomplexität

nlog

n2log

17

Verbesserungen

• Betrachten von Brents Theorem:• Es reichen Prozessoren aus um n Elemente anzusprechen

und deren Minimum in Zeit zu finden.• Jeder Prozessor kann log n Elemente anstatt nur einem ansprechen

oder das Minimum aus log n Elementen berechnen, anstatt nur das Minimum aus zwei Elementen ohne die Zeitkomplexität zu verändern.

• Der Algorithmus benötigt also Zeit bei Prozessoren.

nlog nlog

n2log nnn log

18

Eine Implementierung• Implementierung von Hirschbergs Algorithmus auf das 2D

Mesh SIMD Rechnermodell (Nassimi, Sahni)• 3 neue Befehle:• random.read(a,[b]c) liest den Wert der Variablen c im Bereich

von Prozess b in die Variable a ein • random.write(a,[b]c) schreibt den Wert der Variablen a in die

Variable c im Bereich von Prozess b • Laufzeit dieser Operationen ist nur vom Rechner abhängig =>

konstant in Bezug auf die Anzahl der Elemente• bits(i,j,k) gibt den Wert der Stellen j bis k der Zahl i zurück• z. B. bits (9,3,2) : 9 ist binär 0101 zweite und dritte Stelle: 01

also wird 1 zurückgegeben• Ist j<k wird 0 zurückgegeben

19

p u b l i c V E R B U N D E N E K O M P O N E N T E N ( ) : P a r a m e t e r : d / / m a x i m a l e r K n o t e n g r a d n / / A n z a h l K n o t e n = A n z a h l P r o z e s s o r e n G l o b a l e V a r i a b l e n : k / / b e t r a c h t e t e K a n t e i t e r a t i o n / / N u m m e r d e r I t e r a t i o n L o k a l e V a r i a b l e n : k a n d i d a t / / W u r z e l d e s N a c h b a r k n o t e n s n a c h b a r [ 1 . . . d ] / / N a c h b a r k n o t e n d e r a k t u e l l e n K n o t e n g r u p p e w / / W u r z e l 1 . b e g i n 2 . f o r ( a l l e P i w h e r e ) { 3 . w = i ; j e d e r K n o t e n w i r d W u r z e l 4 . } 5 . f o r ( i t e r a t i o n = 0 t o ) { 6 . f o r ( a l l e P i w h e r e ) { e s g i b t k e i n e b e k a n n t e n N a c h b a r n 7 . k a n d i d a t = ; = > E n t f e r n u n g z u N a c h b a r n w i r d a u f 8 . } g e s e t z t 9 . f o r ( k = 1 t o d ) { 1 0 . f o r ( a l l e P i w h e r e ) { S u c h e n d e s N a c h - 1 1 . H O L E N . U N D . V E R G L E I C H E N ( n a c h b a r [ k ] , w , k a n d i d a t ) ; b a r k n o t e n s m i t 1 2 . } d e r k l e i n s t e n 1 3 . } W u r z e l 1 4 . f o r ( a l l e P i w h e r e ) { 1 5 . A K T U A L I S I E R E . W U R Z E L ( k a n d i d a t , w ) ; 1 6 . } 1 7 . Z U S A M M E N F A S S E N ( w , n ) ; / / Z u s a m m e n f ü g e n d e r K n o t e n g r u p p e n 1 8 . } 1 9 . e n d

ni 1

ni 1

1log n

ni 1

ni 1

20

private HOLEN.UND.VERGLEICHEN(v, w, kandidat); //entspricht 1. Schritt übergebene Werte: v //Nachbarknoten w, kandidat lokale Variablen: tmp //Wurzel des Nachbarknotens 20. begin 21. random.read(tmp, [v]w); 22. if (tmp==w){ 23. tmp=; Prüfen, ob v schon kandidat als Wurzel 24. } hat 25. kandidat=min(kandidat, tmp); 26. end

private AKTUALISIERE.WURZEL(kandidat, w); //entspricht 2. Schritt übergebene Werte: kandidat, w 27. begin 28. random.write(kandidat[w]w); 29. if (w==){ hat diese Knotengruppe überhaupt 30. w=i; Nachbarn? 31. } 32. if (w>i){ 33. random.read(w, [w]w); gibt es einen Zyklus? 34. } 35. end

21

private ZUSAMMENFASSEN(w, n); //entspricht 3. Schritt übergebene Werte: w, n 36. begin 37. for (b=1 to log(n)){ 38. for (alle Pi){ 39. if (bits(w, log(n)-1, b)==bits(i, log(n), b)){ 40. random.read(w, [w]w); 41. } 42. } 43. } 44. end

22

Laufzeit dieser Implementierung

23

1 . b e g i n 2 . f o r ( a l l e P i w h e r e ) { 3 . w = i ; j e d e r K n o t e n w i r d W u r z e l 4 . } 5 . f o r ( i t e r a t i o n = 0 t o ) { 6 . f o r ( a l l e P i w h e r e ) { e s g i b t k e i n e b e k a n n t e n N a c h b a r n 7 . k a n d i d a t = ; = > E n t f e r n u n g z u N a c h b a r n w i r d a u f 8 . } g e s e t z t 9 . f o r ( k = 1 t o d ) { 1 0 . f o r ( a l l e P i w h e r e ) { S u c h e n d e s N a c h - 1 1 . H O L E N . U N D . V E R G L E I C H E N ( n a c h b a r [ k ] , w , k a n d i d a t ) ; b a r k n o t e n s m i t 1 2 . } d e r k l e i n s t e n 1 3 . } W u r z e l 1 4 . f o r ( a l l e P i w h e r e ) { 1 5 . A K T U A L I S I E R E . W U R Z E L ( k a n d i d a t , w ) ; 1 6 . } 1 7 . Z U S A M M E N F A S S E N ( w , n ) ; / / Z u s a m m e n f ü g e n d e r K n o t e n g r u p p e n 1 8 . } 1 9 . e n d

ni 1

ni 1

1log n

ni 1

ni 1

• Loop (Zeilen 5-18) wird log n mal durchlaufen

• In innerem Loop (Zeilen 9-13) wird d mal die Minimumoperation angewendet, welche O(n) Zeit verbraucht

24

Laufzeit dieser Implementierung

• Loop (Zeilen 5-18) wird log n mal durchlaufen

• In innerem Loop (Zeilen 9-13) wird d mal die Minimumoperation angewendet, welche O(n) Zeit verbraucht

Auf dem 2D mesh-SIMD-Rechner mit n Prozessoren und n=2k Knoten und Maximalwert d hat dieser Algorithmus eine Komplexität von .)log( ndnO

25

Minimal Spannender Baum

• Kruskals Algorithmus• Idee: Alle Knoten sind anfangs Bäume

• Pro Iteration wird nun die kleinste noch nicht im Minimal Spannenden Baum vorhandene Kante eingefügt, falls dadurch kein Zyklus entstünde

• Finden des Minimal Spannenden Baumes in einem ungerichteten verbundenen gewichteten Graphen

26

Beispiel Kruskals Algorithmus

6

5

18

2

4

7

3

4

2

A

GF

E

DB

C

6

5

18

2

4

7

3

4

2

A

GF

E

DB

C

6

5

18

2

4

7

3

4

2

A

GF

E

DB

C

6

5

18

2

4

7

3

4

2

A

GF

E

DB

C

27

Beispiel Kruskals Algorithmus

6

5

18

2

4

7

3

4

2

A

GF

E

DB

C

6

5

18

2

4

7

3

4

2

A

GF

E

DB

C

6

5

18

2

4

7

3

4

2

A

GF

E

DB

C

28

Der Heap als Datenstruktur

• Parallelisierung durch geschickte Wahl der Datenstruktur

• Hier bietet sich der Heap an! => Gute Laufzeiteigenschaften

• Hier wird der Heap mit -wertigen Knoten zu einem vollständigen Binärbaum ausgebaut

• Lemma: Man kann mit einer UMA-Multiprozessormaschine mit log nProzessoren ein Element aus einer n-elementigen Menge in konstanter Zeit aus dem Heap auslesen.

29

Der Heap als Datenstruktur

• Jede Ebene hat Flag mit Wert => voll wenn alle Knoten belegt => leer wenn es leere Knoten in Ebene gibt

• Wert empty_node zeigt pro Ebene Knoten, in dem Wert fehlt

• Jeder Prozessor ist für eine Ebene zuständig. Wird ein Knoten leer so füllt ihn der zuständige Prozessor aus dem kleinsten Element der Kinder dieses Knotens wieder auf

• Wird ein Blatt leer, so wird der Wert eingetragen

• Heapaufbau kann durch Prescheduling parallelisiert werden

30

15

7

32

4

8 9 10 11 12 12 14

5

30273025

1821

7

5

1

6

Ein Beispielheap

E Heap F EN

1 Voll kein

2 Leer 2

3 Leer 6

4 Voll kein

31

Der Gesamtalgorithmus• Aufbauen des Heap

• Prozess entnimmt fortlaufend Knoten aus dem Heap und überprüft, ob sie zum Minimal Spannenden Baum gehören

• Die restlichen Prozesse stellen währenddessen den Heap wieder her

• Terminiert, wenn ausgelesen wird

• Laufzeit: Wiederaufbau des Heap und Überprüfung auf Zyklus (Find und Union) geschieht in konstanter Zeit

• Entnahme der Knoten in konstanter Zeit möglich

• =>Gesamtalgorithmus benötigt O(n) Zeit

32

Wechsel....