Efficiency Improvements of Iterative Numerical Algorithms on Modern Architectures

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

Please always quote using this URN: urn:nbn:de:bvb:29-opus-14036
  • 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 highFor 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.show moreshow less
  • 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 undFü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.show moreshow less

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics
Metadaten
Author:Jan Treibig
URN:urn:nbn:de:bvb:29-opus-14036
Advisor:Ulrich Rüde
Document Type:Doctoral Thesis
Language:English
Year of Completion:2008
Publishing Institution:Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU)
Granting Institution:Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU), Technische Fakultät
Date of final exam:2009/06/18
Release Date:2009/09/04
Tag:Assembler; Cache Blocking; Computer Architecture; Optimization
SWD-Keyword:Optimierung; Hardwaremessung; Assembler; Poisson-Gleichung; Cache-Speicher; Computerarchitektur; Compiler; Numerische Mathematik
Institutes:Technische Fakultät / Technische Fakultät -ohne weitere Spezifikation-
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
open_access (DINI-Set):open_access