Welche Programmiersprache/Möglichkeiten für grosse Rechenleistung

Hallo,

Ich programmiere gerade verschiedene Fraktals, u.a. das Buddhabrot-Fraktal. Da man für eine gute Bildqualität extrem viele Iterationen und somit extrem viele Rechnungen machen muss dauert das sehr lange, wenn ich es mit C# programmiere. Deshalb ist meine Frage, ob es Möglichkeiten gibt das ganze zu optimieren und zu beschleunigen, damit es schneller geht. Wäre es besser für eine solche reine Rechenaufgabe eine andere Programmiersprache zu verwenden? Ich habe gehört CUDA wäre für so etwas geeignet.

Gruss Aratar

Hallo Aratar,

dauert das sehr lange, wenn ich es mit C# programmiere.

Profile mal - vielleicht findest du so einige Hot Spots (Bitmap.SetPixel ist z.B. so ein Kandidat 😉 ).

Evtl. bringt auch schon eine Parallelisierung einen ordentlichen Performanceschub.

Ansonsten wird Assembler natürlich meist schneller sein - man hat einfach mehr Spielraum für Optimierungen (allerdings auf Kosten der Lesbarkeit und Verstädnlichkeit etc.).
Für Hochperformantes ist Assembler aber erste Wahl.

Ich habe gehört CUDA wäre für so etwas geeignet.

It depends. 🙂
Geeignet ist es zwar wunderbar, allerdings nur, wenn dir eine (mindestens) Mittelklasse-NVidia-GPU zur Verfügung steht.

Oft kann man sehr viel Tempo gewinnen, wenn man sich wiederholende Berechnungen in Tabellen vor berechnet.

Hat man früher schon gemacht, z.B. Tabellen für Potenzen.

mfg Hajoseb

Hallo,

kommt drauf an was du zur Verfügung hast. Auf der CPU ist Fortran immer noch eine Macht, wenn es um numerische Berechnungen geht. Den Intel-Compiler bekommst du für Linux + Noncommercial use kostenlos. Echt geil das Ding 😃

CUDA bzw. OpenCL ist nur dann sinnvoll, wenn du die Aufgabe splitten kannst und sie unabhängig von einander sind.
Ein kleines Beispiel findest du unter:
http://jogamp.org/jocl/www/

Hallo,

Oft kann man sehr viel Tempo gewinnen, wenn man sich wiederholende Berechnungen in Tabellen vor berechnet.

So ist es - schau dir hierzu mal Memoization an.

CUDA bzw. OpenCL

Nur um das klarzustellen: CUDA ist von nVidia die API für GPGPU und mehr oder weniger das Gleiche wie ATI bzw. AMD mit dem ATI Steam bietet. OpenCL versucht einen plattformunabhängigen Standard zu schaffen. Je nach Grafikkarten wird bei OpenCL dann tatsächlich CUDA oder ATI Stream verwendet.
Somit sind CUDA, etc. auch keine Programmiersprachen sondern APIs für den Zugriff auf die GPU.

D.h. auch wenn du CUDA verwendest und das Programm weitergeben willst so musst du als Hardware-Voraussetzung eine nVidia-Grafikkarte voraussetzen. Deshalb ist der Weg über OpenCL der bessere denn dieses unterstützt auch den Modus dass keine kompatible GraKa vorhanden ist und dann wird halt auf der CPU gerechnet. In Hinsicht auf die Verteilung der Software ist das parkatischer 😉

Was bisher genannt wurde setzt auf OpenGL-Shader und Texturen auf. Von Mircosoft gibt es selbiges für DirectX mit dem MS Accelartor-Projekt von MS Research. Auch hier werden (ab v2) mehrer Modi unterstützt (also CPU wenn die GraKa nicht passt).

Beachte aber bei der GPGPU dass es einige Einschränkungen gibt und v.a. der Datentransfer zwischne Host-Speicher und Device-Speicher sehr langsam ist (wegen der Bus-Verbindung). Als grobe Richtlinie kann gesagt werden dass sich GPGPU erst ab 10e6 Vektor-Elementen lohnt - sonst sind die Speichertransfer-Kosten zu groß.
Auch die Größe der GPU-Targets ist (nach oben) limitiert. Sie entspricht der maximalen Größe einer Textur die verarbeitet werden kann. Mit aktuellen GraKas sind das für eine Tensor 2. Stufe 64e6 Elemente - mit älteren GraKas 16e6 Elemente.
Weiters gibt es nicht unbedingte die beste Unterstützung für double da die GraKa intern mit floats rechnet. Die double (sofern benötigt) müssen "simuliert" werden - OpenCL in der neuesten Version unterstützt dies, aber dabei sinkt die Laufzeit auf knapp die Hälfte. MS Accelarator zwar theoretisch (es gibt den Datentyp dort) aber die Umsetzung ist nicht erledigt.

Aber auch mit .net und mehreren Kernen lässt sich der Code schon um einiges schneller abarbeiten. Ob sich letzten Endes GPGPU lohnt kann nur ein Performance-Vergleich zeigen.

Wie Siassei schon angemerkt hat ist Fortran auf der CPU die effiziente Sprache (aber nur für numerische Berechnungen) bzw. bietet die besten Compiler. Siehe auch Performancebetrachtungen Fortran - C#
Ich nutze daher für zB sehr aufwändige CFD-Simulationen von C# aus eine Fortran-DLL (die als C-style kompiliert wurde). Das ist immer noch um einiges schneller als parallelisierter .net-Code. Zumal es ja auch Fortran-Compiler für die Parallelisierung gibt (die sind aber sehr teuer).

Wenn du die Fraktalberechnung auslagern willst dann wäre es auch sinnvoll die Zeichnung direkt in OpenGL (bei Verwendung von CUDA, ATI Stream oder via OpenCL) zu ermöglichen denn sonst ist das Zeichnen mit GDI+ die Bremse.
Mit OpenCL ist es möglich direkt auf OpenGL zuzugreifen so dass "alles" in der GPU passiert.

mfG Gü

Vielen Dank für die zahlreichen Vorschläge. Werde alle Möglichkeiten mal testen und einen Performancevergleich machen.

Gruss Aratar

Hi Aratar

Ich habe auch vor kurzem mehrere Fraktale auf c# umgesetzt und mir ist auch die relativ lange laufzeit aufgefallen! Nur habe ich nicht sehr viel Ahnung von effizienten Funktionen und Ineffizienten 😄. Deshalb habe ich z-B bei der Mandelbrotmenge jeden Punkt einzeln über CreateGraphics() gezeichnet 😄. In anderen Implementierungen habe ich herausgefunden, dass meistens mit bitmaps gearbeitet werden.

Gleichzeitig habe ich entdeckt, dass Multithreading gar keinen grossen Unterschied macht:

• Core i7 920 -> 8 Threads / 4cores

Das Programm wurde nur ca. 0.875 schneller. Gleichzeitig ist im Taskmanager ersichtlich, dass die Gesamtauslastung nie über 33% gestiegen ist, was mich sehr iritiert. Müsste die Auslastung nicht höher sein?

mfg Moschn

Hallo Moschn,

Das Programm wurde nur ca. 0.875 schneller.

Also um 12,5% langsamer 😉
Für einen Speed-Up müsste der Faktor > 1 sein.

So wie du zeichnest wird der Zeichenvorgang nur in 1 Thread durchgeführt. Von daher ist das normal. Das wären im Idealfall bei einem Quad-Core 25% Auslastung. Das mehr auf die 33% kann von der Berechnung kommen welche auf anderen Cores/Threads durchgeführt wird. Genaueres liefert dir aber ein Profiler.

Das Zeichnen in ein Bitmap kann schon schneller sein als direktes Zeichnen in GDI+ (Graphics). Noch schneller ist eben wenn die GPU das Zeichnen übernimmt (DirectX, OpenGL).

mfG Gü

Außerdem sind Threads sowiso nicht die beste Wahl unter Visual Studio 2010 wurde die TPL eingeführt, die bei komplexen Rechnungen um etliches schneller geht.
Aber C# würde ich nicht empfehlen, da C# unter .Net laüft und daher eh langsamer ist. Ich empfhele Assambler. Oder C++ , da C++ einmal C# sehr ähnlich ist und zum anderen schon fertigen Code erzeugt

Hallo,

Außerdem sind Threads sowiso nicht die beste Wahl unter Visual Studio 2010 wurde die TPL eingeführt, die bei komplexen Rechnungen um etliches schneller geht.

Der erste Teil der Aussage stimmt bedingt, aber der zweite ist Unsinn.
Die TPL vereinfachte die Multithreaded Programmierung und ist daher oft vorzuziehen, aber ist nicht schneller oder langsamer als multithreaded Programmierung "von Hand" mit den Threads. Die TPL verwendet selber Threads aus dem ThreadPool zur Taskausführung. Die TPL verleitet den unwissenden Programmierer sogar eher dazu schlechten multithreaded Code zu schreiben weil man denkt man müsse die Grundprinzipien der multihtreaded Programmierung nicht berücksichtigen.

da C++ einmal C# sehr ähnlich ist und zum anderen schon fertigen Code erzeugt

Den fertigen Code erzeugt wohl der Programmierer oder ein Tool und nicht eine Sprache bzw. dessen Compiler. C++ und C# sind auch nur in der Hinsicht ähnlich dass beide ein "C-Dialekt" und OO-Sprachen sind, sonst gibts keine Ähnlichkeit.

Es gibt auch Fälle wo .net-Programme schneller sind als C++-Programme - suche mal danach.

mfG Gü

hallo gfoidl

Also um 12,5% langsamer 😉
Für einen Speed-Up müsste der Faktor > 1 sein.

das heisst dann einfach die vorherige Zeit * 0.875
-> 12.5% schneller^^

So wie du zeichnest wird der Zeichenvorgang nur in 1 Thread durchgeführt. Von daher ist das normal. Das wären im Idealfall bei einem Quad-Core 25% Auslastung. Das mehr auf die 33% kann von der Berechnung kommen welche auf anderen Cores/Threads durchgeführt wird. Genaueres liefert dir aber ein Profiler.

Ich zeichen aber in jedem Thread! Wieso zeichnet dann nur ein Thread?

Das Zeichnen in ein Bitmap kann schon schneller sein als direktes Zeichnen in GDI+ (Graphics). Noch schneller ist eben wenn die GPU das Zeichnen übernimmt (DirectX, OpenGL).

Bitmap ist schneller, habe ich ausprobiert, aber noch nciht gemessen 😄

mfg Moschn

Hallo,

Ich zeichen aber in jedem Thread! Wieso zeichnet dann nur ein Thread?

Weil GDI+ (bzw. der .net-Zugriff) dann global synchronisiert wird so dass immer nur 1 Thread tatsächlich (intern) zeichnet. Egal wieviele Threads in deinem Programm zeichnen.

mfG Gü

Danke gfoidl!

Ich bin trozdem noch irritiert da, die Auslastung meiner CPU (Obwohl ich in einer Bitmap ziechne) immer noch nicht über 13% (mit einem Thread) ausgeht X(

mfg Moschn

Hallo Moschn,

ich weiß nicht wie bei dir gezeichnet wird und deshalb kann ich nur mutmaßen.
Single-Threaded 13% und Multi-Threaded 33% bei Quad-Core kann hier auch davon kommen dass zwar nur 1 Thread zeichnet aber es passiert ja wohl noch mehr als nur zeichnen - wie zB die Berechnungen des Fraktals. Beim Multi-Thread könnte das Zeichnen somit auf einem Core erledigt werden der voll ausgelastet ist (25%) während ein anderer Core die restlichen 8% übernimmt (= 33%).
Beim Single-Thread muss alles dieser eine erledigen. 25% - 8% = 17%, dann fehlen noch 4% auf die 13% und diese 4% könnten für die Windows-Nachrichtenschleife verwendet werden.

Aber wie gesagt ist diese Zahlenspielerei reine Mutmaßung. Für genaueres müsstest du einen Profiler verwenden (wie zB den in VS 2010 Premium/Ultimate) und dort kannst exakte Zahlen erhalten.

mfG Gü

hallo gfoidl

ich weiß nicht wie bei dir gezeichnet wird und deshalb kann ich nur mutmaßen.
Single-Threaded 13% und Multi-Threaded 33% bei Quad-Core kann hier auch davon kommen dass zwar nur 1 Thread zeichnet aber es passiert ja wohl noch mehr als nur zeichnen - wie zB die Berechnungen des Fraktals. Beim Multi-Thread könnte das Zeichnen somit auf einem Core erledigt werden der voll ausgelastet ist (25%) während ein anderer Core die restlichen 8% übernimmt (= 33%).
Beim Single-Thread muss alles dieser eine erledigen. 25% - 8% = 17%, dann fehlen noch 4% auf die 13% und diese 4% könnten für die Windows-Nachrichtenschleife verwendet werden.

Ich habe das jetzt auch gerade überlegt und bin dann auf einen anderen Schluss gekommen. ich habe 8 Threads in meiner CPU
-> 100 / 8 = 12.5 = ca. 13 😄

Deine überlegung kann gar ned stimmen, da das Zeichnen ja ausgelagert wird und somit auf einem eigene Thread ausgeführt wird. somit steht dem Berechnen die volle Leistung eines Cores/Threads zur Verfügung, die er nicht vollständig ausnützt (13% / 25%). Und 12% für die Windows Nachrichtenschleife? Ist irgendwie zu hoch 😉

und ja ich werde mir bald das vs2010 ultimate zulegen und dann kann ich ja ermitteln, wo die HotSpots sind.

mfg Moschn

Deine Berechnungen sind durchdacht, vollständig und komplett falsch.

Deine 8 Threads können rechnen so schnell sie wollen, wenn sie immer wieder auf den einen Thread warten müssen der gerade per GDI+ zeichnet, stehen sie alle, und damit steht dir nur die Rechenleistung dieses einen Threads zur Verfügung.

Wenn du nicht auf VS Ultimate warten willst, einer der schnellsten Profiler ist der von Equatec, und den gibt es auch kostenlos ( die Einschränkungen sind verkraftbar).
http://www.eqatec.com/tools/profiler/

Hallo Moschn,

Deine überlegung kann gar ned stimmen, da das Zeichnen ja ausgelagert wird und somit auf einem eigene Thread ausgeführt wird. somit steht dem Berechnen die volle Leistung eines Cores/Threads zur Verfügung,

Warum kann die Überlegung nicht stimmen? Kannst du das begründen? (Musst du mir aber nicht zeigen 😉
Wann und wohin wirds denn ausgelagert?* Und dann zeichnet nur 1 Thread und die anderen Threads die Berechnen werden mit diesem Thread synchronisiert, d.h. sie warten auf diesen. Oder schreibst du die Berechnungen in einen Buffer und der Zeichen-Thread liest aus diesem und zeichnet -> Producer/Consumer (wäre IMHO besser so).

* zuerst gehts vom .net-Wrapper Graphics zum GDI+-Objekt Graphics und dann wirds entweder in der CPU (im selben Thread) oder auf der Hardware gerendert. Das Ganze erfolgt aber synchron und somit ist die Hardwareunterstützung nur ein Beschleuniger des sync. Vorganges.

die er nicht vollständig ausnützt (13% / 25%). Und 12% für die Windows Nachrichtenschleife?

Eben hast du vorgerechnet dass 100/8 = 12,5 ~ 13 ist. Wieso verwendest du jetzt wieder die 25? Dass passt nicht zusammen 😉

Zu beachten sind dabei aber auch folgende Dinge welche die Leistung vom theoretischen Ideal unterscheiden können:*False Sharing - wird hier höchstwahrscheinlich ein Bremse sein *dass die 8 Hyper-Threads nicht voll genutzt werden - es gibt ja nicht 8 Kerne, sondern "nur" 4 und die Hyper-Threads füllen die Leerzeiten eines Kerns aus -> wenn die Auslastung hoch ist kann kein "Loch" gestopft werden *usw.

Also trotz 8 Threads gibts nur 4 Kerne die rechnen 😉

mfG Gü

Hi all

stimmt nach überdenken meiner Aussagen, komme ich zum schluss dass sie wirklich komplett falsch waren 😄

Das mit dem Buffer wäre aber eine gute Idee... Mal schauen ob ich die umsetz...

mfg
Moschn

Hallo,

Bei Grafikprogrammierungen ist es vermutlich besser mit Zeigern zu arbeiten.
Hierzu musst du im "unsafe" Modus arbeiten.

Aber dann wird auch C# rasend schnell 8o

anbei ein Codefragment wie man z.B. ein Bitmap in 8-bit Gruastufen verwandelt:

private Bitmap BildSW(Bitmap bmp)
{
    int numBytes = bmpData.Stride * bmp.Height;
    byte[] rgbValues = new byte[numBytes];
    int tmpSW;
    
    PixelFormat pxf = PixelFormat.Format24bppRgb;
	
    Rectangle rect = new Rectangle(0, 0, bmp.Width, bmp.Height);
    BitmapData bmpData = bmp.LockBits(rect, ImageLockMode.ReadWrite, pxf);
	
    IntPtr ptr = bmpData.Scan0;
	
    Marshal.Copy(ptr, rgbValues, 0, numBytes);
	
    for(int counter = 0; counter < rgbValues.Length; counter+=3)
    {
        tmpSW  = rgbValues[counter];
        tmpSW += rgbValues[counter+1];
        tmpSW += rgbValues[counter+2];
        
    	tmpSW /= 3;
    	
    	rgbValues[counter] = rgbValues[counter+1] = rgbValues[counter+2] = Convert.ToByte(tmpSW);
    }
    
    Marshal.Copy(rgbValues, 0, ptr, numBytes);
	
    bmp.UnlockBits(bmpData);

    return bmp;
}