Performance-Engineering für exascalefähige Grundbausteine linearer Algebra mit dünn besetzten Matrizen

The increasing demand for solving larger and more complex problems in computational science and engineering is a major driving factor to deploy computer systems with ever-advancing performance capabilities. To increase the available performance, modern High-Performance Computing (HPC) platforms come with multiple levels of parallelism, complex memory hierarchies, heterogeneous architectures, and extreme scales. To match the need for sustainable and efficient software under these premises, special value has to be attached to the inherent challenges like efficiency on all scales and performance portability across heterogeneous architectures. This work addresses the development of high-performance scientific software for sparse linear algebra, which is an important field of research and forms the foundation of many applications of computational science and engineering, with a special focus on sparse eigenvalue solvers on current and future supercomputers. One of the most prominent building blocks of sparse linear algebra is Sparse Matrix-Vector Multiplication (SpMV). In this work, a platform-agnostic storage format for high-performance general SpMV is developed: SELL-C-σ. Based on existing, device-specific formats, its design is justified and best practices for the selection of tuning parameters are provided. It is demonstrated that SpMV using a unified SELL-C-σ matrix usually not only yields competitive performance but even surpasses device-specific formats and implementations for many test cases. Sparse linear algebra algorithms can often be formulated using blocks of vectors instead of single vectors. This technique is in some cases motivated by numerical benefits, but it also contains performance optimization potential. In this work, the shift of hardware bottlenecks is analyzed and highly efficient implementations of block vector kernels are presented. Kernel fusion is employed in the present work on top of optimized basic building blocks, leading to custom compute kernels for sparse linear algebra algorithms bearing significant performance gains. The performance engineering process consistently implemented for all software development efforts in this work – including code analysis, benchmarking, the evaluation of hardware metrics, and code optimization – is closely guided by performance models. Performance modeling is an indispensable ingredient for the development of high-performance software components, as it helps in revealing hardware bottlenecks, identifying suitable optimization techniques, and assessing the efficiency of a present implementation on a given hardware platform. To be accessible by a broader community, all software development efforts conducted within this work are combined into the scalable open-source software library GHOST. To demonstrate the applicability of the developed software components, full-application performance of several sparse eigenvalue solvers for real-world problems on some of the world’s largest supercomputers with completely different hardware architectures is presented. Combining all of the developed building blocks and techniques, solutions to the standard eigenvalue problem for relevant quantum physics applications are acquired. At the largest scale, matrices with up to 26 billion rows and 7 terabytes of raw data are investigated on thousands of homogeneous and heterogeneous compute nodes with hundreds of TFLOP/s sustained performance and verifiable high efficiency from the single node to the extreme scale.Der steigende Bedarf zur Lösung größerer und komplexerer Probleme im Bereich des wissenschaftlichen Rechnens ist ein treibender Faktor für die Entwicklung und den Einsatz von Hochleistungsrechnern mit stetig wachsenden Hardware-Fähigkeiten. Wichtige Maßnahmen zur Steigerung der verfügbaren Leistung in modernen Systemen des Hochleistungsrechnens (High-Performance Computing, HPC) umfassen die Einführung mehrerer Parallelitätsebenen, komplexer Speicherhierarchien und heterogener Architekturen, sowie eine stetige Vergrößerung der HPC-Systeme. Um dem Bedarf nach nachhaltiger und effizienter Software unter diesen Voraussetzungen gerecht zu werden, muss den inhärenten Herausforderungen wie Effizienz auf allen Skalen und Performance-Portabilität für heterogene Architekturen Beachtung geschenkt werden. Diese Dissertation widmet sich der Entwicklung hoch-performanter wissenschaftlicher Software für lineare Algebra mit dünn besetzten Matrizen, welche ein bedeutendes Forschungsgebiet und die Grundlage für viele Anwendungen wissenschaftlichen Rechnens darstellt. Eine der bedeutendsten Grundoperationen auf dem Gebiet der dünn besetzten linearen Algebra ist die Multiplikation einer dünn besetzten Matrix mit einem Vektor (Sparse Matrix-Vector Multiplication, SpMV). Ein Teil dieser Arbeit befasst sich mit der Entwicklung eines plattformunabhängigen Datenformats für hocheffiziente allgemeine SpMV: SELL-C-σ. Das Design dieses Datenformats wird auf Basis existierender Datenformate begründet und Vorschläge zur Wahl von Optimierungsparametern werden unterbreitet. In Bezug auf SpMV-Performance erweist sich SELL-C-σ nicht nur als konkurrenzfähig, sondern oftmals sogar effizienter als plattformspezifische Datenformate und Implementierungen. Algorithmen dünn besetzter linearer Algebra können häufig mit Blöcken von Vektoren anstatt einzelner Vektoren formuliert werden. Dieses Vorgehen ist in manchen Fällen durch numerische Vorteile motiviert, birgt jedoch auch Potential zur Steigerung der Performance. Diese Arbeit analysiert die durch Block-Formulierungen hervorgerufene Veränderung der limitierenden Hardware-Ressourcen und präsentiert hocheffiziente Implementierungen von Block-Vektor-Operationen. Neben optimierten Grundbausteinen wird in der vorliegenden Arbeit von der Fusion elementarer Berechnungs-Routinen Gebrauch gemacht, welche zu spezifischen Routinen für Algorithmen dünn besetzter linearer Algebra führt und signifikante Performance-Steigerungen zur Folge hat. Der Performance-Engineering-Prozess – einschließlich Code-Analyse, Benchmarking, der Evaluierung von Hardware-Metriken und Code-Optimierung – orientiert sich an Performance-Modellen und findet konsequente Anwendung im Rahmen der Software-Entwicklung in dieser Arbeit. Performance-Modellierung ist ein unverzichtbarer Bestandteil in der Entwicklung hocheffizienter Software-Komponenten, denn sie erlaubt es, limitierende Hardware-Ressourcen aufzudecken, geeignete Optimierungsstrategien zu bestimmen und die Effizienz einer Implementierung auf einer gegebenen Hardware-Plattform zu beurteilen. Um einer breiteren Öffentlichkeit Zugang zu gewähren, werden alle im Rahmen dieser Arbeit entwickelten Software-Komponenten in der skalierbaren und quelloffenen Software-Bibliothek GHOST zur Verfügung gestellt. Die Anwendbarkeit der entwickelten Software-Komponenten wird durch Experimente auf Basis realer Probleme aus der Praxis demonstriert. Hierfür werden einige der größten Hochleistungsrechner der Welt mit gänzlich unterschiedlichen Hardware-Architekturen verwendet. Basierend auf den entwickelten Software-Bausteinen und Methoden werden Eigenwertprobleme für aktuelle Anwendungen der Quantenphysik gelöst. Die größten Experimente beinhalten dünn besetzte Matrizen mit bis zu 26 Milliarden Zeilen und 7 Terabyte Rohdaten auf tausenden von homogenen und heterogenen Rechenknoten, wobei hunderte TFLOP/s Performance mit verifizierbar hoher Effizienz vom einzelnen Rechenknoten bis hin zu extremen Skalen erreicht werden können