Startseite > Automotive > Software + Tools > Load Balancing in AUTOSAR-Multicore-Systemen (Teil 2)

AUTOSAR

Load Balancing in AUTOSAR-Multicore-Systemen (Teil 2)

27. April 2010, 11:50 Uhr | Von Dr. Kathrin D. Scheidemann, Michael Knapp und Claus Stellwag

▶ Diesen Artikel anhören

Fortsetzung des Artikels von Teil 5

Parallelisierung in einer Barrier-Architektur

Durch den Datenfluss zwischen Runnables gleicher Priorität ist ohne weitere Synchronisation deren Verteilung (wie eben gesehen) stark eingeschränkt. Schon bei zwei Rechenkernen kann Rechenkern 1 nur um 13 % entlastet werden. Bei Verteilung der Runnables auf mehr als zwei Rechenkerne ist zu erwarten, dass die "Workload" zwischen den Rechenkernen noch unausgeglichener verteilt sein wird.

Eine Möglichkeit, eine besser ausgeglichene Verteilung zu erzielen, besteht darin, Runnables gleicher Priorität, zwischen denen Abhängigkeiten bestehen, nicht wie eben beschrieben gemeinsam zu platzieren, sondern die Tasks, in denen Runnables auf unterschiedlichen Rechenkernen ausgeführt werden, (wenn notwendig) zu synchronisieren. Dies lässt sich mit einer Barrier- Architektur erreichen. Dort gibt es für jeden ursprünglichen Task auf jedem Rechenkern entsprechende Tasks, auf die die Runnables des ursprünglichen Tasks verteilt werden. Wo notwendig, werden Synchronisationspunkte (Barriers, siehe z.B. [6]) eingefügt, an denen Tasks aufeinander warten. Die Verteilung der Runnables lässt sich so für jeden einzelnen Task separat optimieren. Ziel ist es, die Runnables eines bisherigen Tasks auf die n resultierenden und parallel ausgeführten Tasks so zu verteilen, dass die Laufzeit der Tasks minimal ist. Wenn Datenfluss zwischen Runnables auf unterschiedlichen Rechenkernen stattfindet, muss deren Ausführungsfolge durch Synchronsiationspunkte gesteuert werden. Bild 4 zeigt diese Verteilungsstrategie schematisch.

Um alle Garantien, die die Einzelkern- Architektur bietet, zu erhalten, wurde dafür gesorgt, dass einander entsprechende Tasks auf allen Rechenkernen gleichzeitig ausgeführt werden. Dies erfordert, dass am Anfang jedes Tasks ein Synchronisationspunkt eingefügt wird. Durch das kooperative "Scheduling" der Einzelkern-Architektur war die Unterbrechbarkeit von Tasks sichergestellt. Um diese auch im parallelen Fall zu erhalten, darf der zeitliche Abstand zwischen Synchronisationspunkten die maximale Laufzeit des rechenintensivsten Runnables des Tasks nicht überschreiten. Zusätzlich wird bei jedem Synchronisationspunkt der "Scheduler" aufgerufen, um das kooperative "Scheduling" abzubilden.

Die Minimierung der Intercore-Kommunikation ist bei dieser Verteilungsstrategie nicht direkt Ziel der Optimierung. Datenkonsistenz ist bereits durch die Architektur sichergestellt, weswegen auf Maßnahmen wie das Anlegen lokaler Kopien globaler Daten und den Schutz globaler Variablen durch "Spinlocks" verzichtet werden kann. Unter der Annahme, dass Zugriff auf gemeinsamen Speicher nicht wesentlich mehr Overhead verursacht als auf lokalen Speicher, ist es nicht relevant, auf wie viele und wie häufig einzelne Runnables auf globale Variablen zugreifen. Natürlich ist die Gültigkeit dieser Annahme stark von der Architektur der eingesetzten Hardware abhängig.

In der in Bild 4 dargestellten Verteilung ist das Volumen der Intercore-Kommunikation dementsprechend auch höher als beispielsweise in der Verteilung, die in Bild 3 dargestellt ist. Auch bei dieser Verteilungsstrategie lassen sich optimale Lösungen für hinreichend große Applikationen nicht effizient berechnen [5]. Die Verteilung lässt sich jedoch durch Heuristiken, durch Optimierungsverfahren wie "Simmulated Annealing" [4] oder auch mit "Linear Programming Solvern" [7] optimieren. Letzteres hat den Vorteil, dass neben der eigentlichen Lösung eine Aussage generiert werden kann, wie gut die Qualität einer gefunden Lösung ist, d.h., ob sie optimal ist bzw. wie viel Verbesserungspotential in einer längeren Optimierung liegt.