OpenMP Scheduling (default is default for a reason)

Posted by Andrew Denner on October 30, 2020 · 2 mins read

scheduling is easy, right?

This post was inspired by an interesting post from a friend and colleague about dynamic scheduling in OpenMP as well as a question that I was asked in an interview around a coding problem. (My solution as well as the interview question is at my gitlab page)

In Kyle’s problem he is implementing a naïve prime number generator where each loop takes an increasing amount of time. As he discovers, the dynamic scheduler makes the most sense in his case as each thread picks up a chunk of work (by default the chunks are sized 1). This sounds great but as with all things there is no such thing as a free lunch. Dynamic scheduling has a performance cost in added overhead.

In my case, I am leveraging the GNUMP library to run a test that will check to see if a number is very likely to be prime. Since the test takes a constant amount of time the default scheduler for Open MP ends up being the best as it does not have the overhead of the added book keeping that dynamic has. By default the static scheduler chunks the work into loop_count/number_of_threads chunks and then divides the work evenly between all of the threads.

Of note and worth further investigation is the auto scheduler where the developer yields control to the compiler to make the best scheduling decision. However this apparently requires using a better implementation than g++ and the default libgomp as it is hardcoded to take the static scheduler.

Additional References:
https://software.intel.com/content/www/us/en/develop/articles/openmp-loop-scheduling.html
http://www.inf.ufsc.br/~bosco.sobral/ensino/ine5645/OpenMP_Dynamic_Scheduling.pdf