schedule(guided): should chunks decrease monotonously?

General OpenMP discussion

schedule(guided): should chunks decrease monotonously?

Postby anv » Mon Dec 05, 2011 9:51 am

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?

Postby ftinetti » Mon Dec 05, 2011 11:47 am

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: 558
Joined: Wed Feb 10, 2010 2:44 pm

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

Postby anv » Tue Dec 06, 2011 1:01 am

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?

Postby ftinetti » Tue Dec 06, 2011 3:57 am

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: 558
Joined: Wed Feb 10, 2010 2:44 pm


Return to Using OpenMP

Who is online

Users browsing this forum: Google [Bot] and 7 guests

cron