TU Darmstadt / ULB / TUprints

An Execution Model and High-Level-Synthesis System for Generating SIMT Multi-Threaded Hardware from C Source Code

Huthmann, Jens Christoph (2017)
An Execution Model and High-Level-Synthesis System for Generating SIMT Multi-Threaded Hardware from C Source Code.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

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

Download (2MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: An Execution Model and High-Level-Synthesis System for Generating SIMT Multi-Threaded Hardware from C Source Code
Language: English
Referees: Koch, Prof. Dr. Andreas ; Berekovic, Prof. Dr. Mladen
Date: 2017
Place of Publication: Darmstadt
Date of oral examination: 21 August 2017
Abstract:

The performance improvement of conventional processor has begun to stagnate in recent years. Because of this, researchers are looking for new possibilities to improve the performance of computing systems. Heterogeneous systems turned out to be a powerful possibility. In the context of this thesis, a heterogeneous system consists of a software-programmable processor and a FPGA based configurable hardware accelerator. By using an accelerator specifically tailored to a particular application, heterogeneous system can achieve a higher performance that conventional processors.

Due to their increased complexity, it is more complicated to develop applications for heterogeneous systems than for conventional systems based on a software-programmable processor. For programming the software and hardware parts, different languages have to be used and additional specialised hardware-knowledge is required. Both factors increase the development cost.

This work presents the compiler framework Nymble which allows to program a heterogeneous system with only a single high-level language. In the high-level language the developer only has to select which parts of the application should be executed in hardware. Nymble then generates a program for the software-processor, the configuration of the hardware, and all interfaces between software and hardware.

All heterogeneous systems supported by Nymble have in common that the software and hardware parts of an application have access to a shared memory. As this memory is external RAM with high access latency, it is necessary to insert a cache between the memory and hardware. With this cache, memory accesses can vary between very short or long access latency depending on whether the data is available in the cache.

To hide long latencies, this thesis presents a novel execution model which allows the simultaneous execution of multiple threads in a single accelerator. Additionally, the model enables threads to be dynamically reordered at specific points in the common accelerator pipeline. This capability is used to let other (non-waiting) threads overtake a thread which is waiting for a memory access. Thus, these other threads can execute their calculations independently of the waiting thread to bridge the latency of memory accesses.

Previous works are using execution models which only allow a single thread to be active in the accelerator. In case of a memory access with long latency, the thread is exchanged with another non-waiting thread. This design of the hardware often causes many resources to lie idle for a significant amount of time.

In contrast, the presented novel execution model dynamically spreads multiple threads over the pipeline. This results in a higher utilisation of the resources by using resources more effectively. Furthermore, the simultaneous execution of multiple threads can achieve similar throughput as multiple copies of a single-threaded accelerator running in parallel.

The new execution model makes it possible to combine the improved throughput of multiple copies with the increased efficiency of simultaneous threads in a single accelerator. Thread reordering allows the new model to be effectively used with a cached shared-memory.

In comparison, between four copies of a single-threaded accelerator and a multi-thread accelerator with four thread (both created by Nymble), a resource efficiency of up to factor 2.6x can be achieved. At the same time, four simultaneous threads can be up to 4x as fast as four threads executed consecutively on a single accelerator. Compared to other, more optimised compilers, Nymble can still achieve up to 2x faster runtime with 1.5x resource efficiency.

Alternative Abstract:
Alternative AbstractLanguage

Da bei der Leistung von herkömmlichen Prozessoren in den vergangenen Jahren eine Stagnation bei der Verbesserung der Leistung zu verzeichnen war, wurde nach neuen Möglichkeiten gesucht die Leistung von Computersystemen zu steigern.

Heterogene Systeme haben sich als eine leistungsfähige Alternative herausgestellt. Im Kontext dieser Arbeit besteht ein heterogenes System in der Regel aus einem mit Software programmierbaren Prozessor und einem konfigurierbarem Hardwarebeschleuniger. Durch den für jede Anwendung speziell konfigurierten Hardwarebeschleuniger können heterogene Systeme eine bessere Leistung als ein herkömmlicher Prozessor erreichen.

Wegen ihrer größeren Komplexität ist es schwieriger für heterogene Systeme Anwendungen zu entwickeln als für ein herkömmliches, rein auf einem Software-Prozessor basiertem System. Da zur Programmierung der Soft- und Hardwareanteile verschiedene Sprachen verwendet werden müssen und zusätzliche, spezialisierte Hardware-Kenntnisse erforderlich sind, erhöht dies die Kosten der Entwicklung.

Diese Arbeit stellt das Compilerframework Nymble vor, welches es ermöglicht, ein heterogenes System allein mit einer Hochsprache zu programmieren. Nachdem der Entwickler in der Hochsprache festgelegt hat welche Teile in Hardware ausgeführt werden sollen, erzeugt Nymble ein Programm für den Prozessor, die Hardwarekonfiguration und alle Schnittstellen zwischen der Soft- und Hardware.

Alle von Nymble unterstützen Systeme haben gemeinsam, dass sich der Software- und Hardwareteil einer Anwendung einen gemeinsamen Speicher teilen. Da es sich bei dem Speicher um externen RAM mit hoher Zugriffslatenz handelt, ist es notwendig ein Cachesystem zwischen Speicher und Hardware einzufügen. Dies sorgt dafür, dass Speicherzugriffe zwischen sehr kurzer oder langer Latenz variieren können, in Abhängigkeit davon ob die Daten bereits im Cache verfügbar sind.

Um potentielle lange Latenzen zu überbrücken, präsentiert diese Arbeit ein innovatives Ausführungsmodell, das die simultane Ausführung mehrerer Threads in einem gemeinsamen Hardwarebeschleuniger erlaubt. Zusätzlich ermöglicht das Modell, an bestimmten Punkten in der gemeinsamen Pipeline die Reihenfolge der Threads dynamisch zu ändern. Diese Fähigkeit wird dazu verwendet, dass ein Thread, welcher auf einen Speicherzugriff warten muss, durch andere nicht wartende Threads überholt werden kann. Dadurch können diese unabhängig vom wartenden Threads ihre Berechnungen ausführen und so Latenzen überbrücken.

Bisherige Arbeiten verwendeten ein Ausführungsmodell, in dem jeweils nur ein Thread im Hardwarebeschleuniger aktiv sein konnte und im Falle eines Speicherzugriffs durch einen anderen Thread ausgetauscht wurde. Durch den Aufbau der Hardware kam es hier oft dazu, dass viele der Ressourcen einen signifikanten Anteil der Laufzeit brach lagen.

Durch seinen innovativen Aufbau verteilt das neue Ausführungsmodell mehrere Threads dynamisch über die Pipeline. Dadurch werden mehr Ressourcen gleichzeitig sinnvoll genutzt und eine bessere Auslastung erreicht. Weiter erreicht das simultane Ausführen mehrerer Threads einen ähnliche Durchsatz wie mehrere simultan ausgeführte Kopien eines Hardwarebeschleunigers, welcher jeweils nur einen Thread unterstützt.

Das neue Ausführungsmodell macht es möglich, den erhöhten Durchsatz mit einer verbesserten Effizienz zu kombinieren. Durch das gegenseitige Überholen von Threads ist es möglich das neue Modell effektiv mit einem geteilten Speicher über einen Cache zu verwenden.

Im Vergleich, zwischen vier Kopien eines Beschleunigers für jeweils einen Thread und einem Beschleuniger für vier Threads (beide durch Nymble erzeugt), wird eine Ressourceneffizienz von bis zu Faktor 2,6x erreicht. Dabei sind vier simultane Threads bis annähernd 4x mal so schnell wie vier auf einem Beschleuniger sequentiell ausgeführte Threads. Verglichen mit anderen, besser optimierten Compilern, erreicht Nymble immer noch eine bis zu 2x bessere Laufzeit mit einer 1,5x Ressourceneffizienz.

German
URN: urn:nbn:de:tuda-tuprints-67767
Classification DDC: 000 Generalities, computers, information > 004 Computer science
600 Technology, medicine, applied sciences > 620 Engineering and machine engineering
Divisions: 20 Department of Computer Science
20 Department of Computer Science > Embedded Systems and Applications
Date Deposited: 28 Nov 2017 12:56
Last Modified: 09 Jul 2020 01:51
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/6776
PPN: 423389904
Export:
Actions (login required)
View Item View Item