在多线程应用程序开发中，一个重要的目标是最小化线程的空闲时间。通过在所有线程间平均分配工作负载，并且尽量减少工作共享的开销，可以减少因线程空闲而导致的计算周期浪费，从而提高性能。然而，实现完美的负载均衡并非易事，它依赖于应用程序的并行性、工作负载、线程数量、负载均衡策略以及线程实现方式。
本文是“Intel多线程应用开发指南”系列的一部分，该系列提供了开发高效多线程应用程序的指导方针，适用于Intel®平台。
计算过程中的空闲核心是一种浪费的资源。如果能够有效地在该核心上并行执行，就会增加线程应用程序的总体执行时间。这种空闲可能由多种原因导致，例如从内存或I/O中获取数据。虽然可能无法完全避免核心在某些时候处于空闲状态，但程序员可以采取一些措施来减少空闲时间，例如重叠I/O、内存预取和重新排序数据访问模式以更好地利用缓存。
在多线程执行中，空闲线程同样是浪费的资源。如果分配给线程的工作量不均等，就会产生所谓的“负载不平衡”。不平衡越大，空闲线程就越多，完成计算所需的时间就越长。将计算任务更公平地分配给可用线程，总体执行时间就会越低。
例如，考虑一组12个独立任务，其执行时间如下：{10, 6, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1}。假设有四个线程可用于计算这组任务，一个简单的任务分配方法就是按顺序将每个线程分配三个总任务。因此，线程0将被分配总共20个时间单位的工作（10+6+4），线程1需要8个时间单位（4+2+2），线程2需要5个时间单位（2+2+1），线程3只需要3个时间单位（1+1+1）来执行分配的三个任务。图1(a)展示了这种工作分配，并显示了这12个任务的总体执行时间为20个时间单位（时间从上到下运行）。
更好的工作分配方式可能是线程0：{10}，线程1：{4, 2, 1, 1}，线程2：{6, 1, 1}，线程3：{4, 2, 2, 2}，如图1(b)所示。这种调度只需要10个时间单位来完成，并且只有四个线程中的两个在每个时间单位中空闲2个时间单位。
当所有任务长度相同时，简单地将任务静态分配给可用线程——将总任务数分成（几乎）等大小的组分配给每个线程——是一个简单且公平的解决方案。然而，在一般情况下，即使所有任务长度都提前知道，找到任务分配给线程的最佳平衡也是一个难以处理的问题。当单个任务的长度不同时，更好的解决方案可能是更动态地将任务分配给分配的线程。
OpenMP*迭代工作共享构造通常默认将迭代静态调度到线程（如果不是这样，可以指定这种调度）。当迭代的工作负载变化且模式不可预测时，动态调度迭代到线程可以更好地平衡负载。通过schedule子句指定两种调度替代方案，动态和指导。在动态调度下，迭代块被分配给线程；当分配完成后，线程请求新的迭代块。schedule子句的可选chunk参数表示动态调度的迭代块的固定大小。
#pragma omp parallel for schedule(dynamic, 5)
for (int i = 0; i < n; i++) {
unknown_amount_of_work(i);
}
指导调度最初为线程分配较大的迭代块；随着未分配迭代集合的减少，给请求线程的迭代数量会减少。由于分配模式，指导调度往往比动态调度需要更少的开销。schedule子句的可选chunk参数表示在指导调度下分配的迭代块中的最小迭代次数。
#pragma omp parallel for schedule(guided, 8)
for (int i = 0; i < n; i++) {
uneven_amount_of_work(i);
}
一个特殊情况是迭代之间的工作负载单调递增（或递减）。例如，下三角矩阵每行的元素数量以规则模式增加。对于这种情况，设置一个相对较低的块大小（以创建大量块/任务）与静态调度可能在没有动态或指导调度所需的开销的情况下提供足够的负载平衡。
#pragma omp parallel for schedule(static, 4)
for (int i = 0; i < n; i++) {
process_lower_triangular_row(i);
}
当调度选择不明显时，使用runtime调度允许根据需要更改块大小和调度类型，而无需重新编译程序。
当使用Intel® Threading Building Blocks (Intel® TBB)的parallel_for算法时，调度器将迭代空间划分为小任务，这些任务被分配给线程。如果某些迭代的计算时间比其他迭代长，Intel TBB调度器能够动态地“窃取”线程的任务，以实现线程间更好的工作负载平衡。
显式线程模型（例如，Windows*线程、Pthreads*和Java*线程）没有自动将一组独立任务调度到线程的任何手段。当需要时，必须将这种能力编程到应用程序中。静态调度任务是一个简单的练习。对于动态调度，可以轻松实现两种相关方法：生产者/消费者和老板/工人。在前者中，一个线程（生产者）将任务放入共享队列结构中，而消费者线程根据需要移除任务进行处理。虽然不是绝对必要的，但在任务对消费者线程可用之前需要进行一些预处理时，通常使用生产者/消费者模型。
在老板/工人模型下，工人线程在需要更多工作时与老板线程会合，直接接收任务分配。在任务划分非常简单的情况下，例如数据数组的索引范围需要处理，可以使用全局计数器和适当的同步来代替单独的老板线程。也就是说，工人线程访问当前值并调整（可能增加）计数器，以便下一个请求额外工作的线程。
无论使用哪种任务调度模型，都必须考虑使用正确数量和类型的线程，以确保被分配执行所需计算的线程不会被闲置。例如，如果消费者线程有时处于空闲状态，可能需要减少消费者数量或增加生产者线程。适当的解决方案将取决于算法考虑以及需要分配的任务数量和长度。
任何动态任务调度方法都会因为分配任务而产生一些开销。将小型独立任务捆绑在一起作为一个可分配的工作单元可以减少这种开销；相应地，如果使用OpenMP调度子句，设置一个非默认的块大小，这将是任务中的最小迭代次数。构成任务的计算量的最佳选择将基于要执行的计算以及执行时可用的线程数量和其他资源。
Intel®软件网络并行编程社区
Clay Breshears, 《并发的艺术》，O’Reilly Media, Inc., 2009。
Barbara Chapman, Gabriele Jost, 和 Ruud van der Post, 《使用OpenMP：可移植共享内存并行编程》，The MIT Press, 2007。
Intel® Threading Building Blocks
Intel Threading Building Blocks for Open Source