Koordinatentransformationen auf GPU verschieben

Question

Ich habe eine alte Map Viewer-Anwendung mit WinForms. Es ist sloooooo. (Die Geschwindigkeit war akzeptabel, aber Google Maps, Google Earth kam und Benutzer wurden verwöhnt. Jetzt darf ich machen, wenn schneller :)

Nach all den offensichtlichen Geschwindigkeit Verbesserungen (Caching, parallele Ausführung, nicht zeichnen Was muss nicht gezeichnet werden, etc.), Mein Profiler zeigt mir, dass der echte Engpass die Koordinatentransformationen beim Konvertieren von Punkten aus dem Kartenraum in den Bildschirmbereich sind. Normalerweise wird ein Conversion-Code sieht wie folgt aus:

public Point MapToScreen(PointF input) 
    { 
     // Note that North is negative! 
     var result = new Point(
      (int)((input.X - this.currentView.X) * this.Scale), 
      (int)((input.Y - this.currentView.Y) * this.Scale)); 
     return result; 
    } 

Die eigentliche Implementierung schwieriger ist. Latitudes/Longitues werden als ganze Zahlen dargestellt. Um keine Genauigkeit zu verlieren, werden sie mit 2^20 (~ 1 Million) multipliziert. So wird eine Koordinate dargestellt.

public struct Position 
{ 
    public const int PrecisionCompensationPower = 20; 
    public const int PrecisionCompensationScale = 1048576; // 2^20 
    public readonly int LatitudeInt; // North is negative! 
    public readonly int LongitudeInt; 
} 

Es ist wichtig, dass die möglichen Skalierungsfaktoren zu Potenz von 2 auch ausdrücklich Dies erlaubt uns gebunden sind, um die Multiplikation mit einem bitshift zu ersetzen. Die eigentliche Algorithmus sieht wie folgt aus:

public Point MapToScreen(Position input) 
    { 
     Point result = new Point(); 
     result.X = (input.LongitudeInt - this.UpperLeftPosition.LongitudeInt) >> 
        (Position.PrecisionCompensationPower - this.ZoomLevel); 
     result.Y = (input.LatitudeInt - this.UpperLeftPosition.LatitudeInt) >> 
        (Position.PrecisionCompensationPower - this.ZoomLevel); 
     return result; 
    } 

(UpperLeftPosition representents die linke obere Ecke des Bildschirms in der Karte Platz.) Ich denke jetzt diese Berechnung auf die GPU von Offloading. Kann mir jemand ein Beispiel zeigen, wie man das macht?

Wir verwenden .NET4.0, aber der Code sollte vorzugsweise auch unter Windows XP laufen. Außerdem können Bibliotheken unter GPL nicht verwendet werden.

Answer 1

Jetzt ein Jahr später das Problem wieder auf, und wir fanden eine sehr banale Antwort. Ich fühle mich ein bisschen dumm, es vorher nicht zu merken. Wir zeichnen die geographischen Elemente über gewöhnliches WinForms GDI zu Bitmap. GDI ist hardwarebeschleunigt. Alles, was wir tun müssen, ist nicht die Transformation von uns selbst zu tun, sondern legen Sie die Skalierungsparameter von System.Drawing.Graphics Objekt: Graphics.TranslateTransform (...) und Graphics.ScaleTransform (...) Wir nicht brauche sogar den Trick mit der Bitverschiebung.

:)

Answer 2

Ich schlage vor, Sie schauen auf OpenCL mit und Cloo, dies zu tun - werfen Sie einen Blick auf die vector add example und dann diese Werte unter Verwendung von zwei ComputeBuffer s (jeweils eine für LatitudeInt und LongitudeInt in jedem Punkt) zur Karte ändern 2 Ausgang ComputeBuffer s. Ich vermute, die OpenCL-Code würde etwa wie folgt aussieht:

__kernel void CoordTrans(__global int *lat, 
         __global int *lon, 
         __constant int ulpLat, 
         __constant int ulpLon, 
         __constant int zl, 
         __global int *outx, 
         __global int *outy) 
{ 
    int i = get_global_id(0);   
    const int pcp = 20; 

    outx[i] = (lon[i] - ulpLon) >> (pcp - zl); 
    outy[i] = (lat[i] - ulpLat) >> (pcp - zl); 
} 

aber würden Sie tun mehr als eine coord-Transformation pro Kern. Ich muss losstürmen, ich empfehle Ihnen, auf Opencl zu lesen, bevor Sie dies tun.

Wenn die Anzahl der Coords vernünftig ist (< 100.000/1.000.000), ist die Lösung ohne GPU wahrscheinlich schneller.

Answer 3

Ich komme aus einem CUDA-Hintergrund und kann nur für NVIDIA-GPUs sprechen, aber hier geht.

Das Problem bei der Verwendung einer GPU ist Ihre Betriebs-/Übertragungszeit.

Sie haben in der Größenordnung von 1 Operation pro Element durchzuführen. Sie möchten wirklich mehr als das pro Element tun, um eine echte Geschwindigkeitsverbesserung zu erhalten. Die Bandbreite zwischen dem globalen Speicher und den Threads auf einer GPU beträgt etwa 100 GB/s. Wenn Sie also eine 4-Byte-Ganzzahl laden müssen, um ein FLOP auszuführen, beträgt die theoretische Höchstgeschwindigkeit 100/4 = 25 FLOPS. Dies ist weit von den Hunderten von FLOPS beworben.

Beachten Sie, dass dies das theoretische Maximum ist, das tatsächliche Ergebnis könnte schlechter sein. Und das ist noch schlimmer, wenn Sie mehr als ein Element laden. In Ihrem Fall sieht es wie 2 aus, so dass Sie maximal 12,5 FLOPS davon erhalten können. In der Praxis wird es mit ziemlicher Sicherheit niedriger sein.

Wenn das für Sie aber ok klingt, dann gehen Sie darauf!

Answer 4

XNA kann verwendet werden, um alle Transformationen durchzuführen, die Sie benötigen, und bietet eine sehr gute Leistung. Es kann auch in einer Winforms-Anwendung angezeigt werden: http://create.msdn.com/en-US/education/catalog/sample/winforms_series_1