Mandelbrot SSE

Gast #3408529
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.
1
int testEscapeSeriesForPoint(complex float c, int maxIterations, complex float * last)
2
{
3
  int iteration = 0;
4

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

9
  }
10
return iteration;
11
}

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!
Gast #3408561
...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?
Gast #3408577
ä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!
Gast #3408579
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.
Gast #3408585
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.
#3408601
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.
#3411711
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.
Gast #3417253
Danke für eure Beiträge !!

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

Antwort schreiben

Eine eigene Frage? Dieser Thread ist über 13 Jahre alt. Stell sie in einem eigenen Thread – dort lesen mehr Leute mit, und sie wird öfter und schneller beantwortet.

Neuen Thread starten

Eine Lösung, Ergänzung oder Rückmeldung zu diesem Thread? Dann antworte hier.

Formatierung
  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] – Link zu einem Artikel
  • Verweis auf einen anderen Beitrag: Rechtsklick auf dessen Beitrags-ID (#8078628), „Adresse kopieren“, in den Text einfügen

Mehr zur Formatierung

Längeren Sourcecode als Anhang, nicht in den Text. JPG nur für Fotos und Scans; Zeichnungen und Screenshots als PNG oder GIF. Siehe Bildformate.

Schon registriert? Anmelden

Wird nicht angezeigt. Wir schicken dir einen Link; sobald du damit bestätigst, erscheint dein Beitrag.

Mit dem Abschicken legst du einen kostenlosen Account an und erkennst die Nutzungsbedingungen und die Datenschutzerklärung an.