Verschachtelte Loop-Schleifen in Bloecke unterteilen?

[MartinB]

Ich versuche folgenden C Code, welcher zwei for-Schleifen enthaelt zu parallelisieren. Dies ist bereits getan, indem jede Zeile von einem Thread abgearbeitet wird.

#pragma omp parallel for private(nx, pos2,dy,dx,rlen,pos,xdiff,ydiff,zdiff,vmag,t) reduction (+:pe) shared(n,fx,fy,fz) schedule(static,chunks) num_threads(threads)

for (ny=0;ny<n;ny++){
for (nx=0;nx<n;nx++){

//loop over displacements
for (dy=MAX(ny-delta,0);dy<MIN(ny+delta+1,n);dy++){
for (dx=MAX(nx-delta,0);dx<MIN(nx+delta+1,n);dx++){

// CODE

}
}
}
}
MAX und MIN sind macros die verhindern dass ich an den Grenzen aus dem Array springe.

Das funktioniert auch wunderbar. Nun wuerde ich aber gerne anstatt einer zeilenweise Abarbeitung, das ganze gerne in Bloecke aufteilen. Angenommen n ist 4 und ich habe 4 Threads, dann soll jeder Thread Bloecke der Groesse 2*2 bearbeiten, bei n=16 und 4 Threads, 8*8 Bloecke, usw.

Nur komme ich nicht auf die Loesung.

[Gast]

Damit es blockweise Sinn macht muss dein Datenlayout auch passen. Ansonsten ist es einfach anstatt zwei Schleifen einfach nur eine.

[MartinB]

Ich wuerde gerne testen ob ich durch die blockweise Abarbeitung einen Performancezuwachs bekomme, wenn die Arraydimension ein Vielfaches einer Cacheline ist. Jeder Thread wuerde damit nur Kantenlaenge/Threadanzahl Cachelines laden.

Das gibt im Vergleich zu der zeilenweise Abarbeitung erstmal keinen Vorteil, denn auch dort wird die selbe Anzahl an Cachelines geladen, aber bei der Blockabarbeitung gibt es evtl. einen Performancegewinn weil ich aus verschiedenen Orten des Hauptspeichers lesen kann ohne dass es zu einem Konflikt kommt (System ist ein Dual-Socket i5 Blade, theoretisch also doppelte Bandbreite).

[MartinB]

Ok, falls es jemanden interessiert:

int size = sqrt((n*n)/threads);
int a =0;
int b = 0;

#pragma omp parallel for private(a,b,nx,ny ,pos2,dy,dx,rlen,pos,xdiff,ydiff,zdiff,vmag,t) reduction (+:pe) shared(n,fx,fy,fz) schedule(static,size) num_threads(threads)

for(b=0;b<n;b= b+size){

#pragma omp parallel for private(a,nx,ny ,pos2,dy,dx,rlen,pos,xdiff,ydiff,zdiff,vmag,t) reduction (+:pe) shared(n,fx,fy,fz) schedule(static,size) num_threads(threads)
for (a=0;a<n;a= a +size){
for (ny=0+b;ny<size+b;ny++){
for (nx=0+a;nx<size+a;nx++){

//loop over displacements
for (dy=MAX(ny-delta,0);dy<MIN(ny+delta+1,n);dy++){
for (dx=MAX(nx-delta,0);dx<MIN(nx+delta+1,n);dx++){

//code

}
}
}
}
}
}