Autoren: Oliver Oey, Timo Stripf, emmtrix Technologies<\/p>\n
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\u00fchrung 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 \u00fcber 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\u00fcr eingebettete Multicore-Prozessoren parallelisiert. Dadurch kann nicht nur die aufw\u00e4ndige manuelle Parallelisierung eingespart, sondern auch der Code auf verschiedenen Prozessoren wiederverwendet werden.<\/strong><\/p>\n Laut Studien [1] ist die Programmierung von eingebetteten Mehrkernsystemen 4,5-mal so teuer, dauert 25% l\u00e4nger und ben\u00f6tigt 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\u00f6ren MATLAB und \u00e4hnliche 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\u00fcr Anwender, die keinen gro\u00dfen Programmierhintergrund haben. Der Programmierer kann sich auf die Entwicklung des Algorithmus konzentrieren, w\u00e4hrend die Anpassungen an die Zielhardware automatisch durch die Werkzeugkette erledigt werden.<\/p>\n Die ALMA-Werkzeugkette, wie sie in [2] vorgestellt wurde, ist in mehrere Teilkomponenten unterteilt, die in Abbildung 1 (siehe\u00a0PDF<\/a>) 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\u00e4chst in einen sequentiellen C-Code um, der als Basis f\u00fcr die Parallelisierung verwendet wird. Die Parallelisierungswerkzeuge erzeugen optimierten Code f\u00fcr 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\u00f6nnen Laufzeitinformationen, die mit dem Multicore-Simulator ermittelt werden, f\u00fcr eine bessere Auslastung der Hardware verwendet werden.<\/p>\n 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\u00e4ngig arbeitende Kerne. Die Zielanwendungen kamen zum einen aus der Bildverarbeitung vom Fraunhofer IOSB, bei der eine Objekterkennung mit Hilfe des SIFT-Algorithmus durchgef\u00fchrt wurde, und zum anderen aus der Telekommunikation von Intracom Telecom, in dem Teile des WiMax-Standards in Software ausgef\u00fchrt werden.<\/p>\n Scilab\/MATLAB sind Skriptsprachen, das bedeutet, dass die Befehle nacheinander von einer Laufzeitumgebung interpretiert und ausgef\u00fchrt werden. Dies erm\u00f6glicht es, dass Eigenschaften wie beispielsweise die Gr\u00f6\u00dfe oder der Typ von Variablen, erst zur Laufzeit festgelegt werden. Eine Umsetzung dieses Verhaltens in C ist zwar m\u00f6glich, aber aufgrund der Performanz und des Speicherverbrauchs nicht sinnvoll. Aus dem allgemeinen MATLAB-Code wird als erstes C-Code erzeugt, der sich gut f\u00fcr die statische Analyse und die sp\u00e4tere Parallelisierung eignet. Dazu werden alle dynamischen Entscheidungen aufgel\u00f6st, so dass der statische Programmablauf besser analysiert werden kann. Im Falle von Variablen wird zun\u00e4chst \u00fcber die gesamte Laufzeit des Programms betrachtet, welcher Datentyp n\u00f6tig ist, um alle Zahlen ohne Einschr\u00e4nkungen darstellen zu k\u00f6nnen. 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\u00f6glicht es, den Datenfluss in einem Programm eindeutig bestimmen zu k\u00f6nnen, was wichtig f\u00fcr den Datentransfer zwischen den verschiedenen Kernen ist.<\/p>\n 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\u00fctzt. So k\u00f6nnen Hardware-Module sowohl rein funktional als auch detailliert mit Angabe von Zyklen-akkuraten Instruktionen dargestellt werden. Auf diese Weise k\u00f6nnen sowohl Informationen, die zur Simulation der Hardware notwendig sind, als auch abstraktere Informationen, die f\u00fcr die Parallelisierungsentscheidung ben\u00f6tigt werden, dargestellt werden.<\/p>\n 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\u00fchrung auf einem Kern ab, und die grobe optimiert die gleichzeitige Ausf\u00fchrung auf mehreren Kernen. Durch diese Kombination kann die gegebene Hardware m\u00f6glichst effizient ausgenutzt werden.<\/p>\n Die feingranulare Parallelisierungsextraktion (engl. fine-grained parallelism extraction) analysiert zun\u00e4chst die ben\u00f6tigten Datentypen hinsichtlich eines Kompromisses aus effizienter Ausnutzung der Hardware und der ben\u00f6tigten 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\u00fchrt werden anstelle einer 32-Bit-Addition. Wie in [5] dargestellt, wird au\u00dferdem ermittelt, ob Zahlen in einer Festkommadarstellung repr\u00e4sentiert werden k\u00f6nnen. Der Einsatz kann die Performanz bei der Ausf\u00fchrung erh\u00f6hen, hat aber Einfluss auf die Genauigkeit. Des Weiteren werden Schleifen transformiert, um Zugriffe auf Daten besser an die vorhandenen Caches anzupassen.<\/p>\n 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\u00fchrungszeit des gesamten Programms zu reduzieren, indem m\u00f6glichst viele parallele Recheneinheiten der Architektur gleichzeitig verwendet werden. F\u00fcr die Parallelisierung wird auf eine hierarchische Task-Darstellung des Programms zur\u00fcckgegriffen. Jedes Kontrollflusskonstrukt, wie Schleife oder Bedingung, innerhalb des Programmablaufs sorgt f\u00fcr das Hinzuf\u00fcgen einer neuen Ebene in der Hierarchie. Ein Beispiel ist in Abbildung 2 (siehe\u00a0PDF<\/a>) dargestellt. Die Darstellung erlaubt es, die Parallelisierung sowohl von oben herab als auch von unten herauf durchzuf\u00fchren. Auf diese Weise kann eine optimale Verteilung der Aufgaben auf die einzelnen Kerne f\u00fcr jede Ebene ermittelt werden und anschlie\u00dfend der optimale Gesamtablauf bestimmt werden.<\/p>\n Die parallele Codegenerierung [6] erzeugt schlie\u00dflich parallelen C-Code, der auf der Hardware oder den zugeh\u00f6rigen Simulatoren ausgef\u00fchrt werden kann. Dazu erstellt die Codegenerierung separaten Quellcode f\u00fcr die einzelnen Kerne der Hardware-Plattform, indem Datenabh\u00e4ngigkeiten zwischen den einzelnen Prozessoren \u00fcber Kommunikationsinstruktionen aufgel\u00f6st werden. Die Kommunikationssynthese achtet dabei auf eine Reduzierung der anfallenden Wartezeiten und ist auf Systeme mit verteiltem Speicher optimiert, aber nicht auf sie beschr\u00e4nkt. F\u00fcr die Kommunikation k\u00f6nnen sowohl verbreitete Modelle wie MPI (message passing interface) als auch spezielle Funktionen der jeweiligen Plattformen ausgenutzt werden.<\/p>\n Der erzeugte Code kann automatisch instrumentiert werden, um Laufzeitinformationen mit Hilfe eines Simulators zu ermitteln. Diese Informationen k\u00f6nnen verwendet werden, um die Parallelisierung und damit auch die Performanz iterativ zu verbessern.\u00a0[7] Dazu flie\u00dfen die Laufzeiten der einzelnen Codeteile und der \u00dcbertragung von Daten zur\u00fcck in die grobgranulare Parallelisierung und erm\u00f6glichen eine Aufteilung, die besser an die tats\u00e4chliche Hardware angepasst ist.<\/p>\n Die Werkzeugkette soll zwei Ziele erf\u00fcllen: Zum einen soll die Leistungsf\u00e4higkeit von Mehrkernsystemen durch eine sinnvolle Parallelisierung der Anwendung ausgenutzt werden k\u00f6nnen. Zum anderen soll die Produktivit\u00e4t gesteigert werden, indem der Entwicklungsaufwand f\u00fcr parallele eingebettete Systeme reduziert wird.<\/p>\n In Abbildung 3 (siehe\u00a0PDF<\/a>) 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\u00e4hlten Beispielen konnten dabei Einsparungen von 30 bis 57 % in der Entwicklungszeit erreicht werden. Dabei konnte, wie in Abbildung 4 (siehe\u00a0PDF<\/a>) dargestellt, ein Speedup von 2,8 beim Einsatz von vier Kernen erreicht werden.<\/p>\n Die vorgestellte ALMA-Werkzeugkette erleichtert die Programmierung von eingebetteten Multicore-Systemen, indem die zeitaufw\u00e4ndige Parallelisierung automatisiert durchgef\u00fchrt 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.<\/p>\n Die ALMA-Technologie wird der Industrie durch das EXIST-gef\u00f6rderte KIT-Spin-Off „emmtrix Technologies“ (www.emmtrix.com) verf\u00fcgbar gemacht, weiterentwickelt und an spezielle Kundenanforderungen angepasst. Die Technologie erm\u00f6glicht Unternehmen, Mehrkernprozessoren im eingebetteten Bereich einfacher einzusetzen. Bei der Entwicklung werden Kosten reduziert sowie die Time-to-Market verk\u00fcrzt. F\u00fcr Entwickler wird durch Automatisierung und Integration von Spezialwissen die Programmierung eingebetteter Mehrkernsysteme vereinfacht.<\/p>\n emmtrix setzt dabei auf einen in der Industrie etablierten Workflow, bei dem Algorithmen in MATLAB entwickelt und f\u00fcr die Ausf\u00fchrung auf der Hardware nach C-Code \u00fcbersetzt werden. Dies erfolgt bei Singlecore-Prozessoren automatisch mit Hilfe eines Codegenerators. F\u00fcr die Umsetzung auf Multicore-Prozessoren muss derzeit jedoch auf eine manuelle Neu-Implementierung zur\u00fcckgegriffen werden. Die emmtrix-L\u00f6sung wird vollst\u00e4ndig in diesen Workflow integriert (siehe Abbildung 5,\u00a0PDF<\/a>) und erlaubt es dem Entwickler, den MATLAB-Code effizient auf eingebettete Multicore-Systeme umzusetzen.<\/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 Multicore \/Mikrocontroller.<\/p>\n Training & Coaching zu den weiteren Themen unseren Portfolios finden Sie\u00a0hier<\/a>.<\/strong><\/p>\n Wertvolles Fachwissen zum Thema Modellierung \/Embedded- und Echtzeit-Softwareentwicklung steht\u00a0hier<\/strong>\u00a0<\/a>f\u00fcr Sie zum kostenfreien Download bereit.<\/p>\nMotivation<\/h2>\n
ALMA – Projekt\u00fcbersicht<\/h2>\n
Evaluation<\/h2>\n
ALMA Werkzeugkette & Workflow<\/h2>\n
Ergebnisse<\/h2>\n
Zusammenfassung und Ausblick<\/h2>\n
Literatur- und Quellenverzeichnis<\/h2>\n
\n\n
\n [1]<\/td>\n „Next Generation Embedded Hardware Architectures: Driving Onset of Project Delays, Costs Overruns, and Software Development Challenges“, VDC Research, September 2010.<\/td>\n<\/tr>\n \n [2]<\/td>\n 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\u00a0Digital System Design (DSD), 2012 15th Euromicro Conference on<\/em>, 2012.<\/td>\n<\/tr>\n \n [3]<\/td>\n 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\u00a0Proceedings of the Conference on Design, Automation and Test in Europe<\/em>, Dresden, Germany, 2010.<\/td>\n<\/tr>\n \n [4]<\/td>\n T. Bruckschloegl, O. Oey, M. Ruckauer, T. Stripf und J. Becker, „A Hierarchical Architecture Description for Flexible Multicore System Simulation“, in\u00a0Parallel and Distributed Processing with Applications (ISPA), 2014 IEEE International Symposium on<\/em>, Milano, Italy, 2014.<\/td>\n<\/tr>\n \n [5]<\/td>\n G. Deest, T. Yuki, O. Sentieys und S. Derrien, „Toward scalable source level accuracy analysis for floating-point to fixed-point conversion“, in\u00a0Proceedings of the 2014 IEEE\/ACM International Conference on Computer-Aided Design (ICCAD ’14)<\/em>, Piscataway, NJ, USA, 2014.<\/td>\n<\/tr>\n \n [6]<\/td>\n 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\u00a0Digital System Design (DSD), 2013 Euromicro Conference on\u00a0Digital System Design<\/span><\/em>, 2013.<\/td>\n<\/tr>\n \n [7]<\/td>\n 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\u00a0Reconfigurable Computing: Architectures, Tools, and Applications<\/em>, Springer International Publishing, 2014, pp. 330-336.<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
\nMulticore – unsere Trainings & Coachings<\/h2>\n
\nMulticore – Fachwissen<\/h2>\n