Übersetzertechnologie zur Hochleistungs-Signaltransformation

Seit der Entdeckung der schnellen Fouriertransformation durch Cooley und Tukey im Jahr 1965 sind schnelle Signaltransformationsalgorithmen ein integraler Bestandteil naturwissenschaftlicher Anwendungen. Durch die Verbreitung mehrstufiger Speicherhierarchien seit etwa 10 Jahren hat sich der Forschungsschwerpunkt in diesem Gebiet grundlegend veraendert: War bis dahin die Reduktion der Anzahl arithmetischer Operationen vorrangig, so dominieren jetzt Speicherzugriffskosten die Gesamtkosten. Dieser Hardwaretrend fuehrte zur Entstehung eines neuen Softwareparadigmas, des Automatic-Performance-Tuning. Fuehrende Automatic-Performance-Tuning-Software auf dem Gebiet der Signal-transformationen -- wie z. B. SPIRAL oder das mit dem Wilkinson-Preis ausgezeichnete FFTW -- beschritten in zweierlei Hinsicht neue Wege: (1) Die Loesung von Problemen wird in zwei klar getrennte Bereiche -- suchbasierte automatische Adaptierung, die den effizientesten Algorithmus zur Loesung eines bestimmten Problems auf einer gegebenen Zielplatform ermittelt, sowie den eigentlichen Loesungsprozess - unterteilt. (2) Beide Systeme verwenden domaenenspezifische Code- Generatoren zur automatischen Erzeugung der benoetigten Grundroutinen. Um Portabilitaet zu erreichen, erzeugen die Code-Generatoren dieser Systeme C-Code. In Experimenten hat sich jedoch herausgestellt, dass die von verfuegbaren Compilern erzeugten Assembler-Codes hinsichtlich ihrer Qualitaet handgeschriebenen Codes unterlegen sind. Um diese Luecke zu schliessen wurde im Jahr 2000 das Special- Purpose-Compiler-Projekt MAP initiiert. Anders als allgemeine Compiler nutzt der MAP-Compiler domaenenspezifisches Wissen und konzentriert sich auf die diesem Gebiet wichtigsten Aspekte der Code- Erzeugung, und generiert so Assembler-Code bisher unerreichter Guete. Bis 2006 gab es zwei Zielarchitekturen: (1) x86-kompatible Prozessoren und (2) Prozessoren der IBM Blue-Gene Supercomputer. Die zweite Variante war eine der wichtigsten, leistungssteigernden Komponenten des materialwissenschaftlichen Simulations-programmes Qbox -- dem Gewinner des ACM Gordon-Bell-Preis 2006. Das beantragte Projekt soll die bisher schon sehr erfolgreiche Entwicklung konsequent weiterfuehren: Zunaechst soll der Schwerpunkt auf die von Notebooks bis zu Supercomputern verbreiteten AMD64-kompatiblen Prozessorarchitekturen gelegt werden. Neue Methoden zur Nutzung von vierfachen SIMD- Instruktionssatzerweiterungen und neue Techniken zur verbesserten Speicherzugriffseffizienz sind zu erarbeiten und werden in den MAP-Compiler einfliessen. Die fuer einen Zeitrahmen von 24 Monaten geplanten Aktivitaeten zielen auf die Erreichung klar definierter Meilensteine in drei Bereichen ab: Compilertechnologie, Compiler- Implementierung und Signal-transformationssoftware. Die geplanten Entwicklungen werden besonders die Leistung naturwissenschaftlicher Anwendungssoftware, die grosse Datenmengen zu verarbeiten hat, deutlich steigern.

Diskrete Signaldaten spielen sowohl bei numerischen Simulationen als auch bei Audio/Video-Multimedia- Anwendungen eine bedeutende Rolle. Die möglichst effiziente Verarbeitung dieser Daten erfolgt mit Hilfe hochoptimierter Programmbibliotheken, die aus einer passenden Sammlung problemspezifischer Programm- Routinen bestehen. Für gute Wartbarkeit und Übertragbarkeit auf verschiedene Systeme sind diese Programm-Routinen meist in einer "Hochsprache" wie C oder Fortran verfasst. Ein optimierendes "Übersetzer"-Programm (compiler) erzeugt aus Hochsprachen-Code "Maschinencode" für die konkrete Prozessor-Zielarchitektur und führt eine Reihe von Optimierungsschritten durch, um Laufzeit und Codegröße zu minimieren. Im Rahmen dieses Forschungsprojekts wurden verschiedene, neue Optimierungstechniken für Codes zur diskreten Signalverarbeitung auf Intel64/AMD64 Prozessoren entwickelt und in einem Übersetzer-Programm namens "NXyn" implementiert. "NXyn" arbeitet auf der Ebene von Intel64/AMD64-Maschinencode, was eine einfache Kombination mit etablierten optimierenden Übersetzern wie zum Beispiel dem proprietären Intel C Compiler "icc" ermöglicht. Bei der Verarbeitung von Signalverarbeitungscodes der weit verbreiteten Programmbibliothek "FFTW", die mit "Intel icc" zu Maschinencode übersetzt wurden, wurden mit den Techniken, die im Rahmen dieses Projekts erarbeitet wurden, Verbesserungen der Codegröße und Laufzeit von bis zu 30% erzielt. Experimente zeigen die Eignung der entwickelten Techniken für unterschiedliche Intel64/AMD64 Prozessoren (Intel Core 2, Intel Core i3, AMD Phenom, AMD Phenom II). Intel64/AMD64 Prozessoren finden breite Verwendung in mobilen Internetgeräten (MIDs), am Arbeitsplatz (Notebook und Desktop-PC), in Rechenzentren (Server), und in Hochleistungsrechnern (Supercomputer): Ende 2010 kamen sie bei knapp einer Milliarde PCs und bei mehr als 80% der Top500-Supercomputer zum Einsatz.