Verbesserung der Effizienz für iterative numerische Algorithmen auf modernen Architekturen

For many numerical codes the transport of data from main memory to the registers is commonly considered to be the main limiting factor to achieve high performance on present micro architectures. This fact is referred to as the memory wall. A lot of research is targeting this point on different levels. This covers for example code transformations and architecture aware data structures to achieve an optimal usage of the memory hierarchy found in all present micro architectures. This work shows that on modern micro architectures it is necessary to also take the requirements of the Single Instruction Multiple Data (SIMD) programming paradigm and data prefetching into account to reach high efficiencies. In this thesis the chain from high level algorithmic optimizations over the code generation process involving the compiler and the limitations and influences of the instruction set architecture down to the micro architecture of the underlying hardware are analyzed. As a result we present a strategy to achieve a high efficiency for memory bandwidth limited algorithms on modern architectures. The success of this strategy is shown on the algorithmic class of grid based numerical linear equation solvers: A 2D Red-Black Gauss-Seidel smoother implementation for the x86/x86-64 architecture and a 3D multigrid implementation for the IA64 architecture.Für viele numerischen Programme wird der Transport der Daten vom Hauptspeicher in die Register als der wichtigste leistungbegrenzende Einfluss angesehen um hohe Leistung auf derzeitigen Mikroarchitekturen zu erreichen. Diese Tatsache wird oft als memory wall bezeichnet. Umfassende Forschungsprojekte beschäftigen sich mit diesem Punkt auf unterschiedlichen Ebenen. Dies beinhaltet z.B. Programmcodetransformationen und auf die Architektur zugeschnittene Datenstruktur um eine bestmögliche Nutzung der Speicherhierachie auf derzeitigen Mikroarchitekturen zu erreichen. Dies vorliegende Arbeit zeigt, das es auf modernen Mikroarchitekturen notwendig ist auch die Anforderungen von SIMD und Datenvorausladetechniken zu beachten um ein hohe Effizienz zu erreichen. In dieser Dissertation wird die Kette von der Optimierungen auf Hochsprachenebene über den Programmcodegenerierungsprozess und den Beschränkungen und Einflüssen des Instruktionssatzes bis zur Mikroarchitektur der zugrundeliegenden Hardware untersucht. Als Ergebnis wird eine Strategie präsentiert um eine hohe Leistung für initial speicherbandbreitenbegrenzte Algorithmen auf modernen Architekturen zu erreichen. Der Erfolg dieser Herangehensweise wird anhand der algorithmischen Klasse der Gitterbasierten numerischen Gleichungslöser: Einer Implementierung eines 2D Rot-Schwarz Gauss-Seidel Glätters für die x86/x86-64 Architektur und eine 3D Mehrgitter Implementierung für die IA64 Architektur