Making C# Mandelbrot Zeichnung effizienter

Question

Zunächst einmal ist mir bewusst, dass diese Frage wirklich klingt, als ob ich nicht suchte, aber ich tat, viel.

Ich habe einen kleinen Mandelbrot-Zeichencode für C# geschrieben, es ist im Grunde eine Windows-Form mit einer PictureBox, auf der ich das Mandelbrot-Set zeichne.

Mein Problem ist, dass es ziemlich langsam ist. Ohne einen tiefen Zoom macht es einen ziemlich guten Job und das Bewegen und Zoomen ist ziemlich glatt, dauert weniger als eine Sekunde pro Zeichnung, aber sobald ich anfange, ein wenig zu zoomen und zu Orten zu kommen, die mehr Berechnungen erfordern, wird es wirklich langsam.

Bei anderen Mandelbrot-Anwendungen funktioniert mein Computer sehr gut an Orten, die in meiner Anwendung viel langsamer arbeiten, also denke ich, dass es viel gibt, was ich tun kann, um die Geschwindigkeit zu verbessern.

ich folgende Dinge tat, es zu optimieren:

• Statt die SetPixel GetPixel Methoden auf das Bitmap-Objekt verwenden, benutzte ich LockBits Verfahren direkt in den Speicher zu schreiben, die Dinge viel schneller gemacht.

• Anstatt komplexe Zahlenobjekte zu verwenden (mit Klassen, die ich selbst gemacht habe, nicht die eingebauten), emulierte ich komplexe Zahlen mit 2 Variablen, re und im. Dies ermöglichte es mir, Multiplikationen zu reduzieren, da die Quadratur des Realteils und des Imaginärteils während der Berechnung einige Zeit dauert. Daher speichere ich das Quadrat in einer Variablen und verwende das Ergebnis, ohne es neu berechnen zu müssen.

• Ich benutze 4 Threads um das Mandelbrot zu zeichnen, jeder Thread macht ein anderes Viertel des Bildes und alle arbeiten gleichzeitig. Wie ich verstanden habe, bedeutet das, dass meine CPU 4 ihrer Kerne benutzt, um das Bild zu zeichnen.

• Ich verwende den Escape Time Algorithm, den ich am schnellsten verstanden habe?

Hier ist mein, wie ich zwischen den Pixeln und berechnen zu bewegen, ist es kommentiert, so hoffe ich, es ist verständlich:

 //Pixel by pixel loop: 
     for (int r = rRes; r < wTo; r++) 
     { 
      for (int i = iRes; i < hTo; i++) 
      { 

       //These calculations are to determine what complex number corresponds to the (r,i) pixel. 
       double re = (r - (w/2))*step + zeroX ; 
       double im = (i - (h/2))*step - zeroY; 

       //Create the Z complex number 
       double zRe = 0; 
       double zIm = 0; 

       //Variables to store the squares of the real and imaginary part. 
       double multZre = 0; 
       double multZim = 0; 

       //Start iterating the with the complex number to determine it's escape time (mandelValue) 
       int mandelValue = 0; 
       while (multZre + multZim < 4 && mandelValue < iters) 
       { 
        /*The new real part equals re(z)^2 - im(z)^2 + re(c), we store it in a temp variable 
        tempRe because we still need re(z) in the next calculation 
         */ 
        double tempRe = multZre - multZim + re; 

        /*The new imaginary part is equal to 2*re(z)*im(z) + im(c) 
         * Instead of multiplying these by 2 I add re(z) to itself and then multiply by im(z), which 
         * means I just do 1 multiplication instead of 2. 
         */ 
        zRe += zRe; 
        zIm = zRe * zIm + im; 

        zRe = tempRe; // We can now put the temp value in its place. 

        // Do the squaring now, they will be used in the next calculation. 
        multZre = zRe * zRe; 
        multZim = zIm * zIm; 

        //Increase the mandelValue by one, because the iteration is now finished. 
        mandelValue += 1; 
       } 


       //After the mandelValue is found, this colors its pixel accordingly (unsafe code, accesses memory directly): 
       //(Unimportant for my question, I doubt the problem is with this because my code becomes really slow 
       // as the number of ITERATIONS grow, this only executes more as the number of pixels grow). 
       Byte* pos = px + (i * str) + (pixelSize * r); 
       byte col = (byte)((1 - ((double)mandelValue/iters)) * 255); 
       pos[0] = col; 
       pos[1] = col; 
       pos[2] = col; 

      } 
     } 

Was kann ich dies verbessern tun? Finden Sie irgendwelche offensichtlichen Optimierungsprobleme in meinem Code?

Im Moment gibt es zwei Möglichkeiten, wie ich weiß, dass ich es verbessern kann:

1. Ich brauche einen anderen Typ für Zahlen verwenden, doppelt mit Genauigkeit begrenzt und ich bin sicher, es gibt bessere unbebaut - in alternativen Typen, die schneller sind (sie multiplizieren und fügen schneller hinzu) und mehr Genauigkeit haben, brauche ich nur jemanden, der mir zeigt, wo ich hinschauen muss, und mir sagen, ob es wahr ist.

2. Ich kann die Verarbeitung auf die GPU verschieben. Ich habe keine Ahnung, wie ich das machen soll (OpenGL vielleicht? DirectX? Ist es überhaupt so einfach oder muss ich eine Menge lernen?). Wenn mir jemand Links zu passenden Tutorials zu diesem Thema schicken kann oder mir allgemein davon erzählen würde, wäre das super.

Vielen Dank für die weit Lesen und hoffen, dass Sie mich :)

Answer 1

Für die Verarbeitung auf die GPU zu bewegen helfen können, haben Sie viele gute Beispiele hier:

https://www.shadertoy.com/results?query=mandelbrot

Beachten Sie, dass Sie einen WebGL-fähigen Browser benötigen, um diesen Link anzuzeigen. Funktioniert am besten in Chrome.

Ich bin kein Experte für Fraktale, aber Sie scheinen schon weit mit den Optimierungen gekommen zu sein. Wenn Sie darüber hinaus gehen, wird der Code viel schwieriger zu lesen und zu warten. Sie sollten sich also fragen, ob es sich lohnt.

Eine Technik, die ich oft in anderen Fraktalprogrammen beobachtet habe, ist folgende: Während des Zoomens berechne ich das Fraktal mit einer niedrigeren Auflösung und dehne es während des Renderns auf volle Größe. Rendern Sie dann mit voller Auflösung, sobald das Zoomen stoppt. Wenn Sie mehrere Threads verwenden, sollten Sie darauf achten, dass nicht jeder Thread Speicher anderer Threads liest/schreibt, da dies zu Cache-Kollisionen führen und die Leistung beeinträchtigen kann. Ein guter Algorithmus könnte die Arbeit in Scanlinien aufteilen (statt wie bisher vier Viertel). Erstellen Sie eine Anzahl von Threads, und weisen Sie ihnen so lange einen Scan zu, bis ein Thread verfügbar ist. Lassen Sie jeden Thread die Pixeldaten in einen lokalen Speicherbereich schreiben und kopieren Sie ihn nach jeder Zeile wieder in die Hauptbitmap (um Cache-Kollisionen zu vermeiden).

Answer 2

WRT Codierung für die GPU, können Sie sich Cudafy.Net anschauen (es tut auch OpenCL, das nicht an NVidia gebunden ist), um zu verstehen, was los ist, und vielleicht sogar alles zu tun, was Sie brauchen. Ich habe es schnell gefunden - und meine Grafikkarte - ungeeignet für meine Bedürfnisse, aber für das Mandelbrot auf der Bühne, wo du bist, sollte es in Ordnung sein.

Kurz gesagt: Sie Code für die GPU mit einem Geschmack von C (Cuda C oder OpenCL normalerweise) dann drücken Sie den "Kernel" (Ihre kompilierte C-Methode) auf die GPU, gefolgt von allen Quelldaten, und rufen Sie dann " Kernel ", oft mit Parametern zu sagen, welche Daten zu verwenden - oder vielleicht ein paar Parameter, um es zu sagen, wo die Ergebnisse in seinem Speicher platziert werden.

Wenn ich Fractal-Rendering selbst gemacht habe, habe ich aus den bereits genannten Gründen vermieden, zu einer Bitmap zu zeichnen und die Render-Phase verschoben. Abgesehen davon tendiere ich dazu, massiv Multithreading-Code zu schreiben, was wirklich schlecht ist, um auf eine Bitmap zuzugreifen. Stattdessen schreibe ich in einen gemeinsamen Speicher - zuletzt habe ich eine MemoryMappedFile (eine eingebaute .Net-Klasse) verwendet, da dies mir eine ziemlich gute wahlfreie Zugriffsgeschwindigkeit und einen riesigen adressierbaren Bereich bietet. Ich tendiere auch dazu, meine Ergebnisse in eine Warteschlange zu schreiben und einen anderen Thread damit zu beschäftigen, die Daten an den Speicher zu übergeben; Die Rechenzeit jedes Mandelbrot-Pixels wird "zerlumpt" sein - das heißt, sie werden nicht immer die gleiche Zeitlänge haben. Infolgedessen könnte Ihr Pixel-Commit der Engpass für sehr niedrige Iterationszahlen sein. Wenn Sie es auf einen anderen Thread umstellen, bedeutet dies, dass Ihre Compute-Threads niemals auf die Fertigstellung des Speichers warten.

Ich spiele gerade mit der Buddhabrot-Visualisierung des Mandelbrot-Sets und versuche mit einer GPU das Rendering zu skalieren (da es sehr lange mit der CPU dauert) und ein riesiges Ergebnis-Set zu haben. Ich dachte daran, ein 8-Gigapixel-Bild anzuschneiden, aber ich bin zu der Erkenntnis gekommen, dass ich von den Beschränkungen der Pixel abweichen muss und möglicherweise von der Fließkomma-Arithmetik aufgrund von Präzisionsproblemen abweichen muss.Ich werde auch etwas neue Hardware kaufen müssen, damit ich mit der GPU anders interagieren kann - verschiedene Compute-Jobs werden zu unterschiedlichen Zeiten fertig sein (entsprechend meiner früheren Iteration), so dass ich nicht einfach Threads abfeuern und warten kann für sie alle zu vervollständigen, ohne möglicherweise viel Zeit zu verlieren, die auf eine besonders hohe Iteration wartet, zählen Sie aus der ganzen Reihe.

Ein weiterer Punkt, den ich kaum jemals über das Mandelbrot-Set gesehen habe, ist, dass es symmetrisch ist. Sie könnten doppelt so viel berechnen, wie Sie benötigen.

Answer 3

Wenn Sie die Verarbeitung in die GPU verschieben möchten, können Sie aus einer Reihe von Optionen auswählen. Da Sie C# verwenden, können Sie mit XNA HLSL verwenden. RB Whitaker hat die einfachsten XNA-Tutorials, wenn Sie diese Option wählen. Eine andere Option ist OpenCL. OpenTK kommt mit einem Demo-Programm eines Julia-Fraktals. Dies wäre sehr einfach zu modifizieren, um den Mandlebrot-Satz anzuzeigen. Siehe here Denken Sie daran, den GLSL-Shader zu finden, der zum Quellcode gehört.

über die GPU, Beispiele keine Hilfe für mich, weil ich absolut keine Ahnung von diesem Thema habe, wie funktioniert es auch und welche Art von Berechnungen der GPU tun kann (oder wie ist es sogar zugegriffen?

)

Verschiedene GPU-Software funktioniert anders aber ...

Regel ein Programmierer ein Programm für die GPU in einer Shader-Sprache wie HLSL, GLSL oder OpenCL schreiben. Das in C# geschriebene Programm wird den Shader-Code laden und kompilieren und dann Funktionen in einer API verwenden, um einen Job an die GPU zu senden und das Ergebnis danach zurück zu bekommen.

Werfen Sie einen Blick auf FX Composer oder machen Sie einen Affen, wenn Sie etwas Übung mit Shadern haben wollen, ohne sich um APIs kümmern zu müssen.

Wenn Sie HLSL verwenden, sieht die Rendering-Pipeline wie folgt aus.

Der Vertex-Shader ist verantwortlich für die Punkte im 3D-Raum zu nehmen und ihre Position in der 2D-Sichtfeld zu berechnen. (Keine große Sorge für Sie, da Sie in 2D arbeiten)

Der Pixel-Shader ist verantwortlich für das Anwenden von Shader-Effekten auf die Pixel, nachdem der Vertex-Shader fertig ist.

OpenCL ist eine andere Geschichte, es ist auf allgemeine GPU-Computing (dh: nicht nur Grafiken) ausgerichtet. Es ist leistungsfähiger und kann für GPUs, DSPs und Supercomputer verwendet werden.