This thesis presents techniques tailor-made for the compilation of numerical straight line code: (i) Automatic 2-way SIMD vectorization extracts SIMD (Single Instruction Multiple Data) parallelism out of numerical straight line code in a way that guarantees a satisfactory level of SIMD utilization. (ii) Peephole optimization rewrites the SIMD vectorized code in a domain specific manner to further improve efficiency. (iii) Backend specific techniques are used for compiling the vectorized and optimized code, yielding object code whose performance is significantly better than the performance of code produced by general purpose compilers. The new compiler techniques presented in this thesis form the basis of the "MAP Vectorizer and Backend", a special purpose compiler, which was designed especially for the efficient vectorization and backend optimization of large basic blocks of numerical straight line code. MAP is currently applicable to the state-of-the-art performance tuning systems FFTW (Fastest Fourier Transform in the West}, SPIRAL (Signal Processing Algorithms Implementation Research for Adaptive Libraries) and ATLAS (Automatically Tuned Linear Algebra Software). Thus, MAP is covering a broad range of highly important algorithms in the fields of digital signal processing and numerical linear algebra. The experimental results were obtained using the MAP vectorizer and backend in connection with FFTW, SPIRAL and ATLAS.
en
In dieser Dissertation werden Techniken, die speziell die uebersetzung numerischer Routinen zum Ziel haben, vorgestellt. Die automatische 2-fach-SIMD- Vektorisierung entdeckt den in einer Routine vorhandenen SIMD-Parallelismus und garantiert einen zufriedenstellenden Grad der Nutzung von SIMD-Befehlen. Die Gucklock-Optimierung ersetzt bestimmte Kombinationen von Instruktionen durch effizientere. Fuer den letzten Teil der uebersetzung werden synthese-spefizische Techniken eingesetzt, die deutlich zur Steigerung der Qualitaet des uebersetzten Programmcodes -- ueber das Mass handelsueblicher uebersetzer hinaus -- beitragen. Die in dieser Dissertation praesentierten Konzepte stellen die Grundlage des Special Purpose Compilers MAP dar, der speziell fuer die effiziente Vektorisierung groesser numerischer Straight-Line-Codes entwickelt wurde. MAP unterstuetzt die fuehrenden automatischen Performance-Tuning-Softwareprodukte: FFTW (schnellste Fourier-Transformation des Westens), SPIRAL (Implementierungsforschung an Signalverarbeitungsalgorithmen fuer adaptive Software). und ATLAS (automatisch angepasste Software fuer Probleme der Linearen Algebra). Damit werden die wichtigsten Algorithmen der numerischen linearen Algebra und der digitalen Signalverarbeitung abgedeckt. Zu den praktischen Ergebnissen dieser Dissertation zaehlen: (i) die schnellsten derzeit verfuegbaren FFT-Codes fuer AMD Athlon basierte Systeme; (ii) automatisch erzeugte FFT-Codes fuer den Intel Pentium 4, die vergleichbare Leistung wie die schnellsten handoptimierten Codes liefern und (III) die schnellsten derzeit verfuegbaren FFT-Codes fuer den IBM PowerPC 440 FP2 Prozessor, der im derzeit von IBM entwickelten Supercomputer BlueGene/L Verwendung findet. Die experimentellen Resultate wurden durch Anwendung des MAP Special Purpose Compilers auf von FFTW, SPIRAL und ATLAS erzeugten Code erzielt.