Inferring and analyzing microarchitectural performance models

Abstract

Modern processors are complex systems that employ a wide range of techniques to execute programs as fast and efficiently as possible. However, these hardware intricacies make reasoning about the efficiency of code for the processor difficult. Microarchitectural performance models are therefore indispensable for estimating and improving how efficiently software takes advantage of the hardware. This dissertation presents several advancements in the field of microarchitectural performance modeling. The first part of this thesis proposes techniques to characterize how a processor exploits instruction-level parallelism. Based on a formal model, we explore ways to infer a processor's port mapping from throughput measurements, i.e., how it splits instructions into micro-operations and how these are executed on the processor's functional units. Our techniques enable accurate port mapping inference for processors that prior methods could not reason about. In the second part, we introduce AnICA, a method to analyze inconsistencies between performance models. AnICA takes inspiration from differential testing and abstract interpretation to systematically characterize differences in the outputs of basic block throughput predictors. It can summarize thousands of inconsistencies in a few dozen descriptions that provide high-level insights into the differing behaviors of such predictors. These results have lead to improvements in the scheduling models of the widely used LLVM compiler infrastructure.

Moderne Prozessoren sind komplexe Systeme, die ein breites Spektrum an Techniken anwenden, um Programme so schnell und effizient wie möglich auszuführen. Diese Komplexität der Hardware erschwert jedoch auch das Abschätzen der Effizienz von Programmen für den jeweiligen Prozessor. Um die Hardware-Ausnutzung von Programmen zu beurteilen und zu verbessern, sind daher Leistungsmodelle nötig. Diese Dissertation präsentiert mehrere Beiträge zum Feld der Leistungsmodellierung von Prozessoren. Der erste Teil der Dissertation untersucht die Ausnutzung von Parallelität auf Anweisungsebene innerhalb eines Prozessors. Basierend auf einem formalen Modell leiten wir aus Durchsatzmessungen ab, wie der Prozessor Anweisungen in Mikro-Operationen aufteilt und wie diese von den funktionalen Einheiten des Prozessors ausgeführt werden. Die präsentierten Methoden charakterisieren dieses Verhalten erstmals für eine Reihe von Prozessoren. Der zweite Teil der Arbeit stellt AnICA vor, ein Verfahren zur Untersuchung von Inkonsistenzen zwischen Leistungsmodellen. AnICA vereint differenzielles Testen mit Konzepten der abstrakten Interpretation, um Unterschiede in den Ergebnissen von Durchsatzmodellen für Anweisungssequenzen zu charakterisieren. Tausende von Inkonsistenzen werden so durch wenige kompakte Beschreibungen zusammengefasst, die direkte Einsichten in die Durchsatzmodelle liefern. Durch diese Ergebnisse konnten Code-Generierungs-Modelle der LLVM Compiler-Infrastruktur verbessert werden.