粒度和并行性能

摘要

获得良好并行性能的关键之一是为应用程序选择正确的粒度。粒度是并行任务中实际工作的量。如果粒度太细，性能可能会因通信开销而受损。如果粒度太粗，性能可能会因负载不平衡而受损。目标是确定并行任务的正确粒度（通常越大越好），同时避免负载不平衡和通信开销，以实现最佳性能。

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

背景

多线程应用程序中单个并行任务的工作量（粒度）极大地影响其并行性能。在为多线程分解应用程序时，一种方法是逻辑上将问题“分区”为尽可能多的并行任务。在并行任务中，接下来根据共享数据和执行顺序确定必要的“通信”。由于划分任务、将任务分配给线程以及在任务之间通信（共享）数据不是免费操作，因此通常需要“聚合”或组合分区，以克服这些开销并实现最有效的实现。聚合步骤是确定并行任务最佳粒度的过程。

粒度通常与线程之间工作负载的平衡程度有关。虽然平衡大量较小任务的工作负载更容易，但这可能会以通信、同步等形式导致过多的并行开销。因此，可以通过将较小任务组合成一个任务来增加每个任务内的粒度（工作量）来减少并行开销。Intel® Parallel Amplifier 等工具可以帮助确定应用程序的正确粒度。

以下示例演示了如何通过减少通信开销并为线程找到正确的粒度来提高并行程序的性能。本文中使用的示例是一个素数计数算法，该算法使用简单的暴力测试，将每个潜在素数除以所有可能的因子，直到找到除数或证明该数是素数。由于正奇数可以通过 (4k+1) 或 (4k+3) 计算，k ≥ 0，因此代码还将统计属于每种形式的素数。这些示例将统计 3 到 100 万之间的所有素数。

代码的第一个变体显示了使用 OpenMP* 的并行版本。

#pragma omp parallel 
{ int j, limit, prime;
#pragma for schedule(dynamic, 1) 
  for(i = 3; i <= 1000000; i += 2) {
    limit = (int) sqrt((float)i) + 1;
    prime = 1; // assume number is prime
    j = 3;
    while (prime && (j <= limit)) {
      if (i%j == 0) prime = 0;
      j += 2;
    }
  
    if (prime) {
      #pragma omp critical
      {
      numPrimes++;
      if (i%4 == 1) numP41++;  // 4k+1 primes
      if (i%4 == 3) numP43++;  // 4k-1 primes
      }
    }
  }
}

此代码既有高通信开销（以同步形式），又有对线程来说过小的单个任务大小。在循环内部，有一个临界区用于提供递增计数变量的安全机制。临界区会增加并行循环的同步和锁开销，如图 1 中 Intel Parallel Amplifier 显示所示。

基于大型数据集中的值递增计数变量是一种常见的表达式，被称为规约。通过消除临界区并添加 OpenMP `reduction` 子句，可以消除锁和同步开销。

#pragma omp parallel 
{
  int j, limit, prime;
 
  #pragma for schedule(dynamic, 1) \
    reduction(+:numPrimes,numP41,numP43) 
  for(i = 3; i <= 1000000; i += 2) {
    limit = (int) sqrt((float)i) + 1;
    prime = 1;  // assume number is prime
    j = 3;
    while (prime && (j <= limit))
    {
      if (i%j == 0) prime = 0;
      j += 2;
    }
 
    if (prime)
    {
      numPrimes++;
      if (i%4 == 1) numP41++;  // 4k+1 primes
      if (i%4 == 3) numP43++;  // 4k-1 primes
    }
  }
}

根据循环执行的迭代次数，删除循环体内的临界区可以将执行速度提高数个数量级。然而，上述代码可能仍然存在一些并行开销。这是因为每个任务的工作量太小。`schedule (dynamic, 1)` 子句指定调度程序一次动态地向每个线程分发一个迭代（或块）。每个工作线程处理一个迭代，然后返回调度程序，并同步以获取另一个迭代。通过增加块大小，我们增加了分配给线程的每个任务的工作量，从而减少了每个线程必须与调度程序同步的次数。

虽然这种方法可以提高性能，但必须记住（如上所述）粒度增加过多会导致负载不平衡。例如，考虑将块大小增加到 10000，如下面的代码所示。

#pragma omp parallel
{
  int j, limit, prime;
  #pragma for schedule(dynamic, 100000) \
    reduction(+:numPrimes, numP41, numP43)
  for(i = 3; i <= 1000000; i += 2)
  {
    limit = (int) sqrt((float)i) + 1;
    prime = 1; // assume number is prime
    j = 3;
    while (prime && (j <= limit))
    {
      if (i%j == 0) prime = 0;
      j += 2;
    }
 
    if (prime)
    {
      numPrimes++;
      if (i%4 == 1) numP41++;  // 4k+1 primes
      if (i%4 == 3) numP43++;  // 4k-1 primes
    }
  }
}

在 Parallel Amplifier 中对此代码执行的分析显示，所使用的四个线程的计算量不平衡，如图 2 所示。此计算示例的关键点是，每个块的工作量不同，并且分配为任务的块太少（四个线程有十个块），这导致了负载不平衡。随着潜在素数的值增加（来自 `for` 循环），需要更多的迭代来测试素数的所有可能因子（在 `while` 循环中）。因此，每个块的总工作量将比之前的块需要更多的 `while` 循环迭代。

应使用更合适的工作量 (100) 来为程序选择正确的粒度。此外，由于连续任务之间工作量的差异将小于之前的块大小，因此可以通过使用静态调度而不是动态调度来进一步消除并行开销。下面的代码显示了调度子句中的更改，这将几乎消除此代码段的开销并产生最快的整体并行性能。

#pragma omp parallel
{
  int j, limit, prime;
  #pragma for schedule(static, 100) \
    reduction(+:numPrimes, numP41, numP43)
  for(i = 3; i <= 1000000; i += 2)
  {
    limit = (int) sqrt((float)i) + 1;
    prime = 1;  // assume number is prime
    j = 3;
    while (prime && (j <= limit))
    {
      if (i%j == 0) prime = 0;
      j += 2;
    }
  
    if (prime)
    {
      numPrimes++;
      if (i%4 == 1) numP41++;  // 4k+1 primes
      if (i%4 == 3) numP43++;  // 4k-1 primes
    }
  }
}

通知

多线程代码的并行性能取决于粒度：工作如何在线程之间分配以及这些线程之间如何进行通信。以下是一些通过调整粒度来提高性能的指导原则：

• 了解您的应用程序
  • 了解应用程序中将并行执行的各个部分正在完成多少工作。
  • 了解应用程序的通信要求。同步是一种常见的通信形式，但也要考虑跨内存层次结构（缓存、主内存等）的消息传递和数据共享的开销。
• 了解您的平台和线程模型
  • 了解在目标平台上使用线程模型启动并行执行和同步的成本。
  • 确保应用程序每个并行任务的工作量远大于线程开销。
  • 使用尽可能少的同步，并使用成本最低的同步。
  • 在 Intel® Threading Building Blocks 并行算法中使用分区器对象，以允许任务调度程序为每个任务选择良好的工作粒度并在执行线程上实现负载平衡。
• 了解您的工具
  • 在 Intel Parallel Amplifier 的“锁和等待”分析中，寻找显著的锁、同步和并行开销，这表明通信过多。
  • 在 Intel Parallel Amplifier 的“并发性”分析中，寻找负载不平衡，这表明粒度太大或任务需要更好地分配给线程。

使用指南

虽然上述示例经常提到 OpenMP，但所描述的所有建议和原则也适用于其他线程模型，例如 Windows 线程和 POSIX* 线程。所有线程模型都与其各种功能相关联的开销，例如启动并行执行、锁、临界区、消息传递等。这里关于减少通信和增加每个线程的工作量而不增加负载不平衡的建议适用于所有线程模型。然而，不同模型的不同成本可能会决定不同的粒度选择。

额外资源

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 开源版

James Reinders, *Intel Threading Building Blocks: Outfitting C++ for Multi-core Processor Parallelism*. O’Reilly Media, Inc. Sebastopol, CA, 2007.

Ding-Kai Chen 等人，“同步和粒度对并行系统的影响”，《第 17 届年度国际计算机体系结构研讨会会议记录，1990 年》，美国华盛顿州西雅图。