Aspects of Code Generation and Data Transfer Techniques for Modern Parallel Architectures

Im Bereich der Prozessorarchitekturen hat sich der Fokus neuer Entwicklungen von immer höheren Taktfrequenzen hin zu immer mehr Kernen auf einem Chip verschoben.
Eine hohe Kernanzahl ermöglicht es unterschiedlich leistungsfähige Kerne anzubieten, und sogar dedizierte Kerne mit speziellen Befehlssätzen.
Die Entwicklung für solch heterogene Plattformen ist herausfordernd und benötigt entsprechende Unterstützung von Entwicklungswerkzeugen, wie beispielsweise Übersetzern.
Neben ihrer heterogenen Kernstruktur gibt es eine zweite Dimension, die die Entwicklung für solche Architekturen anspruchsvoll macht: ihre Speicherstruktur.
... mehr
Die Aufrechterhaltung von globaler Cache-Kohärenz erschwert das Erreichen hoher Kernzahlen.
Hardwarebasierte Cache-Kohärenz-Protokolle skalieren entweder schlecht, oder sind kompliziert und führen zu Problemen bei Ausführungszeit und Energieeffizienz.
Eine radikale Lösung dieses Problems stellt die Abschaffung der globalen Cache-Kohärenz dar.
Jedoch ist es schwierig, bestehende Programmiermodelle effizient auf solch eine Hardware-Architektur mit schwachen Garantien abzubilden.

Der erste Teil dieser Dissertation beschäftigt sich Datentransfertechniken für nicht-cache-kohärente Architekturen mit gemeinsamem Speicher.
Diese Architekturen bieten einen gemeinsamen physikalischen Adressraum, implementieren aber keine hardwarebasierte Kohärenz zwischen allen Caches des Systems.
Die logische Partitionierung des gemeinsamen Speichers ermöglicht die sichere Programmierung einer solchen Plattform.
Im Allgemeinen erzeugt dies die Notwendigkeit Daten zwischen Speicherpartitionen zu kopieren.

Wir untersuchen die Übersetzung für invasive Architekturen, einer Familie von nicht-cache-kohärenten Vielkernarchitekturen.
Wir betrachten die effiziente Implementierung von Datentransfers sowohl einfacher als auch komplexer Datenstrukturen auf invasiven Architekturen.
Insbesondere schlagen wir eine neuartige Technik zum Kopieren komplexer verzeigerter Datenstrukturen vor, die ohne Serialisierung auskommt.
Hierzu verallgemeinern wir den Objekt-Klon-Ansatz mit übersetzergesteuerter automatischer software-basierter Kohärenz, sodass er auch im Kontext nicht-kohärenter Caches funktioniert.
Wir präsentieren Implementierungen mehrerer Datentransfertechniken im Rahmen eines existierenden Übersetzers und seines Laufzeitsystems.
Wir führen eine ausführliche Auswertung dieser Implementierungen auf einem FPGA-basierten Prototypen einer invasiven Architektur durch.
Schließlich schlagen wir vor, Hardwareunterstützung für bereichsbasierte Cache-Operationen hinzuzufügen und beschreiben und bewerten mögliche Implementierungen und deren Kosten.

Der zweite Teil dieser Dissertation befasst sich mit der Beschleunigung von Shuffle-Code, der bei der Registerzuteilung auftritt, durch die Verwendung von Permutationsbefehlen.
Die Aufgabe der Registerzuteilung während der Programmübersetzung ist die Abbildung von Programmvariablen auf Maschinenregister.
Während der Registerzuteilung erzeugt der Übersetzer Shuffle-Code, der aus Kopier- und Tauschbefehlen besteht, um Werte zwischen Registern zu transferieren.
Abhängig von der Qualität der Registerzuteilung und der Zahl der verfügbaren Register kann eine große Menge an Shuffle-Code erzeugt werden.

Wir schlagen vor, die Ausführung von Shuffle-Code mit Hilfe von neuartigen Permutationsbefehlen zu beschleunigen, die die Inhalte von einigen Registern in einem Taktzyklus beliebig permutieren.
Um die Machbarkeit dieser Idee zu demonstrieren, erweitern wir zunächst ein bestehendes RISC-Befehlsformat um Permutationsbefehle.
Anschließend beschreiben wir, wie die vorgeschlagenen Permutationsbefehle in einer bestehenden RISC-Architektur implementiert werden können.
Dann entwickeln wir zwei Verfahren zur Codeerzeugung, die die Permutationsbefehle ausnutzen, um Shuffle-Code zu beschleunigen: eine schnelle Heuristik und einen auf dynamischer Programmierung basierenden optimalen Ansatz.
Wir beweisen Qualitäts- und Korrektheitseingeschaften beider Ansätze und zeigen die Optimalität des zweiten Ansatzes.
Im Folgenden implementieren wir beide Codeerzeugungsverfahren in einem Übersetzer und untersuchen sowie vergleichen deren Codequalität ausführlich mit Hilfe standardisierter Benchmarks.
Zunächst messen wir die genaue Zahl der dynamisch ausgeführten Befehle, welche wir folgend validieren, indem wir Programmlaufzeiten auf einer FPGA-basierten Prototypimplementierung der um Permutationsbefehle erweiterten RISC-Architektur messen.
Schließlich argumentieren wir, dass Permutationsbefehle auf modernen Out-Of-Order-Prozessorarchitekturen, die bereits Registerumbenennung unterstützen, mit wenig Aufwand implementierbar sind.

The focus of hardware architecture development has shifted from striving for ever higher clock frequencies towards incorporating an ever increasing number of cores on a single chip.
A high number of cores makes it possible to offer a mixture of weak and strong cores, and even specialized cores with completely different instruction sets.
This makes development for such a heterogeneous platform challenging and requires adequate support by tools, such as compilers.
Besides their core structure, there is a second dimension to these architectures: memory.
A major obstacle to scalability regarding the memory hierarchy of many-core platforms is maintaining global cache coherence.
... mehr
Hardware coherence protocols either scale poorly, or are complex and often suffer from performance and power overheads.
Abandoning global cache coherence is a radical solution to this problem.
However, efficiently mapping programming models to hardware with relaxed guarantees is challenging.
In this dissertation, we make contributions to compilation techniques targeting both dimensions of modern parallel architectures: memory and core structure.

The first part of this dissertation concerns data transfer techniques for non-cache-coherent architectures.
Such non-cache-coherent shared-memory architectures provide a shared physical address space, but do not implement hardware-based coherence between all caches of the system.
Logically partitioning the shared memory offers a safe way of programming such a platform.
In general, this creates the need to copy data between memory partitions.

We study the compilation to invasive architectures, a family of non-cache-coherent many-core architectures.
We investigate the efficient implementation of data transfers for both simple and complex data structures on these architectures.
Specifically, we propose a novel approach to copy complex pointered data structures without the need for serialization.
To this end, we generalize object cloning to work in the presence of non-coherent caches by extending object cloning with compiler-directed automatic software-managed coherence.
We present implementations of multiple data transfer techniques in an existing compiler and runtime system.
We extensively evaluate these implementations on an FPGA-based prototype of an invasive architecture.
Finally, we propose adding hardware support for range-based cache operations, and describe and evaluate possible implementations and overheads.

The second part of this dissertation concerns code generation techniques to accelerate shuffle code by using permutation instructions.
Shuffle code arises during register allocation, where the compiler maps program variables to machine registers.
The compiler may introduce shuffle code, consisting of copy and swap operations, to transfer data between registers.
Depending on the quality of register allocation and the number of available registers, a large amount of shuffle code may be generated.

We propose to speed up the execution of shuffle code by using permutation instructions that arbitrarily permute the contents of small sets of registers in one clock cycle.
To show the feasibility of this idea we first present an extension of an existing RISC instruction set with permutation instructions.
We then describe how to implement the proposed permutation instructions in an existing RISC architecture.
Subsequently, we develop two code generation schemes that exploit permutation instructions to implement shuffle code: a fast heuristic and a dynamic-programming-based approach.
We formally prove quality and correctness properties of both approaches and show the latter approach to be optimal.
In the following, we implement both code generation algorithms in a compiler and extensively evaluate and compare their code quality using a standardized benchmark suite.
We first measure precise dynamic instruction counts, which we then validate by measuring running times on an FPGA-based prototype implementation of the proposed RISC architecture with permutation instructions.
Finally, we argue that permutation instructions are cheap to implement on modern out-of-order architectures that already support register renaming.