Autor: Ralph Mader, Continental Automotive GmbH<\/p>\n
Pattern f\u00fcr das Design von parallel ausf\u00fchrbaren Algorithmen sind bislang noch nicht systematisch in Embedded Realzeit-Systeme vorgedrungen. Bei Continental wird derzeit die Anwendbarkeit von Pattern in AUTOSAR basierten Anwendungen untersucht. Der Vortrag wird auf die als in diesem Anwendungsbereich anwendbaren Pattern abzielen und die Vorgehensweise bei der Analyse darstellen. Des Weiteren wird die Anwendung eines Patterns an einem konkreten Beispiel aus dem Motorsteuerungsumfeld dargestellt. Es werden m\u00f6gliche L\u00f6sungswege zur Scheduling-Unterst\u00fctzung, z.B. \u00fcber Kerngrenzen synchronisierte Zustandswechsel oder die Anwendung von logischer Ausf\u00fchrungszeit, in diesem Kontext aufgezeigt. Eingebettete Systeme im Antriebsstrang eines Kraftfahrzeugs sind seit mehr als 25 Jahren in Verwendung. Sie dienen dazu, die Verbrennung, die Schaltvorg\u00e4nge und das Batteriemanagement zu kontrollieren sowie auch vermehrt \u00fcbergeordnete Algorithmen in Dom\u00e4nen-Steuerger\u00e4ten zu darzustellen. Seit etwa f\u00fcnf Jahren haben Mehrkernrechner in dieses Anwendungsfeld Einzug gehalten. Es werden dort Mikrokontroller mit bis zu drei nahezu homogenen Kernen und einer Taktfrequenz von bis zu 300 MHz eingesetzt. Die darauf zum Einsatz kommende Software ist im Laufe der Jahrzehnte gewachsen; sie umfasst in einer Motorsteuerung etwa 2 Millionen Lines of Code und ben\u00f6tigt etwa 6 MB Programmspeicher.<\/p>\n Die verwendete Software-Architektur basiert auf dem AUTOSAR-Standard 4.0.[1]. Bei der Umstellung auf Mehrkernrechner wurde die Applikationssoftware im Hause Continental im Wesentlichen „Multicore Ready“ \u00fcberarbeitet, mit dem Ziel, Software \u00fcber Kerne hinweg zu verteilen und die Datenkonsistenz weiterhin sicherzustellen [2] Bei der Verteilung wurde darauf geachtet, Wirkketten zu erhalten und im Wesentlichen den inh\u00e4rent vorhandenen Task-Parallelismus auszunutzen. Bei derzeit etwa 60 Tasks (siehe Abbildung 1) in einem Motorsteuerungssystem war bis dato der erzielte Speedup ausreichend, um die Leistungsanforderungen der aktuellen Steuerger\u00e4tegeneration zu befriedigen.<\/p>\n (s. Abb. 1,\u00a0PDF<\/a>)<\/p>\n Eine wesentliche Herausforderung der im Abschnitt 1 genannten Anwendungen ist die Echtzeitf\u00e4higkeit. So finden dort Berechnungsvorg\u00e4nge in sich wiederholenden Tasks mit einer minimalen Wiederholrate von 1 Millisekunde und Deadlines von minimal 200 Mikrosekunden statt. Des Weiteren gibt es an die Motordrehzahl und das Ventilspiel der Verbrennungsmotoren gebundene, sich wiederholende Tasks. Die darin stattfindenden Berechnungen sind ein wesentlicher Faktor f\u00fcr die Qualit\u00e4t der Verbrennung und damit der Abgaszusammensetzung. Aufgrund steigender Anforderungen an die Abgasreinheit und den Kraftstoffverbrauch ist zu erwarten, dass diese Berechnungen in Zukunft noch mehr Rechenzeit ben\u00f6tigen. Deshalb ist es notwendig, diese Algorithmen in einer Weise zu entwerfen, die eine parallele Ausf\u00fchrung zul\u00e4sst, um auch weiterhin das Echtzeitverhalten gew\u00e4hrleisten zu k\u00f6nnen.<\/p>\n Es stellt sich nun die Frage, welche Strategie zur Findung von Parallelit\u00e4t zielf\u00fchrend ist. Bei Analyse des Codes stellt man in dieser Art Anwendungen sehr h\u00e4ufig fest, dass es l\u00e4ngere Berechnungsketten gibt, in denen man Cluster bilden kann, die sich auf Kerne verteilen lassen. Dazu kann man noch den Sourcecode durchsuchen und zum Beispiel hinsichtlich Schleifen-Parallelit\u00e4t Analysen durchf\u00fchren. Dabei l\u00e4sst sich h\u00e4ufig feststellen, dass sehr h\u00e4ufig kurze Schleifen zum Einsatz kommen, meist nur \u00fcber die Anzahl der Zylinder. In den gegebenen Rechnerarchitekturen ist es allerdings aus Effizienzgr\u00fcnden wenig sinnvoll, diese Schleifen \u00fcber Kerne zu parallelisieren.<\/p>\n Aus diesem Grunde wurde zu einer anderen Methode umgeschwenkt. In Interviews wurden die Funktionsentwickler, meist Maschinenbauingenieure, bez\u00fcglich des zu l\u00f6senden funktionalen Problems befragt, und es wurde anhand der Problemstellung versucht, den Softwareentwurf komplett neu zu gestalten, um Parallelit\u00e4t in der Softwareausf\u00fchrung zu erm\u00f6glichen. Dabei wurde den Entwicklungsteams einige Entwurfsmuster vorgestellt, um die Ideenfindung zu unterst\u00fctzen. In den folgenden Kapiteln werden einige der Entwurfsmuster vorgestellt, die sich dabei als umsetzbar herausgestellt haben.<\/p>\n Das „Pipe and Filter“ Entwurfsmuster hilft auf struktureller Ebene, Parallelit\u00e4t zu identifizieren, auch wenn eine Reihe von Tasks voneinander abh\u00e4ngt. Bei einem nach vorw\u00e4rts gerichteten Datenfluss und im Fall, dass die Taskausf\u00fchrung nicht vom Ergebnis der vorausgegangenen Stufe abh\u00e4ngt, lassen sich unterschiedliche Tasks in Stufen gruppieren, \u00e4hnlich dem „Pipeline“-Verfahren in Mikroprozessoren (siehe Abbildung 2,\u00a0PDF<\/a>).<\/p>\n Die Granularit\u00e4t der Stufen muss mit dem Synchronisierungsaufwand in einem ausgewogenen Verh\u00e4ltnis stehen. Ideal ist, wenn alle Stufen eine ann\u00e4hernd gleiche Ausf\u00fchrungszeit aufweisen. Ist dies nicht der Fall, bestimmt die l\u00e4ngste Stufe die Taktung von Stufe zu Stufe.<\/p>\n In einer Steuerungsanwendung, wie z.B. einer Motorsteuerung, kann f\u00fcr die relevanten Daten einer Systemfunktion Vorw\u00e4rtsrichtung im Datenfluss angenommen werden. Die verschiedenen Tasks k\u00f6nnen in Stufen eingeordnet werden. Ein Schema f\u00fcr die Einordnung stellt das bei Continental im Einsatz befindliche Phasenmodell [4] dar, welches sich in dieses Entwurfsmuster \u00fcberf\u00fchren l\u00e4sst.<\/p>\n Das „Divide and Conquer“ Pattern l\u00e4sst sich auf viele Algorithmen anwenden. Dabei wird eine Aufgabenstellung in Unteraufgaben geteilt. Bei dem Entwurf ist darauf zu achten, dass diese Unteraufgaben unabh\u00e4ngig voneinander gel\u00f6st werden k\u00f6nnen. Dies erlaubt dann, die Unteraufgaben auf verschiedene Kerne auszulagern (siehe Abbildung 2,\u00a0PDF<\/a>). Am Ende m\u00fcssen die \u00a0Teilergebnisse wieder zusammengef\u00fchrt werden, welches einen gewissen Synchronisationsaufwand bedeutet. In Steuerungsanwendungen existiert daf\u00fcr eine Reihe von Anwendungsf\u00e4llen. Von Vorteil ist, mehrere wiederum voneinander unabh\u00e4ngige Algorithmen dieser Art zusammenzufassen, um den Synchronisierungsaufwand gering zu halten.<\/p>\n Das „Bulk Synchronous Parallel Pattern“ erlaubt, Tasks, die auf unterschiedlichen Kernen zur Ausf\u00fchrung kommen, an einer Barriere zusammenzuf\u00fchren und dadurch zu synchronisieren. Zu Beginn einer parallelen Phase werden die Daten jedem Task in einer lokalen Kopie aus dem globalen Speicher zur Verf\u00fcgung gestellt. W\u00e4hrend der Ausf\u00fchrung wird auf der lokalen Kopie gearbeitet. W\u00e4hrend der Taskausf\u00fchrung ist Kommunikation nur zwischen Runnables dieses Tasks erlaubt.<\/p>\n Nachdem alle parallel laufen Tasks beendet wurden, werden die Ergebnisse wieder im Global-Speicher zur Verf\u00fcgung gestellt, bevor die n\u00e4chste Phase startet.<\/p>\n Diese Art von Barrieren kann zur Implementierung des „Divide and Conquer“ Patterns als auch des „Pipe and Filter“ Patterns verwendet werden. Aufeinanderfolgende Phasen k\u00f6nnen die verschiedenen Stufen der Pipeline darstellen.<\/p>\n (s. Abb. 3,\u00a0PDF<\/a>)<\/p>\n In Steuerger\u00e4ten im Fahrzeug finden sehr h\u00e4ufig Zustandswechsel statt. Einige davon haben Auswirkungen auf das Gesamtsystem, was zur Konsequenz hat, dass bei einer auf die Kerne eines Controllers verteilten Anwendung diese Zustandswechsel zu synchronisieren sind. Um das Echtzeitverhalten der zyklischen Tasks nicht zu beeintr\u00e4chtigen, werden durch einen sog. „Event-Koordinator“ nach einer erkannten Anforderung zum Wechsel eines Systemzustandes die zyklisch laufenden Tasks beendet und aktivierte Tasks mit weniger kritischen Deadlines verz\u00f6gert; dadurch \u00a0wird im Gesamtsystem ein freier Zeitslot provoziert. Der „Event-Koordinator“ feuert dann zeitgleich auf allen Kernen jeweils einen Zustandswechsel-Task. Darin lassen sich sehr gut Initialisierungsfunktionen parallel ausf\u00fchren, da diese typischerweise nicht oder nur geringf\u00fcgig gekoppelt sind. Nachdem auf allen Kernen die Zustandswechsel-Tasks beendet sind, wird die Abarbeitung der zyklischen Tasks vom „Event Koordinator“ wieder freigegeben.<\/p>\n Durch dieses Verfahren l\u00e4sst sich die ben\u00f6tigte Rechenzeit bei derlei Zustandswechseln signifikant verk\u00fcrzen. Die Initialisierung eines Fehlerspeichers mit etwa 1000 Fehlerorten liefert hier die eindrucksvollsten Ergebnisse, da dies eine der wenigen M\u00f6glichkeiten ist, in einer Steuerungsanwendung von einer Schleifenoptimierung zu profitieren. Der Parallelisierungsgrad dabei ist nahezu 100%, was gem\u00e4\u00df „Amdahls Law“ einem Speedup gleich der Anzahl der Kerne entspricht.<\/p>\n (s. Abb. 4,\u00a0PDF<\/a>)<\/p>\n Das Zeitverhalten von Mehrkernrechner-Systemen mit Hilfe des logischen Ausf\u00fchrungszeitmodells zu beschreiben und zu implementieren, erlaubt die Implementierung des im Abschnitt 4 beschriebenen „Pipe and Filter“ als auch des „Divide and Conquer“ Pattern.<\/p>\n Durch das Einteilen einer Zeit-Periode in Abschnitte mit logischen Ausf\u00fchrungszeit lassen sich Berechnungsketten darstellen, die zwar in einer Sequenz abgearbeitet werden, aber streckenweise Parallelisierungsm\u00f6glichkeiten beinhalten. Analysiert man zum Beispiel, wie in Abbildung f\u00fcnf gezeigt, die Sequenz eines Tasks, kann man dieses Muster erkennen. Die so gefundenen sequenziellen und parallelen Cluster k\u00f6nnen in einem wie in Abbildung 6 dargestellten logischen Ausf\u00fchrungszeitrahmen zur Abarbeitung [5] gebracht werden. Die Kommunikation von sequenziell aufeinanderfolgenden LETs erfolgt ohne zus\u00e4tzliche Datenkonsistenz-Mechanismen, wobei die Kommunikation zwischen parallelen Tasks \u00fcber Konsistenzpuffer gesch\u00fctzt wird [6].<\/p>\n (s. Abb. 5 und 6,\u00a0PDF<\/a>)<\/p>\n Wie gezeigt, wurde die Identifikation von Parallelit\u00e4t \u00fcber den bereits gefundenen Taskparallelismus hinaus in Kontrollanwendungen eingeschr\u00e4nkt. Trotzdem lassen sich einige Pattern identifizieren und durchaus mit Erfolg anwenden. Ein wesentlicher Faktor f\u00fcr den Erfolg ist Parallelit\u00e4t bereits beim Funktionsdesign mit zu ber\u00fccksichtigen. Ein architektureller Rahmen, wie ihn die Anwendung des logischen Ausf\u00fchrungszeitsmodells bietet, kann in abstrahierte Form \u00e4hnlich dem Phasenkonzept [4] den Entwicklern an die Hand gegeben werden. Dies w\u00fcrde die Anwendbarkeit dieses Ansatzes deutlich vereinfachen. Hier ist in Zukunft noch eine bessere Unterst\u00fctzung durch Designwerkzeuge w\u00fcnschenswert.<\/p>\n [1] AUTOSAR-Consortium, in https:\/\/www.autosar.org\/index.php?p=3&up=2&uup=0, Rev 4.0.3.<\/p>\n [2] D. Claraz, F. Grimal, T. Ledier, R. Mader, and G. Wirrer, \u201cIntroducing multi-core at automotive engine systems\u201d, in ERTS2, 2014.<\/p>\n [3] M. Negrean, R. Ernst, and S. Schliecker, \u201cMastering timing challenges for the design of multi-mode applications on multicore real-time embedded systems\u201d, in 6th International Congress of Embedded Real-Time Software and Systems (ERTS), 2012.<\/p>\n [4] D. Claraz, S. Kuntz, U. Margull, M. Niemetz, and G. Wirrer, \u201cDeterministic Execution Sequence in Component Based Multi-Contributor Powertrain Control Systems\u201d, in ERTSS 2012, 2012.<\/p>\n [5] J. Hennig, H. von Hasseln, H. Mohammad, S. Resmerita, S. Lukesch, and A.Naderlinger. 2016. Towards parallelizing legacy embedded control software using the LET programming paradigm. In Proc. of WiP Papers of the 22nd IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS \u201916).<\/p>\n [6] Stefan Resmerita, Andreas Naderlinger, Stefan Lukesch, \u201cEfficient Realization of Logical Execution Times in Legacy Embedded Software\u201d MEMOCODE\u201917, Vienna, Austria, 2017<\/p>\n Ralph Mader<\/strong>\u00a0studied Electrical Engineering at the University of Applied Sciences in Regensburg. He worked on the design and selection of microcontrollers for the Powertrain area and the efficient use of microcontroller resources. Since 2010, he is also leading development of the Multi Core software architecture for engine management systems. Mr. Mader represents Continental Automotive GmbH in several research projects in this area.<\/p>\n Beitrag als PDF downloaden<\/strong><\/a><\/p>\n Wollen Sie sich auf den aktuellen Stand der Technik bringen?<\/strong><\/p>\n Dann informieren Sie sich\u00a0hier<\/strong>\u00a0<\/a>zu Schulungen\/ Seminaren\/ Trainings\/ Workshops und individuellen Coachings von MircoConsult zum Thema\u00a0Automotive\/ Embedded- und Echtzeit-Softwareentwicklung.<\/p>\n Training & Coaching zu den weiteren Themen unseren Portfolios finden Sie\u00a0hier<\/a>.<\/strong><\/p>\n Wertvolles Fachwissen zum Thema Automotive \/Embedded- und Echtzeit-Softwareentwicklung steht\u00a0hier\u00a0<\/strong><\/a>f\u00fcr Sie zum kostenfreien Download bereit.<\/p>\n
\n<\/strong><\/p>\n1. Vorstellen der Anwendungsdom\u00e4ne<\/h2>\n
2. Herausforderungen der Anwendung<\/h2>\n
3. Wie kann Parallelit\u00e4t gefunden werden?<\/h2>\n
4. Design Pattern f\u00fcr paralleles Programmieren<\/h2>\n
4.1 Pipe and Filter Design Pattern<\/h2>\n
4.2 Divide and Conquer (Algorithm Strategy Pattern)<\/strong><\/h3>\n
4.3 Bulk Synchronous Parallel<\/h3>\n
5. Implementierungsbeispiele<\/h2>\n
5.1 \u00dcber Kerne synchronisierter Zustandswechsel<\/h3>\n
5.2 Logical Execution Time (LET)<\/h3>\n
6. Zusammenfassung und Ausblick<\/h2>\n
Quellenverzeichnis<\/h2>\n
Autor<\/h2>\n
\nAutomotive – unsere Trainings & Coachings<\/h2>\n
\nAutomotive – Fachwissen<\/h2>\n