负载均衡和并行性能

摘要

在线程之间对应用程序工作负载进行负载均衡对于性能至关重要。负载均衡的关键目标是最大限度地减少线程的空闲时间。以最少的工作共享开销将工作负载平均分配给所有线程，可以减少空闲线程在计算上浪费的周期，从而提高性能。然而，实现完美的负载均衡并非易事，它取决于应用程序内的并行性、工作负载、线程数、负载均衡策略和线程实现。

本文是大型系列“Intel 多线程应用程序开发指南”的一部分，该系列为 Intel® 平台上的高效多线程应用程序开发提供了指导方针。

背景

计算期间空闲的核心是资源的浪费，当有效并行执行可以在该核心上运行时，它会增加多线程应用程序的整体执行时间。这种空闲可能由多种原因引起，例如从内存或 I/O 获取数据。虽然完全避免核心有时空闲可能不可能，但程序员可以采取一些措施来减少空闲时间，例如重叠 I/O、内存预取以及重新排序数据访问模式以更好地利用缓存。

同样，多线程执行中的空闲线程也是资源的浪费。分配给线程的工作量不均会导致一种称为“负载不平衡”的情况。不平衡程度越大，空闲的线程就越多，完成计算所需的时间也越长。计算任务在可用线程之间的分配越公平，整体执行时间就越短。

例如，考虑一组十二个具有以下执行时间的独立任务：{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) 说明了这种工作分配，并显示了这十二个任务的总体执行时间将为 20 个时间单位（时间从上到下运行）。

更好的工作分配应该是线程 0：{10}，线程 1：{4, 2, 1, 1}，线程 2：{6, 1, 1}，线程 3：{4, 2, 2, 2}，如图 1(b) 所示。此计划仅需 10 个时间单位即可完成，并且只有四个线程中的两个线程各自空闲 2 个时间单位。

通知

当所有任务长度相同时，一种简单的方法是将任务静态地分配给可用线程——将总任务数分成（近似）相等大小的组分配给每个线程——这是一种简单且公平的解决方案。然而，在一般情况下，即使已知所有任务的长度，找到将任务分配给线程的最优、平衡的分配也是一个棘手的难题。当单个任务的长度不同时，更好的解决方案可能是将任务动态地分配给分配的线程。

OpenMP\* 迭代工作共享构造通常默认将迭代静态地调度到线程（如果不是，可以指定此调度）。当迭代之间的工作负载不同且模式不可预测时，动态地将迭代调度到线程可以更好地平衡负载。通过 `schedule` 子句指定了两种调度替代方案：`dynamic` 和 `guided`。在动态调度下，将迭代块分配给线程；当分配完成后，线程请求新的迭代块。`schedule` 子句的可选 `chunk` 参数表示动态调度中迭代块的固定大小。

#pragma omp parallel for schedule(dynamic, 5)
  for (i = 0; i < n; i++)
  {
    unknown_amount_of_work(i);
  }

`guided` 调度最初将大的迭代块分配给线程；随着未分配迭代集减少，分配给请求线程的迭代数量会减小。由于分配模式，`guided` 调度倾向于比 `dynamic` 调度需要更少的开销。`schedule` 子句的可选 `chunk` 参数表示在 `guided` 调度下分配的块中迭代的最小数量。

#pragma omp parallel for schedule(guided, 8)
  for (i = 0; i < n; i++)
  {
    uneven_amount_of_work(i);
  }

一种特殊情况是当迭代之间的工作负载单调递增（或递减）时。例如，下三角形矩阵中每行的元素数量以规律的模式增加。对于这种情况，设置相对较小的块大小（以创建大量块/任务）并使用静态调度，可以在不产生动态或 `guided` 调度所需开销的情况下提供足够的负载均衡。

#pragma omp parallel for schedule(static, 4)
  for (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：可移植共享内存并行编程》，麻省理工学院出版社，2007。

Intel® Threading Building Blocks

Intel Threading Building Blocks 开源版

James Reinders，《Intel Threading Building Blocks：为多核处理器并行性配备 C++》，O’Reilly Media, Inc. 塞巴斯托波尔，加利福尼亚州，2007。

M. Ben-Ari，《并发和分布式编程原理》，第二版，Addison-Wesley，2006。