Vergleich von Pfadfindungsalgorithmen mit OpenMP und CUDA

=========================================================

Dieses Projekt implementiert und vergleicht drei graphbasierte Pfadfindungsalgorithmen (Dijkstra, A* und ALT) unter Verwendung paralleler Verarbeitung mit OpenMP für CPU-Parallelisierung und CUDA für GPU-Beschleunigung.

1. Projektübersicht

Das Projekt vergleicht die Leistung von:

• Dijkstra-Algorithmus: Klassischer Kürzeste-Wege-Algorithmus
• A-Stern-Algorithmus: Heuristikbasierter Pfadfindungsalgorithmus
• ALT-Algorithmus (A, Landmarks und Dreiecksungleichung): Fortgeschrittene Variante von A* mit Landmarken

Jeder Algorithmus wird in drei Versionen implementiert:

1. Sequentiell (CPU Ein-Thread)
2. Parallel mit OpenMP (CPU Multi-Thread)
3. Parallel mit CUDA (GPU-beschleunigt)

2. Projektstruktur

classDiagram
    class main{
        +main()
        +runComparisonTest(int size, int numThreads)
    }
    
    class GraphGenerator{
        +generateRandomGraph(int size) Graph
        +generateHeuristic(int size) vector~float~
    }
    
    class PerformanceTest{
        +measurePerformance(...)
    }
    
    class Dijkstra{
        +runSequential(Graph graph, int start) vector~float~
        +runParallel(Graph graph, int start) vector~float~
    }
    
    class AStar{
        +runSequential(Graph graph, vector~float~ heuristic, int start, int goal) vector~float~
        +runParallel(Graph graph, vector~float~ heuristic, int start, int goal) vector~float~
    }
    
    class ALT{
        +runSequential(Graph graph, int start, int goal) vector~float~
        +runParallel(Graph graph, int start, int goal) vector~float~
    }
    
    class DijkstraCUDA{
        +run(Graph graph, int start) vector~float~
    }
    
    class AStarCUDA{
        +run(Graph graph, vector~float~ heuristic, int start, int goal) vector~float~
    }
    
    class ALTCUDA{
        +run(Graph graph, int start, int goal) vector~float~
    }
    
    class CUDAHelpers{
        +checkCudaDevice() bool
        +copyGraphToDevice(...)
        +copyResultFromDevice(...)
    }
    
    main --> GraphGenerator: erstellt
    main --> PerformanceTest: nutzt
    main --> Dijkstra: testet
    main --> AStar: testet
    main --> ALT: testet
    main --> DijkstraCUDA: testet
    main --> AStarCUDA: testet
    main --> ALTCUDA: testet
    main --> CUDAHelpers: nutzt checkCudaDevice()
    
    DijkstraCUDA --> CUDAHelpers: nutzt
    AStarCUDA --> CUDAHelpers: nutzt
    ALTCUDA --> CUDAHelpers: nutzt

3. Voraussetzungen

• Qt 5.x oder höher (qtbase5-dev für Qt5 oder qt6-base-dev für Qt6)
• C++17-kompatibler Compiler (GCC oder Clang empfohlen)
• OpenMP-Unterstützung
• CUDA Toolkit 12.8 (installiert in /usr/local/cuda-12.8)
• NVIDIA GPU mit Compute Capability 7.5 oder höher (Turing-Architektur oder neuer)

4. Projekt kompilieren

Umgebungseinrichtung

1. Stellen Sie sicher, dass CUDA korrekt auf Ihrem System installiert ist
2. CUDA_DIR = /usr/local/cuda-12.8 # Ändern Sie dies zu Ihrem CUDA-Installationspfad
3. CUDA_ARCH = sm_75 # Ändern Sie entsprechend Ihrer GPU-Architektur

Kompilierung

Mit qmake und make:

qmake -makefile pth.pro

Oder mit Qt Creator:

1. Öffnen Sie die .pro-Datei in Qt Creator
2. Konfigurieren Sie das Projekt für Ihr System
3. Klicken Sie auf Build

Ausführung der Anwendung

Führen Sie die kompilierte Binärdatei aus:

./pth

Für Windows:

./pth.exe

Das Programm führt Leistungstests durch, die die drei Algorithmen über verschiedene Implementierungen hinweg vergleichen und die Ergebnisse ausgeben.

Implementierungsdetails

1. Graphgenerierung

Das Projekt verwendet synthetische Graphen für Tests, die mit kontrollierbaren Parametern wie folgenden generiert werden:

• Anzahl der Knoten
• Graphdichte
• Kantengewichtsverteilung
• Landmarkenauswahl

2. Leistungstests

Das performancetest-Modul bietet Funktionalitäten zum:

• Generieren von Testgraphen verschiedener Größen
• Ausführen jedes Algorithmus mit identischer Eingabe
• Messen und Vergleichen der Ausführungszeiten
• Berechnen von Beschleunigungsfaktoren

3. CUDA-Implementierung

Die CUDA-Implementierung nutzt:

• CUDA-Streams für gleichzeitige Kernel-Ausführung
• Shared-Memory-Optimierung für bessere Speicherzugriffsmuster

4. OpenMP-Implementierung

Die OpenMP-Implementierung verwendet:

• Parallele For-Schleifen für die Arbeitsverteilung
• Dynamische Scheduling für Lastausgleich
• Aufgabenbasierte Parallelität wo angemessen

5. Konfiguration

Die wichtigsten Leistungsparameter können im Code konfiguriert werden:

• Graphgrößen für Tests
• Anzahl der OpenMP-Threads
• Testwiederholungen für statistische Signifikanz

6. Leistungsanalyse

Die Leistung wird über Implementierungen hinweg gemessen und verglichen, basierend auf:

• Ausführungszeit
• Beschleunigung im Vergleich zur sequentiellen Implementierung
• Skalierbarkeit mit der Graphgröße