Kann man das noch optimieren? (Mandelbrot-Berechnung)

drakon

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.

*Q* 1

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.

hustbaer

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

Athar

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.

hustbaer

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.

drakon

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.

Bashar

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

hustbaer

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)

Bashar

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

Athar

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.

*Q* 1

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.

*Q* 1

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!

Ethon

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ä.)

*Q* 1

Q schrieb:

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

Ethon

Wenn die Größe eingrenzbar ist, wäre möglicherweise eine Fixed-Size-Lösung anzuraten. Ich glaub mal dass die Dynamik von GMP sicher auch einige Zeit verschlingt. Im Vergleich könnte eine Template-Lösung, die auf dem Stack lebt, und die selben Algorithmen wie GMP nutzt (nur halt fixed-Size optimiert), doch noch Einiges einsparen.

*Q* 1

Die Größe ist eingrenzbar.

Das kann sein, dass das was bringen würde. Aber woher kriegt man eine hochoptimierte template-lösung?
MPIR benutzt übrigens standardmäßig alloca als allocator, dann sollte das nicht so viel ausmachen, oder?

Und innerhalb der schleife werden nur sehr wenige neue objekte angelegt. Ich könnt das auch auf 0 reduzieren, ich glaub das versuche ich gleich mal und gucke, obs dadurch schneller wird.

Ok, vielleicht bleibt immer noch optimierungspotenzial, weil der compiler mehr informationen hat.

SeppJ

Betreffend Compilerflags:
Beim Intelcompiler (und eigentlich jedem anderen Compiler) kannst du noch die Architektur angeben, auf die optimiert werden soll. Mit nur O3 wird nur auf 386er (für 32-Bit Code) oder auf einen generischen x86-64 Prozessor mit SSE2 (für 64-Bit Code) optimiert. Spezielle Prozessorfeatures bleiben so ungenutzt und besondere Eigenschaften unbeachtet. Wie genau die Flags lauten steht in der Anleitung, insbesondere im Optimierungshandbuch. Was bei mir auch öfters viel gebracht hat ist die IPO, bei der die Optimierung erst zur Linkzeit durchgeführt wird und die fast-math Optionen. Letztere verändern jedoch teilweise die Semantik des Programms - lies dir unbedingt durch, was die genau machen und verstehe, was du da tust.

Compileroptionen für ein configure-Skript übergibt man niemals so wie du es versucht hast. Dazu nutzt man die Variablen CFLAGS (für C) bzw. CXXFLAGS (für C++). Diese setzt du entweder global oder als Kommandozeile des configure-Skripts.

Bezüglich Komprimierung: Zur libz gibt es einen kleinen Wrapper für komprimierte Dateistreams. Da brauchst du am Programm bloß zwei Zeilen ändern (zumindest sofern du vorher schön sauber programmiert hast. Hast du doch, oder? ) und dann wird automatisch komprimiert gelesen und geschrieben.

*Q* 1

Das mit den compilerflags werd ich mir mal genauer angucken.
Allerdings glaube ich nicht das es allzuviel bringen wird, da die hauptarbeit von der MPIR bibliothek gemacht wird, die dynamisch dazugelinkt wird.

Wichtiger ist vermutlich die konfiguration des configure skripts für MPIR.

Wie meinst du das denn mit "oder über die Kommandozeile"?
Ich habe es ja über die Kommandozeile gemacht.

./configure --XYZ=core
nur weiß ich nicht, was zu XYZ hinmuss.

Meinst du das muss dann
./configure CFLAGS=XYZ=core sein oder so?

Und das mit dem wrapper ist natürlich eine schöne sache. Ich habe bisher alles in cout reingeschrieben und die ausgabe beim programmaufruf in eine datei umgeleitet.
Es gab da nämlich Probleme mit MPI, evtl. weil der Prozess der in die Datei schreibt dann auf einem anderen Computer ausgeführt wurde. Aber ich werd das nochmal versuchen. Statt cout einen anderen stream zu nehmen ist ja keine große Sache.
Wie ist das denn dann mit dem einladen? Also erstens - kann ich das einfach mit winzip entpacken? Und ansonsten, wenn ich das jetzt mit einem C# oder Java Programm entpacken will, ist das ohne viel Aufwand möglich? Wahrscheinlich dann eher nicht, oder?

Edit: Ok das mit cout war unnötig, ich hab gerade nochmal nachgeschaut, das mit der auzsgabe direkt in eine datei hatte früher nur nicht geklappt, weil ich ausversehn fstream statt ofstream genommen hatte. (Ich hatte nur den konstruktor aufgerufen und dann geschaut, ob die datei erstellt wird)

SeppJ

Du musst doch schonmal ein configure-Skript benutzt haben? Hier der Crashkurs:

./configure CC="dein C Compiler" CFLAGS="deine C-Compileroptionen" LDFLAGS="deine Linkeroptionen" --prefix=installationspfad

Alle Angaben natürlich optional. Für C++-Optionen CXX und CXXFLAGS. Und auch noch ganz wichtig:

./configure --help

:p

Aber ist bei weitem noch nicht alles, was du Nützliches darüber wissen kannst, bloß das was du wissen musst, um irgendwie klar zu kommen. Da die "configure, make, make install" Toolchain weit verbreitet ist, kann dir da eigentlich jeder helfen, der schonmal Software selber compiliert hat. Und das Internet auch. Kennst du denn niemanden, der dir da persönlich helfen kann?

Das Ausgabeformat der gzstreams ist, wie der Name schon sagt, gzip, also so ungefähr das am zweitweitesten verbreitete Kompressionsformat.

*Q* 1

Ich hab mir nochmal ein bischen die doku zu MPIR durchgelesen und da steht auch etwas von CFLAGS, das ist aber wohl zusätzlich zu anderen flags, die man einfach mit --flag angibt bei configure.

Wie das mit der richtigen CPU funktioniert, habe ichh immer noch nicht rausbekommen, aber ich habe jetzt --enable-fat aktiviert, was wohl einfach für jede cpu den passenden asm code generiert und zur laufzeit das passende auswählt. Einen spürbaren Geschwindigkeitsunterschied gab es allerdings nicht.

Ich habe jetzt noch ein Problem mit der Sache mit dem Zip.
Undzwar verteile ich tasks an worker, aber die Ergebnisse kommen aber nicht notwendigerweise in der "richtigen" reihenfolge an.
Bisher habe ich ja einen Buffer erstellt, der genug Platz für alle ergebnisse hat und wenn neue ergebnisse von den workern kommen, habe ich diese an die richtige stelle im buffer geschrieben.
Am Ende habe ich dann den ganzen buffer in die datei geschrieben.

Wenn ich jetzt aber den Buffer loswerden will (um so auch große mengen an daten verarbeiten zu können), dann kann ich die empfangenen ergebnisse nicht einfach immer direkt in die Datei schreiben, weil ich dort keinen random access zugriff habe (damit würde der Gzstream mit sicherheit nicht klarkommen).

Eine möglichkeit wäre, einen random access file zu erstellen, dareinzuschreiben und am ende die ganze datei zu zippen und die alte datei zu löschen.

Allerdings denke ich nicht das das eine gute Lösung ist.

Es wäre gut, wenn ich irgendwie mit einem recht kleinen buffer auskommen könnte, aber bisher ist mir dafür keine gute möglichkeit eingefallen.

Das einzige was mir eingefallen ist, ist einen zyklischen buffer zu erstellen, der die Ergebnisse von X tasks speichern kann. Und solange dann der task mit der niedrigsten noch im buffer enthaltenen nummer noch nicht abgeschlossen ist, können tasks über der nummer X noch nicht zugewiesen werden, sondern es mjuss erst gewartet werden.

Ich hoffe, das ist verständlich.
Habt ihr da noch Ideen zu?