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 2

Freie Verteilung von Runnables

Bei der freien Verteilung von Runnables werden alle Runnables in n Teilmengen aufgeteilt (jeweils eine pro Rechenkern), so dass die Summe ihrer "Worst Case“-Laufzeit in einem Zeitintervall in allen Teilmengen möglichst gleich groß ist. Weiterhin soll das Kommunikationsvolumen zwischen den Runnable-Gruppen minimiert werden, um den Mehraufwand durch Intercore-Kommunikation, durch Anlegen lokaler Kopien oder gegenseitigen Ausschluss beim Zugriff auf gemeinsamen Speicher, gering zu halten. Diese Fragestellung lässt sich als ein balanciertes "Graph Cut"-Problem (siehe z.B. [4]) darstellen, bei dem die Menge der Knoten eines Graphen so in Partitionen aufgeteilt wird, dass die Anzahl der Kanten (oder die Summe der Kantengewichte) zwischen den Teilmengen minimal und die Anzahl der Knoten (oder die Summe der Knotengewichte) möglichst ausgeglichen ist. Im hier beschriebenen Kontext bilden Runnables die Knoten, gewichtet mit ihrer "Worst Case"- Laufzeit in einem bestimmten Zeitintervall. Kanten zwischen den Knoten ergeben sich aus dem Datenfluss zwischen den Runnables. Zudem lassen sich Kanten entsprechend der Anzahl gemeinsamer Datenobjekte und der Zugriffshäufigkeit gewichten. Der linke Teil von Bild 2 visualisiert einen entsprechenden Graphen für ein einfaches Beispiel. Knoten repräsentieren Runnables der ursprünglichen Software. Die Runnables 1 bis 5 wurden im Einzelkern-System auf Task 1 abgebildet, 6 bis 9 auf Task 2. Dabei stellt die Knotengröße die Laufzeit in einem festgelegten Zeitintervall dar. Die Nummern der Knoten geben die ursprüngliche Ausführungsreihenfolge der Runnables an. Kanten repräsentieren den Datenfluss zwischen Runnables. Im rechten Teil des Bildes ist eine Aufteilung der Runnables auf zwei Rechenkerne entsprechend der Strategie „freie Verteilung von Runnables“ dargestellt, wobei die roten Kanten Intercore- Kommunikation repräsentieren.

Um eine Trennung von Runnables, die gleiche Zeiger verwenden, zu vermeiden, wurden die Kanten zwischen solchen Runnables sehr hoch gewichtet. In der hier beschriebenen Fallstudie kam zur Bestimmung einer Lösung des so beschriebenen Problems die "Open Source"-Bibliothek METIS (siehe [2]) zum Einsatz. In der ursprünglichen Software war durch die Ununterbrechbarkeit der Runnables sichergestellt, dass der Zugriff auf globale Variablen, auch in Unterfunktionen während ihrer Laufzeit, exklusiv gegeben bzw. deren Werte von außen nicht veränderlich waren. Bei der Umsetzung von "Legacy"-Programmierkonzepten auf AUTOSAR-Kommunikationsparadigmen wurde die Kommunikation zwischen Runnables auf unterschiedliche Rechenkerne über globale Variablen auf eine indirekte, ungepufferte Sender-Empfänger- Kommunikation abgebildet.

Die Laufzeitumgebung legt in diesem Fall vor Ausführung der Runnables lokale Kopien der gelesenen Werte an und schreibt die errechneten Werte nach der Ausführung in die Puffer der entsprechenden Empfänger. Damit ist sichergestellt, dass sich der Datenstand, auf dem ein Runnable arbeitet, sich während seiner Ausführung nicht ändert. Eine Herausforderung dabei ergab sich bei der Umsetzung durch die von Runnables aufgerufenen Funktionen, die auf globalen Variablen arbeiten. Solche Funktionen wurden automatisiert so modifiziert, dass sie nicht mehr direkt auf die globalen Variablen zugriffen, sondern stattdessen als zusätzliche Parameter Zeiger auf die lokalen Kopien der globalen Variablen übergeben bekamen.

Auf diese Weise ist sichergestellt, dass der Datenstand, auf dem ein Runnable arbeitet, – wie im nicht parallelisierten Fall – während seiner Ausführung von außen nicht verändert werden kann. Daten, die von Tasks mit höherer Priorität aktualisiert werden, sind wie im Einzelkern-Fall seit der letzten Aktivierung des höher priorisierten Tasks aktuell. Das Verhalten des Gesamtsystems kann sich durch die Verteilung jedoch dennoch ändern: In der ursprünglichen Software gab es durch die deterministische Ausführungsreihenfolge einen definierten Datenfluss zwischen den Runnables eines Tasks. Bei beliebiger Verteilung von Runnables gilt das nicht mehr. Grund hierfür ist, dass die Reihenfolge der Ausführung von Runnables auf unterschiedlichen Rechenkernen ohne zusätzliche Synchronisation nicht deterministisch ist.