Efficient utilization of vector extensions in microprocessors
| dc.contributor.advisor | Juurlink, Ben | |
| dc.contributor.advisor | Glesner, Sabine | |
| dc.contributor.author | Pohl, Angela | |
| dc.contributor.grantor | Technische Universität Berlin | en |
| dc.contributor.referee | Juurlink, Ben | |
| dc.contributor.referee | Glesner, Sabine | |
| dc.contributor.referee | Cosenza, Biagio | |
| dc.contributor.referee | Castrillon, Jeronimo | |
| dc.date.accepted | 2020-10-15 | |
| dc.date.accessioned | 2020-12-17T13:41:04Z | |
| dc.date.available | 2020-12-17T13:41:04Z | |
| dc.date.issued | 2020 | |
| dc.description.abstract | Since the early 1990s, microprocessors have been enhanced with vector extensions to exploit data-level parallelism in applications. Programs are sped up by applying the same instruction to multiple data elements, grouped in a vector, in parallel. Up to this day, efficient utilization of such vector extensions remains challenging, however. While manually transforming code to exploit vector registers and vector instructions yields high performance gains, the effort is significant. Automated approaches, such as those deployed by compilers, on the other hand, struggle to identify parallelism in applications or fail to find profitable code transformations. In this thesis, we present enhancements to auto-vectorizing compilers in order to close the performance gap between manually and automatically vectorized code. Our enhancements increase the number of automatically vectorizable code patterns, offer alternative transformation options that achieve higher performance than state of the art, and enable a comparison of different vectorization options. We thereby improve all steps of the vectorization process: the transformation of vectorizable code patterns, the mapping of abstract intermediate code to low-level instructions, and the profitability analysis of the transformation. Our first contribution is a different vector packing strategy for nested loops whose inner loops only perform few iterations. By changing the way vector elements are grouped together, we enable full vector utilization even for large vectors. Applying our approach to the two most compute-intense filters of the Versatile Video Codec decoder shows improvements of 24% on average over state-of-the-art auto-vectorization. The second contribution is a proposal for the vectorization of loops with control flow. We offer an alternative implementation for architectures that do not support masked store instructions, and introduce a technique to remove predicates from masked load instructions. While both approaches introduce overhead, we demonstrate their benefit for more than 10 loop kernels. For masked load instructions, the overhead is mitigated by the vectorized calculation and evaluation of the control flow condition. For masked store instruction, our solution outperforms state of the art for single-threaded applications, and is profitabel for multi-threaded programs when a minimum vectorization factor---depending on the arithmetic intensity of the kernel---is met. As a third contribution, we present an platform-independent cost model to assess the benefit of code vectorization. Its accurate performance prediction allows for the comparison of different vectorization options, and the compiler refrains from transforming code that will exhibit slowdowns after vectorization. Applying our cost model to three different evaluation platforms, we are able to show improvements with respect to the precision of the speedup prediction, the number of classification errors, and their impact on overall execution time. For example, our cost model improves the correlation between predicted and measured speedup of 99 loop kernels by 13% on an Intel AVX2 platform, thereby reducing the number of mispredictions by 46% and the total execution time by 3%. Overall, we are able to increase the performance of auto-vectorizing compilers by incrasing their vectorization rate, improving their vectorization quality, and reducing the number of mispredictions during their transformation profitability analysis. At the same time, we exploit the automatic and platform independent nature of compilers, thereby keeping the effort of code vectorization at a minimum. All of our approaches have been verified for compatibility with vector-length agnostic code generation, ensuring applicability to the programming model of future vector extensions. | en |
| dc.description.abstract | Seit Beginn der 90er Jahre werden Vektorerweiterungen in Mikroprozessoren eingesetzt, um Parallelität auf Datenebene in Programmen auszunutzen. Durch die gleichzeitige Verarbeitung mehrerer Daten mit derselben Instruktion erhofft man, die Ausführung des Programms zu beschleunigen. Allerdings werden die vorhandenen Vektorerweiterungen oft nicht effizient genutzt. Entweder muss Quellcode von Hand umgeschrieben werden, um die speziellen Register und Befehle zu verwenden, oder der vom Compiler erzeugte Code nutzt das Potential der Hardware nicht aus. In dieser Doktorarbeit wird untersucht, wie man die Rechenleistung von handoptimiertem Code erzielen kann, ohne jedoch den damit einhergehenden Aufwand spendieren zu müssen. Dabei erweitern wir die Vektorisierungsalgorithmen in Compilern derart, dass mehr Codemuster automatisch vektorisiert werden können und der transformierte Code eine höhere Rechenleistung erzielt. Außerdem ermöglichen wir den Vergleich unterschiedlicher Transformationsoptionen. Unsere Erweiterungen verbessern alle Verarbeitungsschritte der Code-Vektorisierung: die Transformation von skalaren in vektoriellen Code, das Abbilden der abstrakten Programmdarstellung auf Maschinensprache, sowie die Kosten-Nutzen-Analyse der vorgenommenen Vektorisierung. Insgesamt präsentieren wir in dieser Arbeit drei Compilererweiterungen für die automatische Code-Vektorisierung. Die erste Erweiterung beschäftigt sich mit der Vektorisierung von verschachtelten Schleifen, deren innere Schleifen nur wenige Durchläufe ausführen. Bei der automatischen Vektorisierung dieser Codemuster werden insbesondere große Vektoren, die viele Datenelemente parallel speichern und verarbeiten können, bislang nicht ausreichend ausgelastet. Wir ändern daher die Art und Weise, wie Datenelemente in diesen Vektoren angeordnet werden. Die Vektorisierung der zwei rechenintensivsten Filter des Dekodierers des Versatile Video Codec zeigt, dass die Ausführungszeit des Programms mit unserem Ansatz im Durchschnitt um 24% verringert werden kann. Die zweite Erweiterung, die wir präsentieren, verbessert die Vektorisierung von Schleifen, die Kontrollstrukturen enthalten. Wir stellen eine alternative Möglichkeit vor, die bedingte Befehlsausführung für Speicherinstruktionen in Maschinensprache zu implementieren. Außerdem zeigen wir, wie die Lesezugriffsrechte für alle Datenelemente eines Vektor zur Laufzeit sichergestellt werden können. Die Evaluierung unserer Methoden bestätigt, dass der Mehraufwand, der durch die Überprüfung der Lesezugriffsrechte zur Laufzeit entsteht, durch die parallele Betrachtung mehrerer Datenelemente aufgehoben wird. Bei der Betrachtung von 10 Schleifen mit Kontrollstrukturen zeigt sich außerdem, dass Schreibzugriffe um ein Vielfaches beschleunigt werden können, wenn ein Mindestanzahl an parallelen Datenelementen garantiert werden kann (VF > 4). Die dritte Erweiterung ist ein neues Kostenmodell für die Kosten-Nutzen-Analyse von Vektorisierungen. Durch die genaue Vorhersage der zu erwartenden Beschleunigung wird es dem Compiler ermöglicht, verschiedene Transformationsoptionen miteinander zu vergleichen. Außerdem verhindert es die Umsetzung von Transformationen, die die Rechenleistung negativ beeinflussen. Unser Kostenmodell wurde auf drei unterschiedlichen Plattformen untersucht und auf allen dreien wurden Verbesserungen erzielt. Diese Verbesserungen betreffen die Genauigkeit der Beschleunigungsvorhersage, die Anzahl der fehlerhaften Vorhersagen, sowie die Ausführungszeit. Zum Beispiel konnten wir auf einer Intel AVX2 Hardware die Korrelation zwischen vorhergesagter und gemessener Beschleunigung von 99 Testcodes um 13% verbessern, wodurch sich die Anzahl der falsch vorhergesagten Beschleunigungen um 46% und die Ausführungszeit um 3% verringerte. Insgesamt können durch die vorgestellten Erweiterungen mehr Codemuster besser vektorisiert werden. Gleichzeitig vermeiden wir fehlerhafte Prognosen bezüglich der zu erwartenden Beschleunigung und ermöglichen den Vergleich unterschiedlicher Vektorisierungsoptionen. Der Aufwand zur Nutzung unserer Verbesserungen ist für den Programmierer minimal, da die Erweiterungen automatisch während des Kompilierens angewendet werden. Zusätzlich sind alle vorgestellten Ansätze auch für die Generierung von vector-length agnostic Code geeignet, der für die effiziente Ausnutzung von Vektorerweiterungen der nächsten Generation benötigt wird. | de |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/11929 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-10820 | |
| dc.language.iso | en | en |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-sa/4.0/ | en |
| dc.subject.ddc | 620 Ingenieurwissenschaften und zugeordnete Tätigkeiten | de |
| dc.subject.ddc | 005 Computerprogrammierung, Programme, Daten | de |
| dc.subject.other | SIMD | en |
| dc.subject.other | Vectorization | en |
| dc.subject.other | Compiler | en |
| dc.subject.other | VLA | en |
| dc.subject.other | SVE | en |
| dc.subject.other | Vektorisierung | de |
| dc.subject.other | Kompilierer | de |
| dc.title | Efficient utilization of vector extensions in microprocessors | en |
| dc.title.translated | Effiziente Nutzung von Vektorerweiterungen in Mikroprozessoren | de |
| dc.type | Doctoral Thesis | en |
| dc.type.version | acceptedVersion | en |
| tub.accessrights.dnb | free | en |
| tub.affiliation | Fak. 4 Elektrotechnik und Informatik::Inst. Technische Informatik und Mikroelektronik | de |
| tub.affiliation.faculty | Fak. 4 Elektrotechnik und Informatik | de |
| tub.affiliation.institute | Inst. Technische Informatik und Mikroelektronik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |