LU-GPU: Effiziente Algorithmen zur Lösung dichter linearer Systeme auf Grafikhardware

Wir präsentieren einen neuartigen Algorithmus zur Lösung dichter linearer Systeme unter Verwendung von Grafikprozessoren (GPUs). Wir reduzieren die Matrixzerlegung und Zeilenoperationen auf eine Reihe von Rasterisierungsproblemen auf der GPU. Dazu gehören neue Techniken zum Streaming von Indexpaaren, zum Tauschen von Zeilen und Spalten sowie zur Parallelisierung der Berechnung, um mehrere Vertex- und Fragmentprozessoren zu nutzen. Wir verwenden auch geeignete Datenrepräsentationen, um die Rasterisierungsreihenfolge und die Cache-Technologie der Grafikprozessoren anzupassen. Wir haben unseren Algorithmus auf verschiedenen GPUs implementiert und die Leistung mit optimierten CPU-Implementierungen verglichen. Insbesondere übertrifft unsere Implementierung auf einer NVIDIA GeForce 7800 GPU eine CPU-basierte ATLAS-Implementierung. Darüber hinaus zeigen unsere Ergebnisse, dass unser Algorithmus cache- und bandbreiteneffizient ist und gut mit der Anzahl der Fragmentprozessoren innerhalb der GPU sowie mit der Kern-GPU-Taktfrequenz skalierbar ist. Wir verwenden unseren Algorithmus zur Simulation von Flüssigkeitsströmungen und demonstrieren, dass die handelsübliche GPU ein nützlicher Co-Prozessor für viele wissenschaftliche Anwendungen ist.