[gelöst] Verschachtelte For-Schleife parallelisieren

Nemic

Hallo,

ich habe ein Problem mit der Parallelisierung von For-Schleifen mit OpenMP. Ich habe eine Funktion erstellt, die ein Bild mit einem Gauß-Kernel glättet. Da der Kernel groß werden kann ist die Berechnung sehr zeitintensiv und ich würde es daher gerne parallelisieren. Schematisch ist der serielle Code der folgende:

for(int y; y < height; y++)
    for(int x; x < width; x++)
    {
        for(mask_y; mask_y < mask_size; mask_y)
            for(mask_x; mask_x < mask_size; mask_x)
            {
                dFilter += bild(mask_x,mask_y) * kernel;
            }
            bild(x,y) = dFilter
    }

Ich würde gerne die äußerste Schleife parallelisieren, bin mir aber nicht ganz sicher ob die Summenbildung in der innersten noch das macht was sie soll. Könntet ihr mir da bitte helfen.

brotbernd

Wo ist denn dFilter definiert? Teilen sich tatsächlich alle Punkte das, oder steht das vielleicht hier

for(int x; x < width; x++)
    {
       double dFilter = 0;

Und dann musst du dir überlegen was passiert, wenn ein Thread bild(mask_x,mask_y) liest und ein anderer gerade dort bild(x,y) = ... schreibt, wenn das vorkommen kann, dass x==mask_x && y == mask_y .
Vielleicht erweitrst du dein Bsp mal noch, dass man auch die Initialisierung und alle Typen sehen kann. Am besten was ausführbares.

Nemic

Der Code war wohl doch etwas zu knapp. Deine Annahme zu der Variable dfilter ist korrekt. Im Code ist außerdem noch ein Fehler, es gibt zwei Bilder (Eingabe und Ausgabe) sonst wäre es auch kein Gauß. Ich hab den Code einmal angepaßt.

for(int y = 0; y < height; y++)
    for(int x = 0; x < width; x++)
    {
        double dFilter = 0.0;

        //start_value ist abhängig von der Filtergröße 

        for(mask_y = start_value; mask_y < mask_size; mask_y)
            for(mask_x = start_value; mask_x < mask_size; mask_x)
            {
                dFilter += in_bild(mask_x,mask_y) * kernel;
            }
            out_bild(x,y) = dFilter;
    }

volkard

Nemic schrieb:

Im Code ist außerdem noch ein Fehler, es gibt zwei Bilder (Eingabe und Ausgabe)

Dann kannste parallelisieren wie wild.

brotbernd

Wenn mask_x und mask_y noch innerhalb der Schleife definiert sind, sollte es kein Problem geben. Es sei denn Bild::operator()(int, int) hat irgendeinen Nebeneffekt, der synchronisiert werden muss.

const double kernel = Kernel();
const int start_value = start(filtergroesse);
for(int y = 0; y < height; y++)
    for(int x = 0; x < width; x++)
    {
        double dFilter = 0.0;
        for(int mask_y = start_value; mask_y < mask_size; ++mask_y)
            for(int mask_x = start_value; mask_x < mask_size; ++mask_x)
            {
                dFilter += in_bild(mask_x,mask_y) * kernel;
            }
            out_bild(x,y) = dFilter;
    }

Nemic

Zum Verständnis, wenn ich dann so parallelisiere:

const double kernel = Kernel();
const int start_value = start(filtergroesse);
int x = 0;

#pragma omp parallel for private(x)
for(int y = 0; y < height; y++)
    for(x = 0; x < width; x++)
    {
        double dFilter = 0.0;
        for(int mask_y = start_value; mask_y < mask_size; ++mask_y)
            for(int mask_x = start_value; mask_x < mask_size; ++mask_x)
            {
                dFilter += in_bild(mask_x,mask_y) * kernel;
            }
            out_bild(x,y) = dFilter;
    }

was wird dann genau parallel bearbeitet? Meine Vermutung ist, dass die äußerste Schleife aufgeteilt wird und vereinfacht gesprochen jeder Thread einen Durchlauf dieser Schleife bearbeitet. Ist das korrekt?

in dem Fall werden verschiedene Zeilen des Bildes parallel berechnet.

Nemic

Damit ist mir sehr geholfen, vielen Dank an alle.