Beside traditional direct solvers iterative methods offer an efficient alternative for the solution of systems of linear equations which arise in the solution of partial differential equations (PDEs). Among them, multigrid algorithms belong to the most efficient methods based on the number of operations required to achieve a good approximation of the solution. The relevance of the number of arithmetic operations performed by an application as a metric for the complexity of an algorithm wanes since the performance of modern computing systems nowadays is limited by memory latency and bandwidth. Consequently, almost all computer manufacturers nowadays equip their computers with cache-based hierarchical memory systems. Thus, the efficiency of multigrid methods is rather determined by good data locality, i.e. good utilization of data caches, than by the number of arithmetic operations. In this thesis, the cache and memory access behavior of multigrid methods is systematically analyzed for the first time. The analysis is based on an exhaustive study of modern microprocessor memory hierarchies. Detailed runtime as well as theoretical studies of the performance of these methods demonstrate the interaction between multigrid algorithms and deep memory hierarchies. In particular, issues involved with the multilevel nature of the memory hierarchy are addressed. Furthermore, delays due to main memory accesses are clearly revealed as the performance bottlenecks of multigrid methods and their components. Besides the performance bottlenecks, upper limits for the achievable performance of multigrid methods on RISC based microprocessors are determined by means of theoretical models. Based on the knowledge gained from the analysis of multigrid algorithms and microprocessor architectures, new data locality optimization techniques for multigrid methods are proposed. The techniques extend existing code and data layout restructuring techniques and are able to significantly improve data locality and consequently speed up the execution of multigrid algorithms by a multiple. With the improved data locality multigrid methods are able to utilize 15 to 30 per cent of the peak performance on a multitude of modern computer systems. The impact of the techniques is demonstrated with runtime and memory hierarchy behavior measurements as well as theoretical data locality examinations. The applicability of the techniques is demonstrated by means of the DiMEPACK library. DiMEPACK is a multigrid solver for two-dimensional problems with constant coefficients on structured grids. In this thesis, however, aspects of multigrid methods for three-dimensional problems and variable coefficients are discussed as well.     «

Beside traditional direct solvers iterative methods offer an efficient alternative for the solution of systems of linear equations which arise in the solution of partial differential equations (PDEs). Among them, multigrid algorithms belong to the most efficient methods based on the number of operations required to achieve a good approximation of the solution. The relevance of the number of arithmetic operations performed by an application as a metric for the complexity of an algorithm wanes sin...     »

Die Klasse der Mehrgitterverfahren zählt, gemessen an der Anzahl der nötigen Operationen, mit zu den effizientesten Verfahren zur Lösung linearer Gleichungssysteme. Die Anzahl der Rechenoperationen als Bewertungsmaßstab für die Effizienz von Algorithmen tritt aber immer weiter in den Hintergrund, da bei modernen Rechensystemen die mögliche Rechengeschwindigkeit durch die hohe Latenz und den geringen Durchsatz des Hauptspeichers limitiert wird. In nahezu allen heutigen Rechensystemen findet deshalb ein hierarchischer Speicheraufbau Anwendung. Sehr kleine aber dafür schnelle Cache-Speicher werden auf der CPU integriert und sollen die Rechenkerne in ausreichender Geschwindigkeit mit Daten versorgen. Aufgrund der begrenzten Größe der Caches kann aber nur ein Teil der Daten eines Mehrgitterverfahren in diesen schnellen Speichern bereitgehalten werden. Zugriffe auf die übrigen Daten führen zu einer entsprechenden Verlangsamung des Programmablaufs. Entscheidend für die Effizienz von Mehrgitterverfahren ist deshalb nicht mehr so sehr die Anzahl der Rechenoperationen, sondern eine hohe Datenlokalität, d.h. gute Ausnutzung der Caches. Die vorliegende Arbeit analysiert zum ersten mal systematisch das Cache- und Speicherverhalten von Mehrgitterverfahren für Rechnerarchitekturen mit mehrstufigen Speicherhierarchien. Die Analyse basiert auf einer detailierten und umfangreichen Studie moderner Mikroprozessoren. Eine detailierte Studie des Laufzeitverhaltens von Mehrgitterverfahren sowie theoretische Überlegungen über die Leistung dieser Verfahren demonstrieren die Interaktion des Mehrgitteralgorithmus und der einzelnen Stufen der Speicherhierarchie. Die Analyse belegt, dass die Laufzeit von Mehrgitterverfahren durch die benötigte Zeit für Hauptspeicherzugriffe dominiert wird. Außerdem werden anhand von theoretischen Modellen obere Schranken ermittelt, welche die erreichbare Rechenleistung im Falle von Mehrgitterverfahren limitieren. Darauf aufbauend werden neue Techniken zur Optimierung der Datenlokaliät von Mehrgitterverfahren auf strukturierten Gittern entwickelt. Diese Techniken erweitern existierende Techniken zur Restrukturierung des Quelltexts und der Datenanordnung und sind in der Lage die Datenlokalität wesentlich zu verbessern. Die Mehrgitterverfahren werden dadurch teilweise um ein Vielfaches beschleunigt und erreichen 15 bis 30 Prozent der maximalen Rechenleistung auf einer Vielzahl von heutigen Rechnersystemen. Außerdem wird die Auswirkung der Techniken anhand von detailierten Laufzeit- und Speicherhierarchieanalysen, sowie theoretischen Datenlokalitätsanalysen aufgezeigt. Die Anwendbarkeit der Techniken wird anhand von DiMEPACK, einer Mehrgitterbibliothek für zweidimensionale Probleme mit konstanten Koeffizienten auf strukturierten Gittern, demonstriert. Obwohl die Arbeit sich schwerpunktartig mit der Analyse und Optimierung von Mehrgitterverfahren auf strukturierten Gittern für zweidimensionale Probleme mit konstanten Koeffizienten beschäftigt, wird auch auf Aspekte von Mehrgitterverfahren für dreidimensionale Probleme und Probleme mit variablen Koeffizienten eingegangen.     «

Die Klasse der Mehrgitterverfahren zählt, gemessen an der Anzahl der nötigen Operationen, mit zu den effizientesten Verfahren zur Lösung linearer Gleichungssysteme. Die Anzahl der Rechenoperationen als Bewertungsmaßstab für die Effizienz von Algorithmen tritt aber immer weiter in den Hintergrund, da bei modernen Rechensystemen die mögliche Rechengeschwindigkeit durch die hohe Latenz und den geringen Durchsatz des Hauptspeichers limitiert wird. In nahezu allen heutigen Rechensystemen findet desha...     »