Parallele Auswertung von Fib-Teilobjekten

Problem: Heutzutage sind Parallelrechner schon weit verbreitet. Um dies bei der Auswertung von Fib-Objekten auszunutzen, sind einige Anpassungen nötig.

Lösungskizze: Anstatt das gesamte Fib-Objekt mit in einem Proßess auszuwerten wird dieses in Teilobjekten aufgespalten und diese seperat ausgewertet. Dabei gibt es 2 Schritte: Ermittlung der Teilobjekte und Auswertung der ermittelten Teilobjekte.

Lösung mit getTimeNeed():

0

ermittle die Anzahl $A$ der Teilobjekte die gleichzeitig ausgewerte werden sollen, dies Anzahl $A$ kann beispielsweise mit der Anzahl Prozessorkerne übereinstimmen

1

Ermittlung der Anzahl $N$ der benötigten Teilobjekte: Diese Zahl sollte ein Vielfaches der Anzahl $A$ der Prozesse sein. Wenn beispielsweise 4 Prozesse gleichzeitig laufen können und ein Multiplikator von 10 festgelegt wurde, sollte $N=10*A=40$ sein. In diesem Fall sollten also rund $40$ Teilobjekte gesucht werden, die ungefähr die gleiche Abarbeitungszeit haben.

2

$T$ ist die Liste der Teilobjekte. Die Liste $T$ wird am Anfang mit dem obersten root-Element als Teilobjekt initialisiert. Zu jedem Teilobjekt gehört der Zeiger auf das definierende Unterobjekt, seine Nummer in der Ordnung der zusammenhängenden Teilobjekte (siehe Abschnitt 14.8 auf Seite ) und (ein Wert für) die zur Auswertung benötigte Zeit (ermittelt mit getTimeNeed() für das jeweilige Teilobjekt ).

3

Ermittlung der Teilobjekte:

3.1

nehme und entferne das Teilobjekt $T_m$ aus $T$, welches den größten Wert für die zur Auswertung benötigte Zeit hat

3.2

ermittle das erste/ nächste Listenelement $L$ in $T_m$; wenn es kein erste/ nächste Listenelement $L$ in $T_m$ gibt, füge $T_m$ an das Ende von $T_O$ an und, wenn $T$ leer ist, gehe zu Schritt 4, sonst gehe zu Schritt 3.1

3.3

ermittle alle Unterobjekte des Listenelements $L$ und füge jeweils für jedes ermittelte Unterobjekt das zusammenhängende Teilobjekt, das es definiert, und die Nummer des zusammenhängenden Teilobjekts in die Liste $T$ an der Stelle an der vorher $T_m$ stand ein

3.4

wenn die Anzahl der Teilobjekte in $T$ größer oder gleich $N$ ist gehe zu Schritt 4

3.5

wenn die Anzahl der Teilobjekte in $T$ kleiner als $N$ ist gehe zu Schritt 3.1

4

füge alle Elemente von $T_O$ an ihrer entsprechenden Stelle von $T$ ein

5

Starten der Auswertung der ermittelten Teilobjekte ($i$ wird auf $1$ gesetzt):

5.1

Wenn $T$ leer ist gehe zu Schritt 6

5.2

Wenn weniger als $A$ Teilobjekte zur Zeit ausgewertet werden, gehe Schritt 5.4

5.3

Warte kurz und gehe dann zu Schritt 5.2

5.4

nehme und entferne das erste Teilobjekt $T_1$ aus $T$

5.5

Starte die Auswertung des Teilobjekt $T_1$ und sammle die Ergebnispunkte in der Liste $LP_i$

5.5

erhöhe $i$ um $1$

5.6

gehe zu Schritt 5.1

6

warten bis alle Teilobjekte fertig ausgewertet sind

7

erstelle die Liste mit Ergebnispunkten $LP=\bigcup_{a=1}^{i-1} LP_a$ , wobei die Elemente der Liste $LP_{i+1}$ in der Ergebnisliste hinter denen der Liste $LP_i$ stehen

8

zeige die Punkte in $LP$ an

9

Ende

Lösung ohne getTimeNeed():

0

ermittle die Anzahl $A$ der Teilobjekte die gleichzeitig ausgewerte werden sollen, dies Anzahl $A$ kann beispielsweise mit der Anzahl Prozessorkerne übereinstimmen

1

Ermittlung der Anzahl $N$ der benötigten Teilobjekte: Diese Zahl sollte ein Vielfaches der Anzahl $A$ der Prozesse sein. Wenn beispielsweise 4 Prozesse gleichzeitig laufen können und ein Multiplikator von 10 festgelegt wurde, sollte $N=10*A=40$ sein. In diesem Fall sollten also rund $40$ Teilobjekte gesucht werden.

2

$T$ ist die Liste der Teilobjekte. Die Liste $T$ wird am Anfang mit dem obersten root-Element als Teilobjekt initialisiert. Zu jedem Teilobjekt gehört der Zeiger auf das definierende Unterobjekt und seine Nummer in der Ordnung der zusammenhängenden Teilobjekte (siehe Abschnitt 14.8 auf Seite ).

3

Ermittlung der Teilobjekte:

3.1

nehme und entferne das i'te Teilobjekt $T_i$ aus $T$

3.2

ermittle das erste/ nächste Listenelement $L$ in $T_i$; wenn es kein erste/ nächste Listenelement $L$ in $T_i$ gibt, markiere $T_i$; wenn alle $T_j$ markiert sind gehe zu Schritt 4, sonst gehe zu Schritt 3.1

3.3

ermittle alle Unterobjekte des Listenelements $L$ und füge jeweils für jedes ermittelte Unterobjekt das zusammenhängenden Teilobjekte, das es definiert, und die Nummer des zusammenhängenden Teilobjekts in ihrer Reihenfolge an den entsprechenden Stellen $(i +$Anzahl bisher eingefügte Teilobjekte$)$ in $T$ ein

3.4

wenn die Anzahl der Teilobjekte in $T$ größer oder gleich $N$ ist gehe zu Schritt 4

3.5

wenn die Anzahl der Teilobjekte in $T$ kleiner als $N$ ist gehe zu Schritt 3.1

4

Starten der Auswertung der ermittelten Teilobjekte ($i$ wird auf $1$ gesetzt):

4.1

Wenn $T$ leer ist gehe zu Schritt 5

4.2

Wenn weniger als $A$ Teilobjekte zur Zeit ausgewertet werden, gehe Schritt 4.4

4.3

Warte kurz und gehe dann zu Schritt 4.2

4.4

nehme und entferne das erste Teilobjekt $T_1$ aus $T$

4.5

Starte die Auswertung des Teilobjekt $T_1$ und sammle die Ergebnispunkte in der Liste $LP_i$

4.5

erhöhe $i$ um $1$

4.6

gehe zu Schritt 4.1

5

warten bis alle Teilobjekte fertig ausgewertet sind

6

erstelle die Liste mit Ergebnispunkten $LP=\bigcup_{a=1}^{i-1} LP_a$ , wobei die Elemente der Liste $LP_{i+1}$ in der Ergebnisliste hinter denen der Liste $LP_i$ stehen

7

zeige die Punkte in $LP$ an

8

Ende