Mandelbrot SSE

[R-Sin (Gast)]

Hey Leute,

ich muss für die Uni ein Programm schreiben, welches die Mandelbrotmenge 
ausgibt.

Die Serielle Berechnung des Bildes funktioniert bei mir, allerdings 
müssen wir das ganze in SSE implementieren damit man das Praktikum 
besteht bei uns und ich habe überhaupt kein Plan mehr.

int testEscapeSeriesForPoint(complex float c, int maxIterations, complex float * last)
{
  int iteration = 0;

      while(cabsf(*last)<=RADIUS && iteration<maxIterations) {
    *last = (*last)*(*last) + c;
    iteration++;

  }
return iteration;
}

Wie kann ich denn sowas parallelisieren, ich habe doc das Problem, dass 
je nachdem was bei dem Parameter c ein Wert reinkommt, die While 
Schleife früher oder später fertig ist???

Danke für eure Hilfe!

[Torsten S. (tse)]

> ...ich habe überhaupt kein Plan...

Du hättest die Vorlesungen besuchen sollen.
SCNR

[dummbrot (Gast)]

...also ich kenne mandelbrotmengen nur als lustige bunte bilder, mit 
denen pann die performance seines rechners und seiner programmierkünste 
bestimmen/vergleichen kann... dein quelltext passt so garnicht zu meinen 
erinnerungen...

...und meiner meinung hat sse nichts mit parallelisierung zu tun...

aber mal angenommen, mein mandelbrot und diesen parallelisieren --> bei 
den allseits bekannten mandelbrot-algorithmen berechnet man immer einen 
ausschnitt, der durch xmin/ymin und xmax/ymax definiert ist. was folgt 
daraus?

[R-Sin (Gast)]

Herzlichen Glückwunsch,

ein konstruktiverer Beitrag ist dir nicht eingefallen?

[dummbrot (Gast)]

ähmm, doch:

dummbrot schrieb:
> aber mal angenommen, mein mandelbrot und diesen parallelisieren --> bei
> den allseits bekannten mandelbrot-algorithmen berechnet man immer einen
> ausschnitt, der durch xmin/ymin und xmax/ymax definiert ist. was folgt
> daraus?

vorausgesetzt meine beiden vorher getroffenen annahmen treffen zu, ...um 
dir mal wieder den ball zuzuwerfen!

[M-Sin (Gast)]

R-Sin schrieb:
> Wie kann ich denn sowas parallelisieren, ich habe doc das Problem, dass
> je nachdem was bei dem Parameter c ein Wert reinkommt, die While
> Schleife früher oder später fertig ist???

Willkommen in der Realität des parallelen Rechnens. Wenn das eine Pixel 
fertig gerechnet ist, sprich doch nichts dagegen, sich vom Chef ein 
neues für die Bearbeitung zu holen und damit weiter zu machen.

[R-Sin (Gast)]

Danke, dummbrot und m-sin

@m-sin: das konzept wo du gesagt hattest (zwei Threads laufen lassen und 
nach und nach die Pixel berechnen hatte ich auch gesehen). Allerdings 
müssen wir das mit SSE machen und ich weiß nicht wie ich das sinnvoll 
implementieren soll wegen dem oben genannten Problem.

[R-Sin (Gast)]

@dummbrot: mein Beitrag mit dem "herzlichen Glückwunsch..." war an den 
Torsten gerichtet!

[Falk S. (falkschilling)]

R-Sin schrieb:
> Die Serielle Berechnung des Bildes funktioniert bei mir, allerdings
> müssen wir das ganze in SSE implementieren damit man das Praktikum
> besteht bei uns und ich habe überhaupt kein Plan mehr.
> ..
> Wie kann ich denn sowas parallelisieren, ich habe doc das Problem, dass
> je nachdem was bei dem Parameter c ein Wert reinkommt, die While
> Schleife früher oder später fertig ist???

Was soll das heißen, parallelisieren? Für dich sind doch die SSE 
transparent als serielle Prozessorbefehle nutzbar, die Parallelisierung 
findet doch nur auf Befehlsebene des Prozessors statt. Stichwort 'Ebenen 
der Rechnerarchitektur'.

Du müsstest nur die richtigen Intrinsics deines Compilers aufrufen oder 
aber mittels inline asm die SSE nutzen. Würde aber die Intrinsics 
empfehlen, da die Datenübergabe per Clobber-Liste etwas unkomfortabler 
ist.

Oder sagtest du SSE und meintest Parallelisierung auf Threadebene mit 
sowas wie OpenMP? Dann reicht ein '#pragma omp parallel for' vor deiner 
Schleife aus, welche die Pixelposition linear in die komplexe Ebene 
abbildet und darauf die Mandelbrot-Iteration durchführt.

Ich habe irgendwie das Gefühl, du hast dich entweder etwas ungeschickt 
ausgedrückt oder die Art der Parallelisierung bei SSE nicht so richtig 
verstanden.

[Robert L. (lrlr)]

@R-Sin


schon mal über Wechsel des Studienfachs nachgedacht, ???


(nur sicherheitshalber, extra für dich: NICHT kopieren, nur zum Ideen 
holen)


erster (ERSTER!) google Treffer:
http://www.codeproject.com/Articles/12350/Generating-Fractals-with-SSE-SSE2




und das auf 4 threads aufzuteilen, die 4 teile berechnen sollte machbar 
sein??

[Karl H. (kbuchegg)]

R-Sin schrieb:

> Die Serielle Berechnung des Bildes funktioniert bei mir, allerdings
> müssen wir das ganze in SSE implementieren damit man das Praktikum
> besteht bei uns und ich habe überhaupt kein Plan mehr.

SSE ist doch eine Single Instruction, Multiple Data Architektur. D.h. 
die Paralleliserung findet dadzrch statt, dass dieselbe Operation auf 
vielen Datensätzen gleichzeitig durchgeführt wird.


> Wie kann ich denn sowas parallelisieren, ich habe doc das Problem, dass
> je nachdem was bei dem Parameter c ein Wert reinkommt, die While
> Schleife früher oder später fertig ist???

Dann musst du dir eben überlegen, wie du das umformen kannst, so dass 
die while Schleife für alle Pixel die gerade bearbeitet werden immer 
gleich oft durchlaufen wird. Unabhängig vom c. Ja, für einzelne Pixel 
kann das dann bedeuten, dass für sie ein paar ehrenrunden umsonst durch 
die Schleife gelaufen wird. Aber dafür werden eben 8 Pixel gleichzeitig 
bearbeitet.

[R-Sin (Gast)]

Danke für eure Beiträge !!

Habe es mittlerweile zum Laufen bekommen.. war doch nicht so schwer.... 
war wohl wieder mal gedanklich etwas blockiert .. ;-)