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

Im Bereich der Prozessorarchitekturen hat sich der Fokus neuer Entwicklungen von immer hoheren Taktfrequenzen hin zu immer mehr Kernen auf einem Chip verschoben. Eine hohe Kernanzahl ermoglicht es unterschiedlich leistungsfahige Kerne anzubieten, und sogar dedizierte Kerne mit speziellen Befehlssatzen. Die Entwicklung fur solch heterogene Plattformen ist herausfordernd und benotigt entsprechende Unterstutzung von Entwicklungswerkzeugen, wie beispielsweise Ubersetzern. Neben ihrer heterogenen Kernstruktur gibt es eine zweite Dimension, die die Entwicklung fur solche Architekturen anspruchsvoll macht: ihre Speicherstruktur. Die Aufrechterhaltung von globaler Cache-Koharenz erschwert das Erreichen hoher Kernzahlen. Hardwarebasierte Cache-Koharenz-Protokolle skalieren entweder schlecht, oder sind kompliziert und fuhren zu Problemen bei Ausfuhrungszeit und Energieeffizienz. Eine radikale Losung dieses Problems stellt die Abschaffung der globalen Cache-Koharenz dar. Jedoch ist es schwierig, bestehende Programmiermodelle effizient auf solch eine Hardware-Architektur mit schwachen Garantien abzubilden. Der erste Teil dieser Dissertation beschaftigt sich Datentransfertechniken fur nicht-cache-koharente Architekturen mit gemeinsamem Speicher. Diese Architekturen bieten einen gemeinsamen physikalischen Adressraum, implementieren aber keine hardwarebasierte Koharenz zwischen allen Caches des Systems. Die logische Partitionierung des gemeinsamen Speichers ermoglicht die sichere Programmierung einer solchen Plattform. Im Allgemeinen erzeugt dies die Notwendigkeit Daten zwischen Speicherpartitionen zu kopieren. Wir untersuchen die Ubersetzung fur invasive Architekturen, einer Familie von nicht-cache-koharenten 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 ubersetzergesteuerter automatischer software-basierter Koharenz, sodass er auch im Kontext nicht-koharenter Caches funktioniert. Wir prasentieren Implementierungen mehrerer Datentransfertechniken im Rahmen eines existierenden Ubersetzers und seines Laufzeitsystems. Wir fuhren eine ausfuhrliche Auswertung dieser Implementierungen auf einem FPGA-basierten Prototypen einer invasiven Architektur durch. Schlieslich schlagen wir vor, Hardwareunterstutzung fur bereichsbasierte Cache-Operationen hinzuzufugen und beschreiben und bewerten mogliche 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 wahrend der Programmubersetzung ist die Abbildung von Programmvariablen auf Maschinenregister. Wahrend der Registerzuteilung erzeugt der Ubersetzer Shuffle-Code, der aus Kopier- und Tauschbefehlen besteht, um Werte zwischen Registern zu transferieren. Abhangig von der Qualitat der Registerzuteilung und der Zahl der verfugbaren Register kann eine grose Menge an Shuffle-Code erzeugt werden. Wir schlagen vor, die Ausfuhrung 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 zunachst ein bestehendes RISC-Befehlsformat um Permutationsbefehle. Anschliesend beschreiben wir, wie die vorgeschlagenen Permutationsbefehle in einer bestehenden RISC-Architektur implementiert werden konnen. 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 Qualitats- und Korrektheitseingeschaften beider Ansatze und zeigen die Optimalitat des zweiten Ansatzes. Im Folgenden implementieren wir beide Codeerzeugungsverfahren in einem Ubersetzer und untersuchen sowie vergleichen deren Codequalitat ausfuhrlich mit Hilfe standardisierter Benchmarks. Zunachst messen wir die genaue Zahl der dynamisch ausgefuhrten Befehle, welche wir folgend validieren, indem wir Programmlaufzeiten auf einer FPGA-basierten Prototypimplementierung der um Permutationsbefehle erweiterten RISC-Architektur messen. Schlieslich argumentieren wir, dass Permutationsbefehle auf modernen Out-Of-Order-Prozessorarchitekturen, die bereits Registerumbenennung unterstutzen, mit wenig Aufwand implementierbar sind.