TU Darmstadt / ULB / TUprints

Automatically Parallelizing Embedded Legacy Software on Soft-Core SoCs

Heid, Kris (2019)
Automatically Parallelizing Embedded Legacy Software on Soft-Core SoCs.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
Text
2019_08_23_Heid_Kris.pdf
Copyright Information: CC BY-NC-ND 4.0 International - Creative Commons, Attribution NonCommercial, NoDerivs.

Download (910kB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Automatically Parallelizing Embedded Legacy Software on Soft-Core SoCs
Language: English
Referees: Hochberger, Prof. Dr. Christian ; Castrillon, Prof. Dr. Jeronimo
Date: 2019
Place of Publication: Darmstadt
Date of oral examination: 2019
Abstract:

Nowadays, embedded systems are utilized in many areas and become omnipresent, making people's lives more comfortable. Embedded systems have to handle more and more functionality in many products. To maintain the often required low energy consumption, multi-core systems provide high performance at moderate energy consumption. The development started with dual-core processors and has today reached many-core designs with dozens and hundreds of processor cores. However, existing applications can barely leverage the potential of that many cores.

Legacy applications are usually written sequentially and thus typically use only one processor core. Thus, these applications do not benefit from the advantages provided by modern many-core systems. Rewriting those applications to use multiple cores requires new skills from developers and it is also time-consuming and highly error prone. Dozens of languages, APIs and compilers have already been presented in the past decades to aid the user with parallelizing applications. Fully automatic parallelizing compilers are seen as the holy grail, since the user effort is kept minimal. However, automatic parallelizers often cannot extract parallelism as good as user aided approaches. Most of these parallelization tools are designed for desktop and high-performance systems and are thus not tuned or applicable for low performance embedded systems. To improve this situation, this work presents an automatic parallelizer for embedded systems, which is able to mostly deliver better quality than user aided approaches and if not allows easy manual fine-tuning.

Parallelization tools extract concurrently executable tasks from an application. These tasks can then be executed on different processor cores. Parallelization tools and automatic parallelizers in particular often struggle to efficiently map the extracted parallelism to an existing multi-core processor. This work uses soft-core processors on FPGAs, which makes it possible to realize custom multi-core designs in hardware, within a few minutes. This allows to adapt the multi-core processor to the characteristics of the extracted parallelism. Especially, core-interconnects for communication can be optimized to fit the communication pattern of the parallel application.

Embedded applications are often structured as follows: receive input data, (multiple) data processing steps, data output. The multiple processing steps are often realized as consecutive loosely coupled transformations. These steps naturally already model the structure of a processing pipeline. It is the goal of this work to extract this kind of pipeline-parallelism from an application and map it to multiple cores to increase the overall throughput of the system. Multiple cores forming a chain with direct communication channels ideally fit this pattern. The previously described, so called pipeline-parallelism is a barely addressed concept in most parallelization tools. Also, current multi-core designs often do not support the hardware flexibility provided by soft-cores, targeted in this approach.

The main contribution of this work is an automatic parallelizer which is able to map different processing steps from the source-code of a sequential application to different cores in a multi-core pipeline. Users only specify the required processing speed after parallelization. The developed tool tries to extract a matching parallelized software design along with a custom multi-core design out of sequential embedded legacy applications. The automatically created multi-core system already contains used peripherals extracted from the source-code and is ready to be used. The presented parallelizer implements multi-objective optimization to generate a minimal hardware design, just fulfilling the user defined requirement. To the best of my knowledge, the possibility to generate such a multi-core pipeline defined by the demands of the parallelized software has never been presented before.

The approach is implemented for two soft-core processors and evaluation shows for both targets high speedups of 12x and higher at a reasonable hardware overhead. Compared to other automatic parallelizers, which mainly focus on speedups through latency reduction, significantly higher speedups can be achieved depending on the given application structure.

Alternative Abstract:
Alternative AbstractLanguage

Eingebettete Systeme werden heutzutage in vielen Bereich eingesetzt, um unseren Alltag zu erleichtern. Hierbei übernehmen diese immer mehr Aufgaben. Um die wachsende Anzahl an Aufgaben erledigen zu können werden Mehrkernprozessoren benötigt, welche eine hohe Leistungsfähigkeit bei gleichzeitig moderatem Energiebedarf bieten. Waren die ersten Mehrkernprozessoren noch mit zwei Rechenkernen ausgestattet, so existieren heute bereits Prozessoren mit dutzenden und hunderten Rechenkernen. Viele bestehende Anwendungen können jedoch ohne Anpassungen kaum von dieser hohen Anzahl an Rechenkernen profitieren.

Existierende Anwendungen haben meist einen sequenziellen Programmablauf und nutzen daher per se nur einen einzigen Rechenkern. Somit können sie nicht von den Vorteilen und der Rechenleistung moderner Prozessoren profitieren. Die Anwendungen müssten umgeschrieben werden, um das volle Potenzial von Mehrkernprozessoren zu nutzen, was jedoch neue Fertigkeiten und Denkmuster von Entwicklern fordert und zudem sehr mühsam und fehleranfällig ist. In den letzten Jahren wurden bereits eine Reihe an Programmiersprachen, Programmierschnittstellen und Compilern entwickelt, um Entwickler bei der Parallelisierung zu unterstützen. Dabei sind vollständig automatische Parallelisierer der heilige Gral der Parallelisierung, da sie dem Nutzer den Großteil der Arbeit abnehmen. Automatische Parallelisierer können jedoch teilweise nicht die Qualität der einer manuellen Parallelisierung von erfahrenen Entwicklern erreichen. Die Meisten der entwickelten Parallelisierungswerkzeuge sind außerdem für Desktop- oder Hochleistungsrechner entworfen worden und sind daher kaum an die Bedürfnisse eingebetteter Systeme angepasst. Daher wird in dieser Arbeit ein automatischer Parallelisierer für eingebettete Systeme vorgestellt, welcher oftmals die Qualität manueller Parallelisierungen übertrifft und auf Wunsch manuelle Anpassungen erlaubt.

Parallelisierungswerkzeuge sind in der Lage parallel ausführbare Aufgaben aus einer Anwendung zu extrahieren und diese dann auf verschiedenen Prozessorkernen auszuführen. Vor allem automatische Parallelisierer haben jedoch oft Probleme den gefundenen Parallelismus effizient auf die verfügbare beschränkte Anzahl an Kernen abzubilden. Daher werden in dieser Arbeit Soft-Core Prozessoren auf FPGAs verwendet, welche es ermöglichen ein angepasstes Mehrkernsystem innerhalb weniger Minuten zu realisieren. Hierdurch kann das System auf die Charakteristiken des extrahierten Parallelismus angepasst werden. Besonders die Kommunikationsinfrastruktur kann speziell auf das Kommunikationsmuster der parallelisierten Anwendung angepasst werden.

Anwendungen eingebetteter Systeme haben oftmals die folgende Struktur: Eingangsdaten empfangen, Verarbeitung der Daten (in mehreren Schritten), Ausgabe der Daten. Die verschiedenen Verarbeitungsschritte sind hierbei meist nur locker gekoppelte aufeinanderfolgende Transformationen der Daten. Die beschriebenen Schritte weisen somit die Struktur eine Verarbeitungs-Pipeline auf. Daher ist das Ziel dieser Arbeit diesen sogenannten Pipeline-Parallelismus aus der Anwendung zu extrahieren. Die einzelnen Verarbeitungsschritte werden dann zur Erhöhung des Datendurchsatzes auf verschiedene Kerne abgebildet. Hierbei passt eine Kette von Prozessorkernen mit direkter Kommunikation zwischen den Nachbarn ideal zur Charakteristik des extrahierten Pipeline-Parallelismus. Das Konzept des Pipeline-Parallelismus ist in heutigen Parallelisierungswerkzeugen eher selten vorzufinden, was auch daran liegt, dass aktuelle Mehrkernsysteme nicht die benötigte Struktur bzw. Flexibilität von Soft-Cores bieten, um die Pipeline-Muster ideal abzubilden.

Der Beitrag dieser Arbeit ist ein automatischer Parallelisierer, welcher in der Lage ist aus einer sequentiellen Anwendung Pipeline-Parallelismus zu extrahieren und diesen auf eine zuvor beschriebene Kette von Prozessorkernen abzubilden. Der Nutzer muss lediglich eine Verarbeitungsgeschwindigkeit vorgeben, welche die parallelisierte Anwendung erreichen soll. Der Parallelisierer extrahiert anschließend den nötigen Parallelismus aus der Anwendung und erstellt automatisch ein individuell angepasstes Mehrkernsystem. In diesem System sind neben der Kommunikationsinfrastruktur auch bereits alle genutzten Peripherien enthalten, sodass es direkt einsatzbereit ist. Der Parallelisierer optimiert das System in verschiedenen Aspekten, um möglichst minimale Hardware zu generieren, die dennoch den Nutzervorgaben entspricht. Die Generierung einer Mehrkern-Pipeline, die individuell auf die parallelisierte Anwendung angepasst ist, wurde nach meinem besten Wissen noch nicht veröffentlicht.

Das Konzept wurde für zwei Soft-Core Prozessoren implementiert und die Evaluation weist einen hohen möglichen Geschwindigkeitszuwachs des Faktors 12 und mehr, bei moderat erhöhtem Hardwarebedarf auf. Im Vergleich zu anderen automatischen Parallelisierern, die sich lediglich auf eine Erhöhung des Durchsatzes durch Verringerung der Latenz fokussieren, kann ein weitaus höherer Geschwindigkeitszuwachs erreicht werden, falls die Anwendung die nötigen Charakteristiken aufweist.

German
URN: urn:nbn:de:tuda-tuprints-90205
Classification DDC: 600 Technology, medicine, applied sciences > 620 Engineering and machine engineering
Divisions: 18 Department of Electrical Engineering and Information Technology > Institute of Computer Engineering > Computer Systems Group
Date Deposited: 03 Sep 2019 14:24
Last Modified: 03 Sep 2019 14:24
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/9020
PPN: 453880541
Export:
Actions (login required)
View Item View Item