schedule(guided): should chunks decrease monotonously?

General OpenMP discussion

schedule(guided): should chunks decrease monotonously?

The OpenMP specification requires the size of each chunk (1) be proportional to the number of unassigned iterations and (2) decreasing to 1.

There are algorithms of analytical calculation of the chunk size using floating arithmetic that produce non-monotonic decrease of chunk size. For example, for N iterations the chunk number i could be calculated as
ch = N * pow(p,i) - N * pow(p,i+1),
where p<1.0 is some parameter of the algorithm (of cause the ch should not be less than given chunk_size except for the last chunk).

Is this conforming method? Or should chunks have strictly monotonously non-increasing sizes?
E.g. is the sequence of chunks acceptable for schedule(guided,3):
7, 8, 6, 6, 6, 5, 4, 5, 4, 3, 3, 3, 3,...?

There are two pairs "7, 8" and "4, 5" those break the "decreasing" rule, though this sequence obtained using algorithm mentioned above which in theory provides "proportional" and "decreasing" floating numbers, but loses these attributes after conversion to integer type.
anv

Posts: 31
Joined: Wed Dec 12, 2007 9:36 am

Re: schedule(guided): should chunks decrease monotonously?

Hi,

The OpenMP specification requires the size of each chunk (1) be proportional to the number of unassigned iterations and (2) decreasing to 1.

What section of the spec are you referring to?
ftinetti

Posts: 603
Joined: Wed Feb 10, 2010 2:44 pm

Re: schedule(guided): should chunks decrease monotonously?

I am talking about ch 2, pg 44, table 2-1:

For a chunk_size of 1, the size of each chunk is proportional to the
number of unassigned iterations divided by the number of threads in the team,
decreasing to 1.

Thanks,
Andrey
anv

Posts: 31
Joined: Wed Dec 12, 2007 9:36 am

Re: schedule(guided): should chunks decrease monotonously?

I see, you are talking about iterations assignment for the dynamic scheduling in Spec 3.1 (and previous specs too), which should be implemented by compilers (I was confused, since I usually think compilers implement the spec correctly...). I'm not an expert and I'm not part of the ARB, but I think (copied from spec 3.1, p. 44)
For a chunk_size of 1, the size of each chunk is proportional to the
number of unassigned iterations divided by the number of threads in the team,
decreasing to 1.

directly gives the equation/way of computing the chunk size for each assignment to thread, so anything else would be a non-compliant implementation. But maybe you should ask in the "OpenMP 3.1 API Specifications", which is at viewforum.php?f=10

HTH.
ftinetti

Posts: 603
Joined: Wed Feb 10, 2010 2:44 pm