Understanding the collapse clause in openmp
The problem with your code is that the iterations of the inner loop depend on the outer loop. According to the OpenMP specification under the description of the section on binding and the collapse
clause:
If execution of any associated loop changes any of the values used to compute any of the iteration counts, then the behavior is unspecified.
You can use collapse when this is not the case for example with a square loop
#pragma omp parallel for private(j) collapse(2)
for (i = 0; i < 4; i++)
for (j = 0; j < 100; j++)
In fact this is a good example to show when to use collapse. The outer loop only has four iterations. If you have more than four threads then some will be wasted. But when you collapse the threads will distribute among 400 iterations which is likely to be much greater than the number of threads. Another reason to use collapse is if the load is not well distributed. If you only used four iterations and the fourth iteration took most of the time the other threads wait. But if you use 400 iterations the load is likely to be better distributed.
You can fuse a loop by hand for the code above like this
#pragma omp parallel for
for(int n=0; n<4*100; n++) {
int i = n/100; int j=n%100;
Here is an example showing how to fuse a triply fused loop by hand.
Finally, here is an example showing how to fuse a triangular loop which collapse
is not defined for.
Here is a solution that maps a rectangular loop to the triangular loop in the OPs question. This can be used to fuse the OPs triangular loop.
//int n = 4;
for(int k=0; k<n*(n+1)/2; k++) {
int i = k/(n+1), j = k%(n+1);
if(j>i) i = n - i -1, j = n - j;
printf("(%d,%d)\n", i,j);
}
This works for any value of n.
The map for the OPs question goes from
(0,0),
(1,0), (1,1),
(2,0), (2,1), (2,2),
(3,0), (3,1), (3,2), (3,3),
to
(0,0), (3,3), (3,2), (3,1), (3,0),
(1,0), (1,1), (2,2), (2,1), (2,0),
For odd values of n the map is not exactly a rectangle but the formula still works.
For example n = 3 gets mapped from
(0,0),
(1,0), (1,1),
(2,0), (2,1), (2,2),
to
(0,0), (2,2), (2,1), (2,0),
(1,0), (1,1),
Here is code to test this
#include <stdio.h>
int main(void) {
int n = 4;
for(int i=0; i<n; i++) {
for(int j=0; j<=i; j++) {
printf("(%d,%d)\n", i,j);
}
}
puts("");
for(int k=0; k<n*(n+1)/2; k++) {
int i = k/(n+1), j = k%(n+1);
if(j>i) i = n - i - 1, j = n - j;
printf("(%d,%d)\n", i,j);
}
}
iomartin
Updated on July 21, 2022Comments
-
iomartin almost 2 years
I came across an OpenMP code that had the collapse clause, which was new to me. I'm trying to understand what it means, but I don't think I have fully grasped it's implications; One definition that I found is:
COLLAPSE: Specifies how many loops in a nested loop should be collapsed into one large iteration space and divided according to the schedule clause. The sequential execution of the iterations in all associated loops determines the order of the iterations in the collapsed iteration space.
I thought I understood what that meant, so I tried the follwoing simple program:
int i, j; #pragma omp parallel for num_threads(2) private(j) for (i = 0; i < 4; i++) for (j = 0; j <= i; j++) printf("%d %d %d\n", i, j, omp_get_thread_num());
Which produced
0 0 0 1 0 0 1 1 0 2 0 0 2 1 0 2 2 1 3 0 1 3 1 1 3 2 1 3 3 1
I then added the
collapse(2)
clause. I expected to have the same result in the first two columns but now have an equal number of0
's and1
's in the last column. But I got0 0 0 1 0 0 2 0 1 3 0 1
So my questions are:
- What is happening in my code?
- Under what circumstances should I use
collapse
? - Can you provide an example that shows the difference between using
collapse
and not using it?
-
Z boson over 8 years@Gilles, why did you add the comment
<!-- language-all: lang-c -->
to my answer? What's the point of doing that. I am not complaining. I just don't know what it's for. -
Gilles over 8 yearsI just added the C syntax highlighting hint as described here. Indeed, on my browser, all your code snippets were displayed a grim grey. Now, on my browser at least, but I guess on many others' too, the C syntax is coloured. OK, the indexes in the output snippets are too, which might be unwanted, but it can be fixed if you want? Anyway, I didn't want to intrude, but I thought a good answer deserves good colours... Did I go too far?
-
Z boson over 8 years@Gilles, I was not aware of that. Thank you! I don't mind at all that you improved my answer.
-
N0rA over 8 yearsBut I didn't get what is the parameter mean? collapse(2) what is 2 ?!
-
Chris Swierczewski almost 7 years@N0rA The number of loops.
collapse(n)
collapses the followingn
nested loops into a single parallel loop shared by the threads.