3. Kann man das noch optimieren? (Mandelbrot-Berechnung)

Kann man das noch optimieren? (Mandelbrot-Berechnung)

  • B

    Da du schon an Inline-Assembler denkst: Hast du dir mal den generierten Code angeguckt?

    Ansonsten:
    Du berechnest die Quadrate pro Iteration zweimal. Falls der Compiler das nicht optimiert, immerhin ist der Wert iterationsübergreifend, dann könntest du dafür zwei extra Variablen einführen:

    int calculateNumIterations(mandelType x, mandelType y)
{
    mandelType x1=0, x2=0, y1=0, x1squared = 0, y1squared = 0;
    for(int i = 0; i < numIterations; ++i)
    {
        x2 = x1squared - y1squared + x;
        y1 = 2*x1*y1 + y;
        y1squared = y1*y1;
        x1 = x2;
        x1squared = x1*x1;
        if(x1squared  + y1squared > 4)
        {
            return i;
        }
    }
    return numIterations;
}
    0
  • D

    SeppJ schrieb:

    @SeppJ
    Compiler sind relativ schwache optimierer für solche kleine Sachen, weil sie so verdammt konservativ sind (ist auch gut so). Wenn man solche Stückchen von Auge anschaut kann man da durchaus recht viel rausholen, wenn man sich ein wenig mit der Arbeitsweise von CPUs auskennt (Caching, Pipelineing, Data dependencies, forwarding, aliasing etc.)

    Also ich habe das letzte halbe Jahr damit verbracht, herauszufinden, dass dies nicht so ist.

    Also ich habe schon sehr einfache Strukturen gesehen, die sehr gut optimierbar waren, wenn man nur ein paar Anweisungen vertauscht. Wenn man dem nicht bewusst ist, dann verliert man da Power. Kann gut sein, dass du da einiges mehr Erfahrung hast, aber finde es halt auch plausibel, dass man da im feinen einiges besser von Hand optimieren kann als es ein Compiler überhaupt darf.

    0

  • Die einzelnen Pixel sind völlig unabhängig voneinander. D.h. du kannst mit SSE/AVX und Multithreading potentiell viel rausholen. Gegen eine Lösung im FragmentShader hat die CPU aber sicher keine Chance...

    0
  • O

    drakon schrieb:

    Also ich habe schon sehr einfache Strukturen gesehen, die sehr gut optimierbar waren, wenn man nur ein paar Anweisungen vertauscht.

    Dann musst du dem Compiler erlauben Operationen zu vertauschen. Beispiel beim Gcc -Ofast

    0
  • D

    otze schrieb:

    drakon schrieb:

    Also ich habe schon sehr einfache Strukturen gesehen, die sehr gut optimierbar waren, wenn man nur ein paar Anweisungen vertauscht.

    Dann musst du dem Compiler erlauben Operationen zu vertauschen. Beispiel beim Gcc -Ofast

    Sicher eine Möglichkeit, aber es gibt ja Optimierungen, die eigentlich nicht äquivalent sind, aber dann halt im jeweiligen Fall doch (weil man halt gewisse Umstände kennt, die ein Compiler nicht kenne kann) und da kann man auch mit solchen Einstellungen nichts gewinnen.
    Auf die schnelle kann ich kein gutes Beispiel bringen, aber ich denke ihr wisst was ich meine.
    Natürlich sollte man zuerst den Compiler ausreizen, aber dann kann es sich schon auch lohnen den generierten Code sehr gut anzuschauen.

    0
  • *

    Also erstmal zu multithreading:
    Das ganze läuft schon multithreaded. Die schleife wird für jeden Pixel aufgerufen.
    Ich habe den Bildschirm in "Tiles" aufgeteilt (je ca. 100x100 Pixel). Dann überegebe ich einem Threadpool die ganzen tiles zum rendern.

    NumIterations ist eine kompilezeitkonstante und hat normalerweise einen wert von ca. 500-3000. (Atm verwende ich 800).

    Wie wäre es rein theoretisch, wenn man die ganze schleife "entrollen" würde?
    Würde das eher schaden oder was bringen? Der code wird dadurch größer, was vermutlich schlecht für den cache ist, aber dann braucht man keine explizite schleife mehr.

    Und zum quadrat zweimal berechnen: Ich glaube das geht nicht besser, weil sich die werte zwischendrin auch ändern? Aber ich gucks mir gleich nochmal genau an.

    Ok danke für eure hilfe. Aber vermutlich werd ichs dann so belassen, weil ich mich mit asm nicht auskenne und das vermutlich auch nicht soooo viel bringen würde.

    Edit: Ich benutz übrigens MSVC. Hab einfach release mode genommen. Was kann man denn da noch so umstellen, was was bringen könnte?

    Edit2: Profiler hab ich benutzt (den vom visual studio 2010), der zeigt mir aber immer an das 99% cpu zeit auf einen slot (ich benuitze qt) draufgehen. Aber das zeigt er auch an wenn in dem slot gar kein code steht.
    Aber das liegt definitiv an der schleife. Das ist das Herzstück des algorithmus und wird für jeden Pixel aufgerufen.
    Setze ich die anzahl der iterationen runter, dann läuft das problem VIEL schneller. Es skaliert also direkt mit der anzahl der iterationen (~linear nehme ich an).

    0
  • B

    Q schrieb:

    Und zum quadrat zweimal berechnen: Ich glaube das geht nicht besser, weil sich die werte zwischendrin auch ändern?

    Tun sie ja nicht. Klar, innerhalb der Iteration schon, aber nicht von einer Iteration zur nächsten: Die Quadrate in deiner Abbruchbedingung sind die gleichen wie die am Anfang der nächsten Iteration.

    0
  • D

    Q schrieb:

    Wie wäre es rein theoretisch, wenn man die ganze schleife "entrollen" würde?
    Würde das eher schaden oder was bringen? Der code wird dadurch größer, was vermutlich schlecht für den cache ist, aber dann braucht man keine explizite schleife mehr.

    Loop unrolling beherrschen Compiler eigentlich recht gut, weil es klar ist, wie man das machen muss.

    Aber kannst es ja mal testen. Ich vermute aber, dass es nichts bringt, wenn du das von Hand selber machst.

    0
  • *

    Sind compiler denn so "verrückt" und unrollen loops die von 0 bis ~1000 gehen?
    Bzw ist sowas gang und gebe oder ist das eher schlecht, weils den code zu sehr aufbläht?

    Das mit den quadraten bau ich dann evtl. gleich mal ein.

    0

  • Ne, kein Compiler wird den loop 1000 fach ausrollen.
    Aber vielleicht 4-fach oder so.

    0
  • A

    Auf Loopunrolling seitens des Compilers würde ich wegen des ifs nicht gerade setzen.
    Man kann es manuell machen und die Tatsache ausnützen, dass die Abbruchbedingung (erst einmal erreicht) auch nach weiteren Iterationen wahr bleiben müsste.

    Ein Test auf zwei verschiedenen Prozessoren mit gcc 4.6 (Generierung eines 1680x1050-Bildes im Bereich (-2.1 | -1.3) bis (0.8 | 1.3) mit numIterations=1000):
    http://94.23.22.190/etc/phenom-ii-x4.png
    http://94.23.22.190/etc/atom.png

    Noch einmal mit der auf Wikipedia beschriebenen Optimierung:
    http://94.23.22.190/etc/phenom-ii-x4-opt.png
    http://94.23.22.190/etc/atom-opt.png

    Ich würde für 5-faches Unrolling plädieren.
    Ob es Unterschiede beim MSVC gibt, würde mich auch interessieren, allerdings muss ich mein Testsystem vorher noch um Wine-Unterstützung erweitern.

    0

  • Athar schrieb:

    Man kann es manuell machen und die Tatsache ausnützen, dass die Abbruchbedingung (erst einmal erreicht) auch nach weiteren Iterationen wahr bleiben müsste.

    Arrr, zu langsam 🙂
    Genau das ist mir auch gerade eingefallen, wollte ich gerade vorschlagen.

    0
  • D

    drakon schrieb:

    Sicher eine Möglichkeit, aber es gibt ja Optimierungen, die eigentlich nicht äquivalent sind, aber dann halt im jeweiligen Fall doch (weil man halt gewisse Umstände kennt, die ein Compiler nicht kenne kann) und da kann man auch mit solchen Einstellungen nichts gewinnen.
    Auf die schnelle kann ich kein gutes Beispiel bringen, aber ich denke ihr wisst was ich meine.

    Athar schrieb:

    Man kann es manuell machen und die Tatsache ausnützen, dass die Abbruchbedingung (erst einmal erreicht) auch nach weiteren Iterationen wahr bleiben müsste.

    Danke für das gute Beispiel! 🙂

    Perfect branch predictor gibts leider (noch) nicht.

    0
  • B

    Ich steh wohl grad auf dem Schlauch. Was genau bringt es, dass die Abbruchbedingung erfüllt bleibt, wenn sie es einmal ist?

    0

  • Dadurch kannst du das machen

    loop {
    save_state();
    step();
    step();
    step();
    step();
    step();
    if (cond) {
        restore_state();
        loop {
            step();
            if (cond)
                return;
        }
    }
}

    D.h. du musst nur pro N Steps 1x testen.
    Sonst könntest du zwar den Loop ausrollen, aber müsstest trotzdem nach jedem Step testen.

    (Alternativ zu save/restore/repeat könnte man auch ein Backlog der Z Werte schreiben, dann müsste man in der 2. Schleife nur den Test wiederholen, aber nix mehr rechnen)

    0
  • B

    Oh ja, danke. Wie gesagt, Schlauch... 🙂

    0
  • A

    Interessanterweise bringen die eingesparten Vergleiche und Multiplikationen weniger als erwartet. Möglicherweise deswegen, weil die Werte schnell +inf erreichen und sich die CPU evtl. bei Berechnungen mit diesen schwertut (geraten, aber unwahrscheinlich). Hat vermutlich eher mit dem Cache bzw. Sprungweiten zu tun.

    Der Atom profitiert zwar von den ausgelassenen Vergleichen, der Phenom aber nicht unbedingt. Hier mit Vergleich nach jeder Iteration:

    http://94.23.22.190/etc/phenom-ii-x4-opt-f.png
    http://94.23.22.190/etc/atom-opt-f.png

    Es bleibt aber dabei, dass 5-faches Unrolling mit einem Vergleich alle 5 Iterationen insgesamt am besten zu sein scheint.

    0
  • *

    Vielen Dank, dass du dir so viel Mühe machst!
    Soll ich dann versuchen beim MSVC das unrolling zu konfigurieren oder sowas oder manuell machen?

    Ich fange gerade auch an mit der fragment-shader implementierung, allerdings gibts da ein paar schwierigkeiten, weil ich ja auch fixed point einbaun will.
    Ich brauch da operatinen wie z.B. bitweises und, dass die Graka von meinem laptop leider nicht kann, deswegen muss ich das dann leider alles am Desktop-PC entwickeln.

    Auch unterstützt glsl keine 16bit-datentypen.

    Meine derzeitige fixed-point-planung sieht so aus:

    (Wird dann in glsl wohl geringfügig anders aussehen)

    const int numMantissaInts = 8; //änderbar

struct FixedPoint
{
   uint data[1 + numMantissaInts]; //bei glsl heißts uint und nicht unsigned int
};

//oder einfach:
typedef uint FixedPoint[1 + numMantissa]; //ist die syntax (bei c++) so richtig?
// Glsl hat afaik eh keine typedefs, 
//aber ich kanns dann ja einfach das array so verwenden, 
//oder die struct.

    das erste element des arrays hat eine besondere bedeutung:
    es speichert gleichzheitig das vorzeichen und die zahlen vorm komma.
    Ein bereich von -16..16 als ganzzahlanteil reicht völlig und dazu ein flag. der rest bleibt unenutzt.

    Jeder uint danach steht jeweils für die nächsten 32 nachkommastellen (im 2er system).

    Beim Berechnen von addition/multiplikation werde ich dann mit einer schleife von hinten nach vorne dadurch gehen.
    Dabei werde ich dann jeden uint in 2 teile teilen um einen überlauf zu vermeiden.

    Also mal angedeutet als beispiel:

    uint x1, x2;
//x1 und x2 werden addiert
uint x11 = (x1 & 0xFFFF0000u) >> 16;
uint x12 = x1 & 0x0000FFFFu;
uint x21 = (x2 & 0xFFFF0000u) >> 16;
uint x22 = x2 & 0x0000FFFFu;

uint sum1 = x12 + x22;
uint uebertrag1 = (sum1 & 0xFFFF0000u) >> 16;
uint sum2 = x11 + x12 + uebertrag1;
uint uebertrag2 = (sum2 & 0xFFFF0000u) >> 16; // wird für die stellen weiter vorne 
//verwendet (die im moment nicht beachtet werden)

uint sum = (sum1 & 0x0000FFFFu) | ((sum 2 & 0x0000FFFFu) << 16);

    Ich hoffe, dass das prinzip nachvollziehbar ist, dass ich keine fehler eingebaut hab und vor allem, dass moderne Grafikkarten bitweise operationen performant durchführen können.
    Das hat zwar ziemlichen overhead, aber ich wüsste nicht, wie ich fixed-point-arithmetik besser implementieren kann.
    Hat jemand (verbesserungs-)Vorschläge?

    Edit: Nur um verwirrungen vorzubeugen: Auch wenn die variablen hier ähnlich wie bei der Mandelbrotformel heißen - hier geht es nicht um berechnung dieser formel, sondern nur um die realisierung von fixed point arithmetik.

    0
  • *

    Ich beleb den Thread mal wieder, weil ich mich inzwischen wieder damit beschäftige.

    Ich habe jetzt eine Implementierung geschrieben, die MPI und OpenMP verwendet und auf einem Cluster ausgegführt werden soll.
    Außerdem verwende ich die MPIR bibliothek für genauere floating-point-berechnungen.

    Auch hier will ich wieder kräftig optimieren 🙂

    Es gibt da jetzt ein paar Sachen, die ich im Moment untersuche:

    1. In der Anleitung zu MPIR steht, dass das schneller läuft, wenn man es auf die richtige CPU konfiguriert, da dann optimierter asm-code benutzt werden kann. (Siehe http://www.mpir.org/mpir-2.5.1.pdf Seite 11)
    Dort wird angedeutet, wie man das einstellen kann.
    Bisher habe ich einfach ./configure und dann make gemacht.
    Ich habe ein bischen recherchiert und glaube, dass das Cluster die 'core' Architektur hat (es sind dort Intel Xeon E5450 @ 3.00GHz verbaut).
    Allerdings weiß ich nicht, wie ich dem "configure"-Programm sage, welche Architektur er nehmen soll.
    Mit

    ./configure core

    funktioniert es nicht.
    dann habe ich

    ./configure march=core

    versucht, das klappt sogar.
    Allerdings habe ich dann testweise mal versucht:

    ./configure march=fgiosdhiogdhidvshisdf

    und das ging auch, also glaub ich eig nicht, dass das geklappt hat mit dem core.

    Auf der Seite davor steht etwas von:
    Cross Compilation, ‘--host=CPU-VENDOR-OS’
    Ich denke, dass das evtl. das richtige ist, bin mir aber nicht sicher, was ich dann als vendor und os angeben muss.
    Habt ihr eine Idee, wie das geht?

    2. Kann ich vielleicht mit den Compilerflags noch was rausholen? Im moment kompiliere ich mit

    mpicc Main.cpp Worker.cpp Master.cpp Common.cpp -I mpir-2.5.0 -L mpir-2.5.0/.libs -lmpir -Wall -O3 -fopenmp -fomit-frame-pointer -o mandelbrot.out

    Wobei mpicc ein intelcompiler ist.

    3. Ich werde nachher mal einen Profiler für parallele Programme drüber laufen lassen, aber ich bin nach wie vor der Meinung, dass die Funktion "CalculateNumIterations" das bottleneck ist.
    Ich habe diese auch schon optimiert, so das temporaries vermieden werden und berechnungen (quadrat) nicht mehrfach gemacht werden.
    Das hat auch ganzschön was gebracht, die Laufzeit eines Beispielszenarios hat sich von 357.603s auf 97,23s reduziert.

    Der aktuelle Code dazu sieht so aus (wobei mandelType ein typedef für mpf_class ist, was quasi ein BigFloat ist, den ich im Moment auf mindestens 512 bit genauigkeit eingestellt habe).

    int CalculateNumIterations(const mandelType& x, const mandelType& y)
{
	mandelType x1 = x, y1 = y;
	mandelType xQuad = x * x, yQuad= y * y;
	for(int i = 0; i < numIterations; ++i)
	{	
		y1 *= x1;
		y1 *= 2;
		y1 += y;

		x1 = xQuad;
		x1 -= yQuad;
		x1 += x;

		xQuad = x1 * x1;
		yQuad = y1 * y1;

		if(xQuad + yQuad  > 4)
		{
			return i;
		}
	}
	return numIterations;
}

    Hinweis: numIterations hat typischerweise einen Wert von 1000-10000. Mehr als 1 Million wird es so gut wie sicher nicht.
    Und bitte dran denken, dass das keine normalen doubles sind, sondern klassen mit überladenen operatoren.

    Seht ihr da noch optimierungspotenzial?

    4. Die Ausgabedatei wird inzwischen ziemlich groß (z.B. 100 MB oder mehr), aber wenn ich winrar dadrauf loslasse, bleibt meist < 1MB übrig. Deswegen habe ich mir überlegt, die daten am besten schon komprimiert in die Ausgabedatei zu schreiben, dan dauert das rüberkopieren vom Cluster auf meinen Rechner auch nicht mehr solang. Dabei wäre es gut, wenn die komprimiering "on the fly" erfolgen kann, also das ich nicht erst alle Daten im Speicher haben muss und dann alles auf einmal komprimiere, sondern das das "inkrementell" passieren kann.
    Ich habe mir überlegt, evtl. mal die zlib anzugucken, aber erstens weiß ich nicht, ob die eine solche inkrementelle komprimierung unterstützt und außerdem ist es immer extraaufwand mit externen Bibliotheken.
    Meine andere Idee ist, selbst eine LZW Komprimierung zu implementieren. Das verfahren ich recht einfach und ich habe das schonmal in java implementiert. Außerdem kann das auch inkrementell eingestzt werden. Allerdings bin ich mir unsicher, inwiefern das gute Kompressionsraten bringt.
    Kennt ihr da vielleicht noch eine gute Alternative?
    Die Ausgabedateien sind im Moment einfach eine lange reihe von zahlen die im Werteberech [0, numIterations] liegen (wobei numIterations so ca. 1000 - allerallerhöchstens 1Million groß ist), die mit Komma getrennt sind.
    Falls möglich, will ich die komprimierten dateien auch mit anderen Programmiersprachen verarbeiten können. Beim LZW wäre das möglich, weil ich den sowieso selbst implementieren würde.

    Vielen Dank für eure Hilfe!

    0
  • E

    Was ist mandelType? Da es wohl ein Integer ist, probier doch mal einen äquivalenten fast-typedef aus cstdint, falls du das nicht schon machst. (Also std::uint_fast32_t statt std::uint32_t oä.)

    0
Anmelden zum Antworten