Fork-Join-Services im Low-Power-Mode
Um Fork-Services im POSIX-Stil zu unterstützen, ist ein gängiger Weg, rund um die Thread-Erzeugungs-API eine Wrapper-Funktion zur Verfügung zu stellen, die zusätzlich die Einrichtung einer Mailbox oder eines Ereignisses im Zusammenhang mit diesem Child-Thread enthält. Information von einem Ereignis (Mailbox) werden den Thread-Daten – wenn möglich in der Thread-Control-Box – hinzugefügt. Im Falle eines Join-Calls überprüft das RTOS den Mailbox-Status um festzustellen, ob das Child die Ausführung abgeschlossen hat. Diese simple Anordnung führt zu einem TLP-Synchronisierungs-Overhead, da sie von den Komponenten des RTOS und nicht vom Software-Kontext abhängt. Das in Abbildung 1 vorgeschlagene Schema zeigt die Knoten, die einen Thread – entweder Parent oder Child – darstellen, während die Verzweigungen den Fork-Join-Betrieb abbilden. Jeder Knoten wird durch eine Prioritätsstufe gekennzeichnet, mit Ausnahme des letzten Knoten E. Children haben in Beziehung zum Parent einen höheren Level. Jedes Child reagiert auf einen Join-Call vom Parent, um den Abschluss anzuzeigen. Die vorgeschlagenen RTOS-Fork-Join-Services umfasst bei jedem Systemaufruf die folgenden Schritte: Wenn ein Parent den Thread-Status überprüft und ein anderer Zustand als ‚Ende‘ angezeigt wird, existieren mehr parallele Ressourcen als die verbliebene Anzahl von Children. Andernfalls könnte der Parent nicht noch einmal ablaufen und Join aufrufen. So kann es einen Scheduler-Durchlauf dauern, bis andere Tasks ablaufen können. Für den Fall, dass Parent und Children die einzigen Lasten im System sind, kann der Kern, auf dem der Join-Call durchgeführt wurde, gefahrlos in einen Low-Power-Mode wechseln. Dies geschieht in dem Wissen, dass dieser Kern jetzt nichts mehr zu tun hat. Zu beachten ist, dass, obwohl Dynamic Voltage and Frequency Scaling (FVFS) schwierig zu erreichen ist, nahezu alle Anbieter Low-Power-CPU-Modi unterstützen. Das erhöht die Portabilität der vorgeschlagenen Lösung. Als Beispiel dient eine parallele Multithread-Anwendung, die aus acht Child-Threads auf einem Vier-Kern-System besteht. Abbildung 2 zeigt ein Ablaufdiagramm von RTOS-Fork-Join-Services, die diesen Anwendungsfall unterstützen. Jede Spalte stellt einen einzelnen Kern dar. Auf Kern null (C0) verteilt der Parent-Thread (Thread_Fork) nacheinander acht Child-Threads, ohne dass er die Kontrolle über den Prozessor verliert. Während der Parent-Thread die Child-Threads verteilt, sind im System drei Kerne frei. Auf diesen können die ersten drei Child-Threads ablaufen, ohne auf den Parent warten zu müssen. Das vierte Child muss ausharren, bis der Parent alle Threads erstellt hat. Dadurch wird gewährleistet, dass der Parent die Arbeit beim Erstellen der Child-Threads bei einem Kern verrichtet. Wenn ein Parent – auf irgendeinem freien Kern – wieder die Kontrolle hat, werden einige der Children bereits ihre Aufgabe abgeschlossen haben und Thread_Join erfordert nur die Statusprüfung einer ‚Flag‘ im Thread-Control-Block. Dies ist für Child null bis sechs der Fall, bei denen aufgrund der Prioritätenbeziehung zwischen Parent- und Child-Threads keine Synchronisation erforderlich ist. Da der letzte Thread, der zu Child hinzukommen soll, noch nicht fertig ist und Parent der Thread mit der niedrigsten Priorität ist, bedeutet das, dass das System nun leicht belastet ist. Deshalb wird der Kern auf dem der Parent läuft in einen Low-Power-Mode versetzt. Sobald Thread sieben beendet ist, weckt er diesen Kern mit Hilfe eines Hardware-unterstützten Ereignisses auf, was Synchronisationszwecken dient.
Zeitvergeudung für interne Betriebslogistik
Dieser Anwendungsfall lässt sich vergleichen mit seinem Gegenpart, der für die Thread-Synchronisation RTOS-Konstrukte wie Message-Passing oder Ereignisse nutzt. Als erstes ist zu beachten, dass – weil üblicherweise ein Child die Priorität seines Parent erbt – ein Parent in der Lage ist, alle Children zu erstellen. Child vier muss dann jedoch warten, bis der Parent Thread_Join gegen den ersten Child-Thread aufruft. Wenn der Parent diesen Aufruf unterbricht, weil die Abschluss-Message von Child vier noch nicht eingetroffen ist, dann kann Child vier auf dem vom Parent freigegebenen Kern ablaufen. Dies hängt natürlich von der Zeitdauer ab, die Child eins bis zum Abschluss benötigt. Das Resultat ist, dass die für die Berechnung erforderliche Zeit auf interne Betriebssystemlogik verschwendet wird und somit den Synchronisations-Overhead erhöht.
Overhead-Einsparungen von rund drei Prozent
Um die beschriebene Lösung zu verifizieren, wurde eine CPU-abhängige Skalarprodukt-Applikation entwickelt und auf einem ARM-Cortex-A9-MPCore mit vier identischen, mit 400MHz getakteten Kernen getestet. Als RTOS kam das Nucleus-RTOS von Mentor Graphics zum Einsatz, das mit Mentors Sourcery GNU-Tools für ARM EABI kompiliert wurde. Die Ergebnisse für die vorgeschlagenen und die Message-Passing (MP) basierten Fork-Join-Schemata sind in Abbildung 3 für Matrixgrößen von 2048, 4096 und 8192 zu sehen. Da der Overhead eine Funktion der Anzahl der Threads ist, wird jede Matrixgröße im Vergleich zu 2, 4, 8 und 16 Threads ausgewertet. Zu erkennen ist, dass in allen Fällen die beschriebene Technik zu einer niedrigeren Ausführungszeit mit durchschnittlichen Overhead-Einsparungen von rund drei Prozent führt. Zudem verspricht sie eine reduzierte Stromaufnahme. Da in einer hochparallelen Anwendung wie einem Skalarprodukt der Overhead ein Bruchteil der absoluten Ausführungszeit ist, sind die Einsparungen hier signifikant.
