Channels ▼
RSS

Parallel

OpenMP: A Portable Solution for Threading


Loop Scheduling and Partitioning

To have good load balancing and thereby achieve optimal performance in a multi-threaded application, you must have effective loop scheduling and partitioning. The ultimate goal is to ensure that the execution cores are busy most, if not all, of the time, with minimum overhead of scheduling, context switching and synchronization. With a poorly balanced workload, some threads may finish significantly before others, leaving processor resources idle and wasting performance opportunities. In order to provide an easy way for you to adjust the workload among cores, OpenMP offers four scheduling schemes that are appropriate for many situations: static, dynamic, runtime, and guided. The Intel C++ and Fortran compilers support all four of these scheduling schemes.

A poorly balanced workload is often caused by variations in compute time among loop iterations. It is usually not too hard to determine the variability of loop iteration compute time by examining the source code. In most cases, you will see that loop iterations consume a uniform amount of time. When that's not true, it may be possible to find a set of iterations that do consume similar amounts of time. For example, sometimes the set of all even iterations consumes about as much time as the set of all odd iterations, or the set of the first half of the loop consumes about as much time as the second half. On the other hand, it may be impossible to find sets of loop iterations that have a uniform execution time. In any case, you can provide loop scheduling information via the schedule(kind [, chunksize]) clause, so that the compiler and runtime library can better partition and distribute the iterations of the loop across the threads, and therefore the cores, for optimal load balancing.

By default, an OpenMP parallel for or worksharing for loop uses static-even scheduling. This means the iterations of a loop are distributed among the threads in a roughly equal number of iterations. If m iterations and N threads are in the thread team, each thread gets m/N iterations, and the compiler and runtime library correctly handles the case when m is not evenly divisible by N.

With the static-even scheduling scheme, you could minimize the chances of memory conflicts that can arise when more than one processor is trying to access the same piece of memory. This approach is workable because loops generally touch memory sequentially, so splitting up the loop into large chunks results in little chance of overlapping memory and a reasonable chance of good processor cache efficiency. Consider the following simple loop when executed using static-even scheduling and two threads.


#pragma omp parallel for
for ( k = 0; k < 1000; k++ ) do_work(k);

OpenMP will execute loop iterations 0 to 499 on one thread and 500 to 999 on the other thread. While this partition of work might be a good choice for memory issues, it could be bad for load balancing. Unfortunately, the converse is also true: what might be good for load balancing could be bad for memory performance. Therefore, performance engineers must strike a balance between optimal memory usage and optimal load balancing by measuring performance to see what method produces the best results.

Loop-scheduling and partitioning information is conveyed to the compiler and runtime library on the OpenMP for construct with the schedule clause.


#pragma omp for schedule(kind [, chunk-size])

The four schedule schemes specified in the OpenMP standard are summarized in Table 2. The optional parameter chunk-size, when specified, must be a loop-invariant positive integer constant or integer expression.

Be careful when you adjust the chunk size, because performance can be adversely affected. As the chunk size shrinks, the number of times a thread needs to retrieve work from the work queue increases. As a result, the overhead of going to the work queue increases, thereby reducing performance and possibly offsetting the benefits of load balancing.

Table 2: The Four Schedule Schemes in OpenMP.

For dynamic scheduling, the chunks are handled with the first-come, first-serve scheme, and the default chunk size is 1. Each time, the number of iterations grabbed is equal to the chunk size specified in the schedule clause for each thread, except the last chunk. After a thread has finished executing the iterations given to it, it requests another set of chunk-size iterations. This continues until all of the iterations are completed. The last set of iterations may be less than the chunk size. For example, if the chunk size is specified as 16 with the schedule(dynamic,16) clause and the total number of iterations is 100, the partition would be 16,16,16,16,16,16,4 with a total of seven chunks.

With dynamic and guided scheduling mechanisms, you can tune your application to deal with those situations where each iteration has variable amounts of work or where some cores (or processors) are faster than others. Typically, guided scheduling performs better than dynamic scheduling due to less overhead associated with scheduling.

The runtime scheduling scheme is actually not a scheduling scheme per se. When runtime is specified in the schedule clause, the OpenMP runtime uses the scheduling scheme specified in the OMP_SCHEDULE environment variable for this particular for loop. The format for the OMP_SCHEDULE environment variable is schedule-type[,chunk-size]. For example:


export OMP_SCHEDULE=dynamic,16

Using runtime scheduling gives the end-user some flexibility in selecting the type of scheduling dynamically among three previously mentioned scheduling mechanisms through the OMP_SCHEDULE environment variable, which is set to static by default.

Furthermore, understanding the loop scheduling and partitioning schemes will significantly help you to choose the right scheduling scheme, help you to avoid false-sharing for your applications at runtime, and lead to good load balancing. Considering the following example:


float x[1000], y[1000];
#pragma omp parallel for schedule(dynamic, 8)
        for (k=0; k<1000; k++) {
            x[k] = cos(k)* x[k] + sin(k) * y[k]
        }

Assume you have a dual-core processor system and the cache line size is 64 bytes. For the sample code shown above, two chunks (or array sections) can be in the same cache line because the chunk size is set to 8 in the schedule clause. So each chunk of array x takes 32 bytes per cache line, which leads to two chunks placed in the same cache line. Because two chunks can be read and written by two threads at the same time, this will result in many cache line invalidations, although two threads do not read/write the same chunk. This is called false-sharing, as it is not necessary to actually share the same cache line between two threads. A simple tuning method is to use schedule(dynamic,16), so one chunk takes the entire cache line to eliminate the false-sharing. Eliminating false sharing through the use of a chunk size setting that is aware of cache line size will significantly improve your application performance.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video