Next: Auswertung von zeitlichen Fib-Objekten
Up: Vorgehensweisen für Fib
Previous: Vorgehensweisen für Fib
Contents
Index
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 der Teilobjekte die gleichzeitig ausgewerte werden sollen, dies Anzahl kann beispielsweise mit der Anzahl Prozessorkerne übereinstimmen
- 1
- Ermittlung der Anzahl der benötigten Teilobjekte: Diese Zahl sollte ein Vielfaches der Anzahl der Prozesse sein. Wenn beispielsweise 4 Prozesse gleichzeitig laufen können und ein Multiplikator von 10 festgelegt wurde, sollte sein. In diesem Fall sollten also rund Teilobjekte gesucht werden, die ungefähr die gleiche Abarbeitungszeit haben.
- 2
- ist die Liste der Teilobjekte. Die Liste 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 aus , welches den größten Wert für die zur Auswertung benötigte Zeit hat
- 3.2
- ermittle das erste/ nächste Listenelement in ; wenn es kein erste/ nächste Listenelement in gibt, füge an das Ende von an und, wenn leer ist, gehe zu Schritt 4, sonst gehe zu Schritt 3.1
- 3.3
- ermittle alle Unterobjekte des Listenelements 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 an der Stelle an der vorher stand ein
- 3.4
- wenn die Anzahl der Teilobjekte in größer oder gleich ist gehe zu Schritt 4
- 3.5
- wenn die Anzahl der Teilobjekte in kleiner als ist gehe zu Schritt 3.1
- 4
- füge alle Elemente von an ihrer entsprechenden Stelle von ein
- 5
- Starten der Auswertung der ermittelten Teilobjekte ( wird auf gesetzt):
- 5.1
- Wenn leer ist gehe zu Schritt 6
- 5.2
- Wenn weniger als 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 aus
- 5.5
- Starte die Auswertung des Teilobjekt und sammle die Ergebnispunkte in der Liste
- 5.5
- erhöhe um
- 5.6
- gehe zu Schritt 5.1
- 6
- warten bis alle Teilobjekte fertig ausgewertet sind
- 7
- erstelle die Liste mit Ergebnispunkten
, wobei die Elemente der Liste in der Ergebnisliste hinter denen der Liste stehen
- 8
- zeige die Punkte in an
- 9
- Ende
Lösung ohne getTimeNeed():
- 0
- ermittle die Anzahl der Teilobjekte die gleichzeitig ausgewerte werden sollen, dies Anzahl kann beispielsweise mit der Anzahl Prozessorkerne übereinstimmen
- 1
- Ermittlung der Anzahl der benötigten Teilobjekte: Diese Zahl sollte ein Vielfaches der Anzahl der Prozesse sein. Wenn beispielsweise 4 Prozesse gleichzeitig laufen können und ein Multiplikator von 10 festgelegt wurde, sollte sein. In diesem Fall sollten also rund Teilobjekte gesucht werden.
- 2
- ist die Liste der Teilobjekte. Die Liste 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 aus
- 3.2
- ermittle das erste/ nächste Listenelement in ; wenn es kein erste/ nächste Listenelement in gibt, markiere ; wenn alle markiert sind gehe zu Schritt 4, sonst gehe zu Schritt 3.1
- 3.3
- ermittle alle Unterobjekte des Listenelements 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 Anzahl bisher eingefügte Teilobjekte in ein
- 3.4
- wenn die Anzahl der Teilobjekte in größer oder gleich ist gehe zu Schritt 4
- 3.5
- wenn die Anzahl der Teilobjekte in kleiner als ist gehe zu Schritt 3.1
- 4
- Starten der Auswertung der ermittelten Teilobjekte ( wird auf gesetzt):
- 4.1
- Wenn leer ist gehe zu Schritt 5
- 4.2
- Wenn weniger als 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 aus
- 4.5
- Starte die Auswertung des Teilobjekt und sammle die Ergebnispunkte in der Liste
- 4.5
- erhöhe um
- 4.6
- gehe zu Schritt 4.1
- 5
- warten bis alle Teilobjekte fertig ausgewertet sind
- 6
- erstelle die Liste mit Ergebnispunkten
, wobei die Elemente der Liste in der Ergebnisliste hinter denen der Liste stehen
- 7
- zeige die Punkte in an
- 8
- Ende
Next: Auswertung von zeitlichen Fib-Objekten
Up: Vorgehensweisen für Fib
Previous: Vorgehensweisen für Fib
Contents
Index
Betti Österholz
2013-02-13