FFT specific compilation on IBM Blue Gene

Abstract

Algorithmen zur digitalen Transformation von Signalen sind im Scientific Computing von größter Bedeutung und werden in zahlreichen Gebieten angewendet -- von der Echtzeit-Signalverarbeitung in eingebetteten Systemen bis zur numerischen Lösung partieller Differentialgleichungen im Rahmen komplexer Simulationen auf Supercomputern.<br />Die Entwicklung und Publikation der schnellen Fourier-Transformation (FFT) durch Cooley und Tukey leitete die Entwicklung einer neuen Klasse schneller Signalverarbeitungsalgorithmen ein, die -- im Gegensatz zur direkten Auswertung des entsprechenden Matrix-Vektor-Produktes -- nicht eine Berechnungskomplexität von $O(N 2)$, sondern nur von $O(N \log N)$ haben.<br />Für eine bestimmte Transformation gibt es aber nicht nur einen eindeutig bestimmten schnellen Algorithmus, sondern eine ganze Vielzahl äquivalenter Algorithmen. Diese Algorithmen unterscheiden sich nur unwesentlich im Hinblick auf ihren Rechenaufwand, umso mehr aber in ihrem Speicherzugriffsverhalten, was auf modernen Computersystemen mit ihren mehrstufigen Speicherhierarchien zu enormen Laufzeitunterschieden führen kann.<br />Automatische Performance-Tuning-Systeme, wie zum Beispiel die den State-of-the-art verkörpernden Signalverarbeitungs-Programmbibliotheken FFTW und SPIRAL, führen auf einem gegebenen Computersystem eine Suche nach dem optimalen Algorithmus im Raum aller äquivalenten Algorithmen und Implementierungen durch. Da der Output von Performance-Tuning-Systemen aber in Form von C-Code erfolgt, ist deren Leistung durch die Qualität der verfügbaren Compiler beschränkt.<br />Die vorliegende Arbeit stellt einen neu entwickelten Special-Purpose-Compiler vor, der für die Übersetzung laufzeitkritischer Codes existierende C Compiler ersetzt. Dieser Compiler, die Vienna MAP compiler tool-chain, besteht aus den folgenden Komponenten, die speziell den Bedürfnissen von Signalverarbeitungscodes angepasst sind: Der MAP Vectorizer extrahiert 2-weg SIMD-Parallelismus in numerischen Straight-Line-Codes. Der MAP Optimizer führt lokale Codeverbesserungen durch, wie sie von versierten Assembler-Programmierern manuell ausgeführt werden. Zuletzt erzeugt das MAP Backend Assemblercode für die Zielarchitektur.<br />Die wichtigste Ziel-Architektur des MAP-Compilers ist der IBM PowerPC 440 FP2 Prozessor, der in IBM Blue-Gene-Systemen -- den derzeit schnellsten Supercomputern der Welt -- eingesetzt wird.<br />FFTW-Grundroutinen, die mit Hilfe der Blue-Gene-Version des MAP-Compilers übersetzt werden, erreichen eine Effizienz von bis zu 80% und damit die dreifache Leistung jener Objekt-Codes, die von der aktuellsten Version des optimierenden IBM XL C Compilers erzeugt werden.<br />

Digital signal transforms are core algorithms in computational science and engineering, ranging from real-time signal processing in small-scale problems with stringent time constraints up to large-scale simulations based on partial differential equation solvers running on the world's largest supercomputers.<br />Starting with Cooley and Tukey's work on the fast Fourier transform (FFT), a vast class of fast signal transform algorithms has been developed, pushing the computational complexity down from $O(N 2)$ to $O(N \log N)$. In practice, however, there is not just one unique algorithm, but a large number of fast algorithms for computing one specific transform. These diverse algorithms are equivalent, but may differ significantly with regard to their memory access behavior, which causes tremendous runtime differences on all common-place machines with deep memory hierarchies.<br />Automatic performance tuning systems---like the state-of-the-art signal transform libraries FFTW and SPIRAL---search the space of suitable algorithms and implementations, automatically generating a large number of promising codes. To obtain the best performing code on a given target hardware, the search process is guided by empirical runtime measurements. However, as the program generators used in automatic performance tuning systems produce high-level C code, the performance of these systems is clearly limited by the quality of available compilers.<br />The thesis at hand presents a newly developed special-purpose compiler---the Vienna MAP compiler tool chain---as a replacement for general purpose high-level compilers in the context of automatic performance tuning systems. The MAP tool chain is composed of several generic components, consecutively focusing on specific properties of signal transform codes. The MAP vectorizer extracts 2-way SIMD-style parallelism out of numerical straight line code. The MAP optimizer performs local code improvements similar to the ones that experienced programmers would achieve by hand. Finally, the MAP backend produces assembly code for the specific target architecture.<br />The primary target architecture of the MAP compiler is IBM's PowerPC 440 FP2 processor used in all Blue Gene systems, currently being the fastest supercomputers worldwide. FFTW's core routines were compiled by the Blue Gene version of the MAP compiler. The resulting assembly code boasts an unprecedented performance---reaching a level of 80% efficiency. That way, MAP compiled codes are up to three times as fast as object codes obtained with the latest version of IBM's optimizing XL C compiler.