ESE Fachwissen
Effiziente Embeddded-Multicore-Programmierung
Autoren: Oliver Oey, Timo Stripf, emmtrix Technologies
Beitrag - Embedded Software Engineering Kongress 2015
Durch immer weiter steigende Performanzanforderungen wird in immer mehr Bereichen anstelle von Einkernprozessoren auf Mehrkernprozessoren gesetzt. Dieser Wechsel ist im Bereich von Desktop-PCs oder Smartphones bereits vollzogen, im Bereich der eingebetteten Systeme ist der Umbruch jedoch noch im Gange. Durch die parallele Ausführung von Programmen kann sowohl die Performanz gesteigert als auch die Leistungsaufnahme reduziert werden. Bis heute verursacht die parallele Programmierung jedoch einen hohen Zeit- und Kostenaufwand und erfordert spezielles Wissen über die Zielsysteme. Innerhalb des ALMA-EU-Projekts hat ein Konsortium aus Forschung und Industrie eine Werkzeugkette entwickelt, die die parallele Programmierung erheblich vereinfacht. Mittels automatischer Parallelisierung wird sequentieller Scilab/MATLAB-Code für eingebettete Multicore-Prozessoren parallelisiert. Dadurch kann nicht nur die aufwändige manuelle Parallelisierung eingespart, sondern auch der Code auf verschiedenen Prozessoren wiederverwendet werden.
Motivation
Laut Studien [1] ist die Programmierung von eingebetteten Mehrkernsystemen 4,5-mal so teuer, dauert 25% länger und benötigt 3-mal so viele Software-Ingenieure wie die Programmierung von Einkernsystemen. Das Ziel des EU-Projekts ALMA war es, diese Anforderungen an den Entwickler zu reduzieren. Dazu wurde die Entwicklung in zwei Bereiche aufgeteilt: die reine Programmierung des Algorithmus und die Anpassung an die gegebene Hardware. Um diese Anforderungen an die Entwickler zu reduzieren, wurden im EU-Projekt ALMA eine automatische Parallelisierung und Codeerzeugung aus arraybasierten Programmiersprachen untersucht. Zu diesen gehören MATLAB und ähnliche Sprachen wie Scilab, die sehr nah an der rein mathematischen Beschreibung sind und als Standarddatentyp auf Matrizen arbeiten. Aus diesem Grund eignen sie sich auch gut für Anwender, die keinen großen Programmierhintergrund haben. Der Programmierer kann sich auf die Entwicklung des Algorithmus konzentrieren, während die Anpassungen an die Zielhardware automatisch durch die Werkzeugkette erledigt werden.
ALMA - Projektübersicht
Die ALMA-Werkzeugkette, wie sie in [2] vorgestellt wurde, ist in mehrere Teilkomponenten unterteilt, die in Abbildung 1 (siehe PDF) dargestellt werden. Als Eingangsdateien kommen die Anwendungen, die in Scilab/MATLAB geschrieben wurden, sowie eine abstrakte Architekturbeschreibung zum Einsatz. Das Matrix FrontEnd wandelt den Eingangscode zunächst in einen sequentiellen C-Code um, der als Basis für die Parallelisierung verwendet wird. Die Parallelisierungswerkzeuge erzeugen optimierten Code für die Zielarchitekturen, indem der Code parallelisiert und an die Eigenheiten der Zielplattformen angepasst wird, wie sie in der Architekturbeschreibung hinterlegt sind. In weiteren Optimierungsschritten können Laufzeitinformationen, die mit dem Multicore-Simulator ermittelt werden, für eine bessere Auslastung der Hardware verwendet werden.
Evaluation
Zur Evaluation des Ansatzes kamen zwei Zielarchitekturen sowie zwei Testanwendungen zum Einsatz. Die Architekturen waren aufgeteilt in den wissenschaftlichen Prozessor Kahrisma [3] sowie das X2014 System der Firma Recore Systems. Beide Plattformen setzen auf verteilten Speicher sowie mehrere unabhängig arbeitende Kerne. Die Zielanwendungen kamen zum einen aus der Bildverarbeitung vom Fraunhofer IOSB, bei der eine Objekterkennung mit Hilfe des SIFT-Algorithmus durchgeführt wurde, und zum anderen aus der Telekommunikation von Intracom Telecom, in dem Teile des WiMax-Standards in Software ausgeführt werden.
ALMA Werkzeugkette & Workflow
Scilab/MATLAB sind Skriptsprachen, das bedeutet, dass die Befehle nacheinander von einer Laufzeitumgebung interpretiert und ausgeführt werden. Dies ermöglicht es, dass Eigenschaften wie beispielsweise die Größe oder der Typ von Variablen, erst zur Laufzeit festgelegt werden. Eine Umsetzung dieses Verhaltens in C ist zwar möglich, aber aufgrund der Performanz und des Speicherverbrauchs nicht sinnvoll. Aus dem allgemeinen MATLAB-Code wird als erstes C-Code erzeugt, der sich gut für die statische Analyse und die spätere Parallelisierung eignet. Dazu werden alle dynamischen Entscheidungen aufgelöst, so dass der statische Programmablauf besser analysiert werden kann. Im Falle von Variablen wird zunächst über die gesamte Laufzeit des Programms betrachtet, welcher Datentyp nötig ist, um alle Zahlen ohne Einschränkungen darstellen zu können. Im C-Code wird dieser Datentyp verwendet, um sowohl die dynamischen Entscheidungen zu reduzieren als auch den Speicherverbrauch zu minimieren. Ein weiterer Vorteil von MATLAB hinsichtlich der Parallelisierung ist das Fehlen von Pointern. Dies ermöglicht es, den Datenfluss in einem Programm eindeutig bestimmen zu können, was wichtig für den Datentransfer zwischen den verschiedenen Kernen ist.
Die abstrakte Hardwarebeschreibung setzt auf eine im Projekt entwickelte Architektur-Beschreibungssprache (engl. architecture desciption language, ADL) [4]. Als Besonderheit wird eine Beschreibung auf verschiedenen Abstraktionsebenen unterstützt. So können Hardware-Module sowohl rein funktional als auch detailliert mit Angabe von Zyklen-akkuraten Instruktionen dargestellt werden. Auf diese Weise können sowohl Informationen, die zur Simulation der Hardware notwendig sind, als auch abstraktere Informationen, die für die Parallelisierungsentscheidung benötigt werden, dargestellt werden.
Um eine gute Performanz einer parallelisierten Anwendung zu erreichen, muss die Parallelisierung auf zwei unterschiedlichen Ebenen ansetzen: auf einer feinen und einer groben. Dabei zielt die feine auf eine Optimierung der Ausführung auf einem Kern ab, und die grobe optimiert die gleichzeitige Ausführung auf mehreren Kernen. Durch diese Kombination kann die gegebene Hardware möglichst effizient ausgenutzt werden.
Die feingranulare Parallelisierungsextraktion (engl. fine-grained parallelism extraction) analysiert zunächst die benötigten Datentypen hinsichtlich eines Kompromisses aus effizienter Ausnutzung der Hardware und der benötigten Genauigkeit der Ergebnisse. Dies erlaubt es, die SIMD (engl. single instruction, multiple data) Einheiten der Architektur auszunutzen, indem beispielsweise vier 8-Bit-Additionen gleichzeitig ausgeführt werden anstelle einer 32-Bit-Addition. Wie in [5] dargestellt, wird außerdem ermittelt, ob Zahlen in einer Festkommadarstellung repräsentiert werden können. Der Einsatz kann die Performanz bei der Ausführung erhöhen, hat aber Einfluss auf die Genauigkeit. Des Weiteren werden Schleifen transformiert, um Zugriffe auf Daten besser an die vorhandenen Caches anzupassen.
Die grobgranulare Parallelisierung, wie sie in [6] vorgestellt wurde, verteilt die Anwendung auf die einzelnen Kerne der Zielplattform. Ziel dieser Optimierung ist es, die Ausführungszeit des gesamten Programms zu reduzieren, indem möglichst viele parallele Recheneinheiten der Architektur gleichzeitig verwendet werden. Für die Parallelisierung wird auf eine hierarchische Task-Darstellung des Programms zurückgegriffen. Jedes Kontrollflusskonstrukt, wie Schleife oder Bedingung, innerhalb des Programmablaufs sorgt für das Hinzufügen einer neuen Ebene in der Hierarchie. Ein Beispiel ist in Abbildung 2 (siehe PDF) dargestellt. Die Darstellung erlaubt es, die Parallelisierung sowohl von oben herab als auch von unten herauf durchzuführen. Auf diese Weise kann eine optimale Verteilung der Aufgaben auf die einzelnen Kerne für jede Ebene ermittelt werden und anschließend der optimale Gesamtablauf bestimmt werden.
Die parallele Codegenerierung [6] erzeugt schließlich parallelen C-Code, der auf der Hardware oder den zugehörigen Simulatoren ausgeführt werden kann. Dazu erstellt die Codegenerierung separaten Quellcode für die einzelnen Kerne der Hardware-Plattform, indem Datenabhängigkeiten zwischen den einzelnen Prozessoren über Kommunikationsinstruktionen aufgelöst werden. Die Kommunikationssynthese achtet dabei auf eine Reduzierung der anfallenden Wartezeiten und ist auf Systeme mit verteiltem Speicher optimiert, aber nicht auf sie beschränkt. Für die Kommunikation können sowohl verbreitete Modelle wie MPI (message passing interface) als auch spezielle Funktionen der jeweiligen Plattformen ausgenutzt werden.
Der erzeugte Code kann automatisch instrumentiert werden, um Laufzeitinformationen mit Hilfe eines Simulators zu ermitteln. Diese Informationen können verwendet werden, um die Parallelisierung und damit auch die Performanz iterativ zu verbessern. [7] Dazu fließen die Laufzeiten der einzelnen Codeteile und der Übertragung von Daten zurück in die grobgranulare Parallelisierung und ermöglichen eine Aufteilung, die besser an die tatsächliche Hardware angepasst ist.
Ergebnisse
Die Werkzeugkette soll zwei Ziele erfüllen: Zum einen soll die Leistungsfähigkeit von Mehrkernsystemen durch eine sinnvolle Parallelisierung der Anwendung ausgenutzt werden können. Zum anderen soll die Produktivität gesteigert werden, indem der Entwicklungsaufwand für parallele eingebettete Systeme reduziert wird.
In Abbildung 3 (siehe PDF) ist die im Projekt ermittelte Reduktion des Entwicklungsaufwands dargestellt. Verglichen wurde eine manuelle Umsetzung eines bestehenden Algorithmus in parallelem C-Code mit dem Einsatz des Parallelisierungswerkzeugs, das in ALMA entwickelt wurde. Bei den gewählten Beispielen konnten dabei Einsparungen von 30 bis 57 % in der Entwicklungszeit erreicht werden. Dabei konnte, wie in Abbildung 4 (siehe PDF) dargestellt, ein Speedup von 2,8 beim Einsatz von vier Kernen erreicht werden.
Zusammenfassung und Ausblick
Die vorgestellte ALMA-Werkzeugkette erleichtert die Programmierung von eingebetteten Multicore-Systemen, indem die zeitaufwändige Parallelisierung automatisiert durchgeführt wird. Die Evaluation zeigte, dass der Entwicklungsaufwand um bis zu 57% reduziert werden konnte und dabei ein Speedup von 2,8 beim Einsatz von vier Kernen erreicht werden konnte.
Die ALMA-Technologie wird der Industrie durch das EXIST-geförderte KIT-Spin-Off "emmtrix Technologies" (www.emmtrix.com) verfügbar gemacht, weiterentwickelt und an spezielle Kundenanforderungen angepasst. Die Technologie ermöglicht Unternehmen, Mehrkernprozessoren im eingebetteten Bereich einfacher einzusetzen. Bei der Entwicklung werden Kosten reduziert sowie die Time-to-Market verkürzt. Für Entwickler wird durch Automatisierung und Integration von Spezialwissen die Programmierung eingebetteter Mehrkernsysteme vereinfacht.
emmtrix setzt dabei auf einen in der Industrie etablierten Workflow, bei dem Algorithmen in MATLAB entwickelt und für die Ausführung auf der Hardware nach C-Code übersetzt werden. Dies erfolgt bei Singlecore-Prozessoren automatisch mit Hilfe eines Codegenerators. Für die Umsetzung auf Multicore-Prozessoren muss derzeit jedoch auf eine manuelle Neu-Implementierung zurückgegriffen werden. Die emmtrix-Lösung wird vollständig in diesen Workflow integriert (siehe Abbildung 5, PDF) und erlaubt es dem Entwickler, den MATLAB-Code effizient auf eingebettete Multicore-Systeme umzusetzen.
Literatur- und Quellenverzeichnis
|
[1] |
"Next Generation Embedded Hardware Architectures: Driving Onset of Project Delays, Costs Overruns, and Software Development Challenges", VDC Research, September 2010. |
|
[2] |
J. Becker, T. Stripf, O. Oey, M. Huebner, S. Derrien, D. Menard, O. Sentieys, G. Rauwerda, K. Sunesen, N. Kavvadias, K. Masselos, G. Goulas, P. Alefragis, N. Voros, D. Kritharidis, N. Mitas and D. Goehringer, "From Scilab to High Performance Embedded Multicore Systems: The ALMA Approach", in Digital System Design (DSD), 2012 15th Euromicro Conference on, 2012. |
|
[3] |
R. Koenig, L. Bauer, T. Stripf, M. Shafique, W. Ahmed und J. a. H. J. Becker, "KAHRISMA: A Novel Hypermorphic Reconfigurable-instruction-set Multi-grained-array Architecture", in Proceedings of the Conference on Design, Automation and Test in Europe, Dresden, Germany, 2010. |
|
[4] |
T. Bruckschloegl, O. Oey, M. Ruckauer, T. Stripf und J. Becker, "A Hierarchical Architecture Description for Flexible Multicore System Simulation", in Parallel and Distributed Processing with Applications (ISPA), 2014 IEEE International Symposium on, Milano, Italy, 2014. |
|
[5] |
G. Deest, T. Yuki, O. Sentieys und S. Derrien, "Toward scalable source level accuracy analysis for floating-point to fixed-point conversion", in Proceedings of the 2014 IEEE/ACM International Conference on Computer-Aided Design (ICCAD '14), Piscataway, NJ, USA, 2014. |
|
[6] |
G. Goulas, C. Valouxis, P. Alefragis, N. Voros, O. Oey, T. Stripf, T. Bruckschloegl, J. Becker, C. Gogos, A. El Moussawi, M. Naullet und T. Yuki, "Coarse-Grain Optimization and Code Generation for Embedded Multicore Systems", in Digital System Design (DSD), 2013 Euromicro Conference on Digital System Design, 2013. |
|
[7] |
J. Becker, T. Bruckschloegl, O. Oey, T. Stripf, G. Goulas, N. Raptis, C. Valouxis, P. Alefragis, N. Voros und C. Gogos, "Profile-Guided Compilation of Scilab Algorithms for Multiprocessor Systems", in Reconfigurable Computing: Architectures, Tools, and Applications, Springer International Publishing, 2014, pp. 330-336. |
Multicore - unsere Trainings & Coachings
Wollen Sie sich auf den aktuellen Stand der Technik bringen?
Dann informieren Sie sich hier zu Schulungen/ Seminaren/ Trainings/ Workshops und individuellen Coachings von MircoConsult zum Thema Multicore /Mikrocontroller.
Training & Coaching zu den weiteren Themen unseren Portfolios finden Sie hier.
Multicore - Fachwissen
Wertvolles Fachwissen zum Thema Multicore /Mikrocontroller steht hier für Sie zum kostenfreien Download bereit.
Fachwissen zu weiteren Themen unseren Portfolios finden Sie hier.