Multithreading im Multiprocessing-Echtzeit-Betriebssystem

Energieeffizienz dank Multicore

Embedded-Software-Entwickler stehen heute Komplexitäten und Anforderungen gegenüber, die vor zehn Jahren noch unvorstellbar waren. Eine der häufigsten Herausforderungen stellt das Thema Energieeffizienz dar: Teams sollen Designs entwickeln, die Vorteile von Hardware- und Software-Power-Management-Funktionen nutzen und gleichzeitig hinsichtlich Funktionalität und Performance optimiert sind.

Trotz des Zielkonflikts zwischen Energieeffizienz und höherer Performance entstehen innerhalb von Embedded-Multicore-Systemdesigns Situationen, in denen sich Leistungsaufnahme und Performance ergänzen: Ein Symmetrisches Multiprocessing-Echtzeit-Betriebssystem (SMP-RTOS) lässt sich mit Multicore-Hardware und Power-Management-Funkionen verbinden, um parallele Embedded-Programmierung zu erleichtern. Obwohl die Power-Management-Funktionen eines vollständig ausgestatten RTOS wesentlich zu einem energieeffizienten Design beitragen, existieren Thread-Synchronisierungsmechanismen, die auf von der Hardware gelieferten Primitiven basieren und für Energieeinsparungen bei gleichzeitiger Verbesserung der System-Performance sorgen. Muliticore hat sich in der Embedded-Welt inzwischen etabliert: Nahezu alle großen Halbleiteranbieter liefern Multicore-Chips, z.B. ARM (Cortex A9), PowerPC (QorIQ), MIPS (1004K MT) und Intel (Atom). Höhere Performance ist aber nicht der einzige Faktor hinter diesem Trend. Embedded Systeme können sich keine Performancesteigerung auf Kosten eines höheren Leistungsbudgets oder Beeinträchtigung vorhandener Software leisten. Embedded-Halbleiteranbieter fokussieren sich deshalb auf eine kleine Anzahl von Kernen, in der Regel nicht mehr als acht.

Flexibel mit Multicore

Eine Embedded-Runtime-Softwarelösung mit Betriebssystem, Middleware und Endanwendungen, die auf Multicore-Plattformen abzielt, muss Performance, Leistungsbedarf und bestehende Softwaredesigns berücksichtigen. Obwohl Parallel-Computing ein ziemlich fortschrittliches Feld mit vielen verfügbaren Programmiersprachen, Architekturen und Computertechnologien ist, führt die parallele Embedded-Entwicklung aufgrund der Vielzahl von Hardware und involvierten Tools zu neuen Anforderungen, die hohe Flexibilität erfordern. Da es keinen allgemein akzeptierten Multicore-Programmierstandard gibt, verlassen sich die meisten Entwickler von Embedded-Anwendungen auf Thread-Level Parallelism (TLP), den das RTOS liefert. In der Theorie verspricht dieser Ansatz keine Veränderungen des bestehenden Codes, wenn die RTOS-Unterstützung für die Multicore-Architektur robust ist. Doch TLP ist immer mit Overhead verbunden. Dies liegt an der Erstellung und Terminierung von Worker-Threads sowie an der Synchronisation zwischen einzelnen Kontexten. Typische Embedded-Systeme besitzen jedoch eine begrenzte Anzahl von Threads. Aktiviert wird ein Software-Kontext üblicherweise als Ergebnis eines externen Ereignisses, z.B. eines Interrupts. Dieser Thread muss dann die Ausführung in der vorgeschriebenen Zeit abschließen. Basierend auf den Eigenschaften von Embedded-Runtime-Applikationen verringert die Verwendung wichtiger Preemption- und Prioritäts-Thread-Attribute in einem Echtzeit-Betriebssystem der TLP-Overhead. Die Grundidee ist es, Parent- und Child-Threads auf verschiedenen Ebenen zu priorisieren, damit keine Synchronisierungszeit erforderlich ist. In Situationen, in denen eine Synchronisation unvermeidlich ist, verwendet das vorgeschlagene Schema energiesparende Primitiven, die von der Hardware geliefert werden. Ein weiterer Ansatz zur Entwicklung von Lastausgleichsstrategien und neuen Echtzeit-Scheduling-Algorithmen besteht darin, maximale Auslastung von mehreren Ressourcen zu erlangen. Aber diese Schemata erfordern in der Anwendungslogik oder im Betriebssystem-Code oft signifikante Änderungen. Sie haben für ein praktikables System erhebliche Nachteile, da ein Großteil des vorhandenen, zertifizierten und robusten Codes entweder gefährdet oder unbrauchbar ist. Statt der Suche nach einer optimalen Scheduling-Technik oder raffinierten Compiler-Technologie, empfiehlt sich ein portables Schema, das den Anwendungscode nicht beeinflusst und nur Veränderungen der Wrapper-Funktion der RTOS-Schnittstelle enthält.

Systemmodell: Round Robin oder Priorisierung

Das als Beispiel gewählte Embedded-System besteht aus einer Multicore-Plattform mit M identischen bzw. homogenen Kernen. Der SMP-RTOS-Thread-Scheduler folgt dem traditionellen Ansatz eines primitiven Threading-Modells mit festen Prioritäten. Diese Art des Schedulings ist in den heute kommerziell verfügbaren RTOS am weitesten verbreitet. Ein solcher Ansatz sorgt dafür, dass der wichtigste Thread immer als erster abläuft. Jeder unterbrechbare Thread mit niedrigerer Priorität kann nur von einem Thread mit höherer Priorität angehalten werden. Daher ist für wichtige Threads eine indirekte Garantie für den Echtzeitbetrieb erhältlich. Threads mit gleicher Priorität werden nach dem Round-Robin-Verfahren ausgeführt. Eine einfache Multicore-Erweiterung dieses Modells nimmt den Thread mit der höchsten Priorität ’n‘ (0 < M-1) und versendet ihn an einen der 'n' verfügbaren freien Kerne. Will man so viel Legacy-Code wie möglich nutzen, geht der einfachste Weg zur Multicore-Entwicklung über TLP unter einem Parent-Child-Programmiermodell. Bei diesem Beispiel bleibt der Code unabhängig von parallelen Programmierkonstrukten. Das Parent-Child-Modell hat keinen Einfluss auf die Deadline-Anforderungen solange es TLP unter den Grenzwerten halten kann. Beispielsweise kann ein vorhandener Anwendungs-Thread (Parent), der Video-Frames dekodiert, die Ausführung mit Hilfe von TLP beschleunigen, wenn er Frames unter den Child-Threads aufteilt. Diese Child-Threads laufen parallel auf mehreren verfügbaren Kernen ab und erhöhen so unter Umständen die Performance des Systems. Dort gibt es nur sehr geringe Anforderungen für Codeänderungen. Ein 'Parent' muss verteilen und dann auf alle 'Children' warten, um eine Task abzuschließen. Wenn Thread-Erstellung (Fork) und Wartezeit (Join) im Vergleich zur Thread-Workload klein sind, lassen sich die Deadline-Anforderungen des Original-Threads leicht erfüllen. Fork- und Join-Services sind üblicherweise Wrapper, die andere Standard-RTOS-Schnittstellen umgeben.

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.