Critical-Path Analysis and Optimization Guidance for CUDA Programs

Date

Dec 17, 2013

Time

9:30 AM - 10:30 AM

Speaker

Felix Schmitt

Language

de

Main Topic

Informatik

Other Topics

Informatik

Description

Die aktuelle dominierende Herausforderung im Hochleistungsrechnen ist die Entwicklung paralleler Algorithmen, welche bis in den Petaflop Bereich skalieren. Ein etablierter Ansatz ist die Verwendung massiv-paralleler Grafikprozessoren (GPUs), häufig unter Verwendung von NVIDIAs Compute Unified Device Architecture (CUDA). CUDA bietet eine umfangreiche Programmierschnittstelle und erzielt hohe Rechenleistung je GPU. Damit Programme die verfügbaren Ressourcen auf GPU und CPU effizient nutzen, müssen diese jedoch häufig mehrere Parallelisierungsebenen gleichzeitig verwenden. Aus dieser steigenden Programmkomplexität ergibt sich die Notwendigkeit für leistungsfähige Werkzeuge, sowohl für die Programmentwicklung als auch für deren Leistungsanalyse. Ziel meiner Arbeit ist die Bestimmung des kritischen Pfades von heterogenen CUDA- und MPI-Programmen sowie die Unterstützung des Entwicklers mittels Optimierungsvorschlägen, basierend auf einem Modell der Interaktionen und Abhängigkeiten zwischen CUDAs CPU-und GPU-Funktionen. Auf der Grundlage dieses regelbasierten Modells und der Aufzeichnung einer Programmausführung kann ein Abhängigkeitsgraph konstruiert werden. In diesem lässt sich der kritische Pfad bestimmen, welcher die Laufzeit des Programms dominiert. An Punkten an denen eine Programmspur auf Grund von Synchronisation auf eine andere warten muss und verzögert wird, können Wartestellen eingefügt werden. Kombiniert mit den in der Analyse ermittelten Leitungsdaten können hypothetische Programmabläufe vorhergesagt und verglichen werden. Schlussendlich wird dem Entwickler eine Liste mit vielversprechen- den Optimierungsstellen, zu erwartenden Leistungsgewinnen und detaillierte Informationen zu Programmabhängigkeiten angeboten. Während der Entwicklung meiner Arbeit wurden zufällig generierte Eingabedaten sowie praktische Beispiele genutzt, um die berechneten Abhängigkeiten zu verifizieren und vorhergesagte Leistungssteigerungen zu validieren.

• -----------------

Abstract High performance computing is currently facing the need to design parallel algorithms and programs to solve challenges in the peta-scale domain. An established approach is to utilize the massively parallel computing power of graphics processing units (GPUs), most often by using NVIDIA’s compute unified device architecture (CUDA). Today, CUDA offers a rich programming interface and requires developers to write programs which incorporate several layers of parallelism on both CPU and GPU to make efficient use of the available resources. From this increasing program complexity emerges the need for powerful tools, which support the application development process. My work aims at analyzing heterogeneous CUDA and MPI programs for their critical path and providing the developer with guiding optimization recommendations, based on a model for the interactions and dependencies between CUDA host and device functions. Given this rule-based model and an execution trace, a dependency graph can be constructed and analyzed for its critical path which determines the total runtime. In this graph, wait-states are located at points where one stream of program activities is delayed by another as a result of synchronization. Combining the dependency information with performance counters computed during my analysis, hypothetical program executions can be computed using graph-based performance projection. This allows to estimate the impact of the optimization of critical functions which have been detected during analysis. Finally, the developer is given a guiding list of promising optimization points, potential performance gains and detailed knowledge about the dependencies and inefficiencies of his program. The correctness of the constructed dependencies and the performance projection are validated with randomly generated test trace data along with real-world examples. Diese Veranstaltung wird unterstützt von Professur für Rechnerarchitektur.

Last modified: Dec 17, 2013, 8:37:02 AM