3.6 负载平衡和循环调度

循环调度是将并行循环的迭代分布到多个线程的进程。为获得最大加速，在线程间均匀地分布工作而不产生太大开销十分重要。编译器针对不同情况提供多种调度类型。

3.6.1 静态调度或块调度

当循环的不同迭代执行的工作相同时，将工作均匀地分摊在系统上不同的线程之间很有益。此方法称为静态调度。

示例 3-13 静态调度的良好循环

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

在静态调度或块调度中，每个线程将获取相同次数的迭代。如果有 4 个线程，则在以上示例中，每个线程将获取 250 次迭代。假设不存在中断，并且每个线程的进度相同，则所有线程将同时完成。

3.6.2 自我调度

一般说来，当每次迭代执行的工作不同时，静态调度不会达到良好的负载平衡。在静态调度中，每个线程获取同一迭代块。除主线程之外，每个线程在完成自己的块时，将等待参与下一个并行循环的执行。主线程将继续执行程序。在自我调度中，每个线程获取不同的小迭代块，并且在完成为其分配的块之后，尝试从同一循环中获取更多块。

3.6.3 引导自我调度

在引导自我调度 (guided self scheduling, GSS) 中，每个线程获取连续变少的块。如果每次迭代的大小不同，GSS 有助于平衡负载。