并行算法

项目
08/12/2011

并行模式库 (PPL) 提供了可用于同时对多个数据集合执行操作的算法。这些算法与标准模板库 (STL) 提供的算法类似。

并行算法由并发运行时中的现有功能组成。例如，Concurrency::parallel_for 算法使用 Concurrency::structured_task_group 对象执行并行循环迭代。在给定可用数量的计算资源的情况下，parallel_for 算法会按照最佳方式对工作进行分区。

各节内容

本主题详细描述下列并行算法：

parallel_for 算法
parallel_for_each 算法
parallel_invoke 算法

parallel_for 算法

Concurrency::parallel_for 算法重复地以并行方式执行相同的任务。其中每个任务都由迭代值进行参数化。当一个循环体不在该循环的各个迭代之间共享资源时，此算法很有用。

parallel_for 算法会按照最佳方式对任务进行分区以便并行执行。当工作负载不平衡时，此算法还会使用工作窃取算法来平衡这些分区。当以协作方式阻止某个循环迭代时，运行时会将指派给当前线程的迭代范围重新发布给其他线程或处理器。类似地，当某个线程完成迭代范围时，运行时会将其他线程的工作重新发布给该线程。 parallel_for 算法还支持嵌套并行。当一个并行循环包含另一个并行循环时，运行时会以一种适合并行执行的高效方式在循环主体之间协调处理资源。

parallel_for 算法具有两个重载版本。第一个版本采用起始值、结束值和工作函数（lambda 表达式、函数对象或函数指针）。第二个版本采用起始值、结束值、步长值和工作函数。此函数的第一个版本使用 1 作为步长值。

可以将很多 for 循环转换为使用 parallel_for。但是，parallel_for 算法与 for 语句在以下方面存在差异：

parallel_for 算法 parallel_for 不按照预定的顺序执行任务。
parallel_for 算法不支持任意终止条件。当迭代变量的当前值比 _Last 小 1 时，parallel_for 算法将停止。
_Index_type 类型参数必须是整型。此整型可以带符号或者不带符号。
循环迭代必须是向前的。如果 _Step 参数小于 1，则 parallel_for 算法会引发 std::invalid_argument 类型的异常。
parallel_for 算法的异常处理机制与 for 循环的不同。如果并行循环主体中同时发生多个异常，则运行时仅传播其中一个异常给名为 parallel_for 的线程。另外，当某个循环迭代引发异常时，运行时不会立即停止整个循环。而是将循环置于取消状态，并且运行时会放弃任何尚未开始的任务。有关异常处理和并行算法的更多信息，请参见并发运行时中的异常处理。

虽然 parallel_for 算法不支持任意终止条件，但您可以通过取消操作来停止所有任务。有关取消操作的更多信息，请参见 PPL 中的取消操作。

提示

尽管因负载平衡和功能支持（例如取消）而产生了一些计划成本，但这并不能抵消并行执行循环主体所带来的好处相比，特别是在循环主体相对比较小的情况下。

示例

下面的示例显示了 parallel_for 算法的基本结构。本示例在控制台上并行打印 [1, 5] 范围内的每个值。

// parallel-for-structure.cpp
// compile with: /EHsc
#include <ppl.h>
#include <array>
#include <sstream>
#include <iostream>

using namespace Concurrency;
using namespace std;

int wmain()
{
   // Print each value from 1 to 5 in parallel.
   parallel_for(1, 6, [](int value) {
      wstringstream ss;
      ss << value << L' ';
      wcout << ss.str();
   });
}

此示例产生下面的示例输出：

1 2 4 3 5

由于 parallel_for 算法并行作用于每个项目，因此值打印在控制台的顺序将会有所变化。

有关使用 parallel_for 算法的完整示例，请参见如何：编写 parallel_for 循环。

[转到页首]

parallel_for_each 算法

Concurrency::parallel_for_each 算法以并行方式对迭代容器执行任务（如 STL 提供的任务）。此算法使用的分区逻辑与 parallel_for 算法使用的分区逻辑相同。

parallel_for_each 算法与 STL std::for_each 算法类似，只是 parallel_for_each 算法将并发执行任务。与其他并行算法一样，parallel_for_each 不按特定的顺序执行任务。

虽然 parallel_for_each 算法既可用于向前迭代器，又可用于随机访问迭代器，但此算法更适用于随机访问迭代器。

示例

下面的示例显示了 parallel_for_each 算法的基本结构。本示例在控制台上并行打印 std::array 对象内的每个值。

// parallel-for-each-structure.cpp
// compile with: /EHsc
#include <ppl.h>
#include <array>
#include <sstream>
#include <iostream>

using namespace Concurrency;
using namespace std;

int wmain()
{
   // Create an array of integer values.
   array<int, 5> values = { 1, 2, 3, 4, 5 };

   // Print each value in the array in parallel.
   parallel_for_each(values.begin(), values.end(), [](int value) {
      wstringstream ss;
      ss << value << L' ';
      wcout << ss.str();
   });
}

此示例产生下面的示例输出：

4 5 1 2 3

由于 parallel_for_each 算法并行作用于每个项目，因此值打印在控制台的顺序将会有所变化。

有关使用 parallel_for_each 算法的完整示例，请参见如何：编写 parallel_for_each 循环。

[转到页首]

parallel_invoke 算法

Concurrency::parallel_invoke 算法以并行方式执行一组任务。在完成所有任务之前，此算法不会返回。当您需要同时执行多个独立的任务时，此算法很有用。

parallel_invoke 算法采用一系列工作函数（lambda 函数、函数对象或函数指针）作为其参数。可对 parallel_invoke 算法进行重载以采用 2 到 10 个参数。传递给 parallel_invoke 的每个函数都必须采用零个参数。

与其他并行算法一样，parallel_invoke 不按特定的顺序执行任务。主题任务并行（并发运行时）说明 parallel_invoke 算法如何关联至任务和任务组。

示例

下面的示例显示了 parallel_invoke 算法的基本结构。本示例对三个局部变量并发调用 twice 函数并将结果打印到控制台。

// parallel-invoke-structure.cpp
// compile with: /EHsc
#include <ppl.h>
#include <string>
#include <iostream>

using namespace Concurrency;
using namespace std;

// Returns the result of adding a value to itself.
template <typename T>
T twice(const T& t) {
   return t + t;
}

int wmain()
{
   // Define several values.
   int n = 54;
   double d = 5.6;
   wstring s = L"Hello";

   // Call the twice function on each value concurrently.
   parallel_invoke(
      [&n] { n = twice(n); },
      [&d] { d = twice(d); },
      [&s] { s = twice(s); }
   );

   // Print the values to the console.
   wcout << n << L' ' << d << L' ' << s << endl;
}

该示例产生下面的输出：