3.5 Load Balance and Loop Scheduling

Loop scheduling is the process of distributing iterations of a parallel loop to multiple threads. In order to maximize the speedup, the work should be distributed evenly among the threads while not imposing too much overhead. The compiler offers several types of scheduling for different situations.

3.5.1 Static or Chunk Scheduling

For the best results, divide the work evenly among the different threads on the system when the work performed by different iterations of a loop is the same. This approach is known as static scheduling.

Example 3-13 Good Loop for Static Scheduling

for (i=1; i < 1000; i++) {
    sum += a[i]*b[i];       /* S1 */
}

Under static or chunk scheduling, each thread will get the same number of iterations. With four threads, each thread will get 250 iterations. Provided no interruptions occur and each thread progresses at the same rate, all the threads will complete at the same time.

3.5.2 Self-Scheduling

Static scheduling usually will not achieve good load balance when the work performed by each iteration varies. In static scheduling, each thread grabs the same chunk of iterations. Each thread, except the master thread, upon completion of its chunk waits to participate in the next parallel loop execution. The master thread continues execution of the program. In self-scheduling, each thread grabs a different small chunk of iteration and after completion of its assigned chunk, tries to acquire more chunks from the same loop.

3.5.3 Guided Self-Scheduling

In guided self-scheduling (GSS), each thread gets successively smaller number of chunks. In cases where the size of each iteration varies, GSS can help balance the load.