Martin Wichner:
Abhängigkeitserkennung und parallele Ausführung von Code-Modulen im FUmanoid-Framework
Kurzbeschreibung
In dieser Arbeit wird eine Anpassung des Module-Frameworks der BerlinUnited-FUmanoids vorgestellt. Dabei wird als Erstes eine effizientere Berechnung der Abhängigkeiten der Module vorgestellt. Durch das Aufstellen eines Graphen, mit den Modulen als Knoten und den Abhängigkeiten zwischen den Modulen als Kanten, kann darauf eine Tiefensuche ausgeführt werden. Durch die Tiefensuche lassen sich zyklische Abhängigkeiten feststellen, welche dann mit Hilfe des Dijkstra-Algorithmus ausgegeben werden.
Im zweiten Teil der Anpassung wird das Framework dahingehend geändert, dass es möglich ist, mehrere Module parallel auszuführen. Durch eine Topologische Sortierung werden zur Laufzeit die Module ausgeführt, bei denen die Vorbedingungen erfüllt sind. Die Module, die ausgeführt werden können, werden dann nach dem FIFO-Prinzip ausgeführt. Eine Erweiterung der parallelen Ausführung ist, die Module nach dem Longest-Job-First-Prinzip auszuführen. Dabei werden die Laufzeiten der Module gespeichert und eine Durchschnittslaufzeit berechnet.
Am Ende werden die Ausführungszeiten der sequentiellen Ausführung, der parallelen Ausführung mit First-Come-First-Served und der parallelen Ausführung mit Longest-Job-First miteinander verglichen.