windows C++-并行编程-并行算法(三)-分区工作

并行模式库 (PPL) 提供了对数据集合并行地执行工作的算法。这些算法类似于 C++ 标准库提供的算法。并行算法由并发运行时中的现有功能组成。

若要对数据源操作进行并行化，一个必要步骤是将源分区为可由多个线程同时访问的多个部分。 分区程序将指定并行算法应如何在线程之间对范围进行分区。 如本文档前面所述，PPL 使用的是默认分区机制，该默认分区机制创建初始工作负荷并在工作负荷不平衡时使用工作窃取算法和范围窃取来平衡这些分区。 例如，当某个循环迭代完成一个迭代范围时，运行时会将其他线程的工作重新分配给该线程。 但是，在某些方案中，你可能希望指定另一个更适用于你的问题的分区机制。

parallel_for、parallel_for_each 和 parallel_transform 算法提供采用一个附加参数 _Partitioner 的重载版本。 此参数定义了用于划分工作的分区程序类型。 以下是 PPL 定义的分区程序种类：

concurrency::affinity_partitioner
将工作划分为一个固定数量的范围(通常是可用于在循环中工作的辅助线程的数量)。 此分区程序类型与 static_partitioner 类似，但通过将范围映射到辅助线程的方式改善了缓存的关联。 当在相同数据集中多次执行一个循环(例如一个循环内的循环)且数据适合缓存时，此分区程序类型可提高性能。 此分区程序不完全参与取消。 它也不使用协作停滞语义，因此不能与具有前向依赖关系的并行循环一起使用。

concurrency::auto_partitioner
将工作划分为一个初始数量的范围(通常是可用于在循环中工作的辅助线程的数量)。 当您不调用采用 _Partitioner 参数的重载的并行算法时，运行时默认使用此类型。 每个范围可以划分为子范围，从而实现负载平衡。 当一个工作范围完成时，运行时会将其他线程工作的子范围重新分配给该线程。 如果您的工作负荷不在另外一个类别下或者您需要完全支持取消或协作停滞，请使用该分区程序。

concurrency::simple_partitioner
将工作划分到范围中，使每个范围至少拥有给定区块大小所指定的迭代的数目。 此分区程序类型加入了负载平衡；然而，运行时未将范围划分为子范围。 对于每个辅助，运行时将在 _Chunk_size 迭代完成后检查取消情况并执行负载平衡。

concurrency::static_partitioner
将工作划分为一个固定数量的范围(通常是可用于在循环中工作的辅助线程的数量)。 此分区程序类型可以提高性能，因为它不使用工作窃取，开销较小。 当一个并行循环的每次迭代执行固定和统一数量的工作而且您不需要支持取消或前向协作停滞时，请使用此分区程序类型。

parallel_for_each 和 parallel_transform 算法仅支持为静态、简单和关联分区程序使用随机访问迭代器(如 std::vector)的容器。 采用双向和向前迭代器的容器的使用会导致编译时错误。 默认分区程序 auto_partitioner 支持所有这三种迭代器类型。

通常，除 affinity_partitioner 外，这些分区程序的使用方式相同。 大多数分区程序类型不会维持状态，而且不会由运行时进行修改。 因此，如下例所示，您可以在调用站点创建这些分区程序对象。

// static-partitioner.cpp
// compile with: /EHsc
#include <ppl.h>using namespace concurrency;void DoWork(int n)
{// TODO: Perform a fixed amount of work...
}int wmain()
{// Use a static partitioner to perform a fixed amount of parallel work.parallel_for(0, 100000, [](int n) {DoWork(n);}, static_partitioner());
}

但是，必须将 affinity_partitioner 对象作为非 const 左值引用传递，以便算法可以存储状态，以供未来循环重用。 下面的示例演示对数据集多次并行执行相同操作的基本应用程序。 因为数组有可能适合缓存，使用 affinity_partitioner 可以提高性能。

// affinity-partitioner.cpp
// compile with: /EHsc
#include <ppl.h>
#include <array>using namespace concurrency;
using namespace std;int wmain()
{// Create an array and fill it with zeroes.array<unsigned char, 8 * 1024> data;data.fill(0);// Use an affinity partitioner to perform parallel work on data// that is likely to remain in cache.// We use the same affinitiy partitioner throughout so that the // runtime can schedule work to occur at the same location for each // iteration of the outer loop.affinity_partitioner ap;for (int i = 0; i < 100000; i++){parallel_for_each(begin(data), end(data), [](unsigned char& c){c++;}, ap);}
}

在修改依赖于协作停滞语义的现有代码以使用 static_partitioner 或 affinity_partitioner 时应谨慎。 这些分区程序类型不使用负载平衡或范围窃取，因此可能会更改应用程序的行为。

确定在任何给定方案中是否使用分区程序的最佳方式是：体验并度量操作在有代表性的负载和计算机配置下要花多长时间完成。 例如，如果是只有几个内核的多核计算机，静态分区可以让速度显著提升；但如果是内核相对较多的计算机，静态分区可能会导致速度降低。