Boost C++ Libraries

...世界上最受推崇和专业设计的 C++ 库项目之一。 — Herb Sutter 和 Andrei Alexandrescu, C++ Coding Standards

PrevUpHomeNext

并行 - 分叉-汇合 -- 实验性的

分叉-汇合
参考 -- 实验性的

分叉-汇合

简介
教程
示例
设计原理
[Warning] 警告

这些功能是实验性的，并且在未来版本中可能会发生变化。目前还没有进行太多测试，所以您可能会发现一些微不足道的错误 :(

[Note] 注意

这些功能基于 n4088 - Task Region R3 P. Halpern, A. Robison, A. Laksberg, H. Sutter 等人的 C++1y 提案。以下文本已根据本文档进行改编，以显示差异。

与标准提案的主要区别在于，我们能够为多个任务区域使用一个通用的执行器。

[Note] 注意

到目前为止，Boost.Thread 尚未实现 n4105 - Information technology – Programming languages, their environments and system software interfaces – Technical Specification for C++ Extensions for Parallelism 中定义的并行算法。

本模块引入了一个 C++11/c++14 库函数模板 task_region 和一个库类 task_region_handle，其成员函数 run 和 wait 共同使开发人员能够编写富有表现力和可移植的分叉-汇合并行代码。

并行性 TS N4105 的工作草案通过包含并行执行策略来增强 STL 算法。程序员使用这些作为基础来编写额外的高级算法，这些算法可以使用提供的并行算法来实现。但是，n4105 的范围不包括表达任意分叉-汇合并行性的低级机制

此库提供的 task_region、run 和 wait 函数基于 task_group 概念，该概念是 PPL 和 TBB 库的公共子集的一部分。

考虑一个树的并行遍历示例，其中用户提供的函数 compute 应用于树的每个节点，返回结果的总和

template<typename Func>
int traverse(node *n, Func&& compute)
{
  int left = 0, right = 0;
  task_region([&](task_region_handle& tr) {
    if (n->left)
      tr.run([&] { left = traverse(n->left, compute); });
    if (n->right)
      tr.run([&] { right = traverse(n->right, compute); });
  });
  return compute(n) + left + right;
}

上面的示例演示了本文档中提出的两个函数 task_region 和 task_region_handle::run 的使用。task_region 函数在程序代码中划定一个区域，该区域可能包含由 task_region_handle 类的 run 成员函数生成的任务调用。

run 函数生成一个任务，这是一个工作单元，允许相对于调用者并行执行。在 task_region 中由 run 生成的任何并行任务在 task_region 结束时都将连接回单个执行线程。

run 接受用户提供的函数对象 f 并异步启动它 - 即它可能在 f 执行完成之前返回。实现的调度程序可以选择立即运行 f 或延迟运行 f 直到计算资源可用。

task_region_handle 只能由 task_region 构造，因为它没有公共构造函数。因此，run 只能从传递给 task_region 的用户提供的函数（直接或间接）调用

void g();
void f(task_region_handle& tr)
{
  tr.run(g); // OK, invoked from within task_region in h
}
void h()
{
  task_region(f);
}

int main()
{
  task_region_handle tr; // Error: no public constructor
  tr.run(g); // No way to call run outside of a task_region
  return 0;
}
并行 Fibonacci
并行 Fibonacci - 特定执行器
并行累加
并行快速排序

这肯定是 Fibonacci 函数最糟糕的实现。无论如何，它在这里，因为它很简单并且清楚地显示了分叉-汇合结构。Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)，因此任务分解很简单。

int fib_task_region(int n)
{
  using boost::experimental::parallel::task_region;
  using boost::experimental::parallel::task_region_handle;

  if (n == 0) return 0;
  if (n == 1) return 1;

  int n1;
  int n2;

  task_region([&](task_region_handle& trh)
      {
        trh.run([&]
            {
              n1 = fib_task_region(n - 1);
            });

        n2 = fib_task_region(n - 2);
      });

  return n1 + n2;
}

int main()
{
  for (int i = 0; i<10; ++i) {
    std::cout << fib_task_region(i) << " ";
  }
  std::cout << std::endl;
}

前面的示例使用了一种实现定义的方式来生成任务。通常，用户希望掌握任务必须如何生成。task_region 有一个重载版本，它接受一个额外的 Executor 参数和一个函数，该函数将 task_region_handle_gen<Executor> 作为参数。task_region_handle_gen<Executor> run 使用此执行器来生成任务。

template <class Ex>
int fib_task_region_gen( Ex& ex, int n)
{
  using boost::experimental::parallel::task_region;
  using boost::experimental::parallel::task_region_handle_gen;

  if (n == 0) return 0;
  if (n == 1) return 1;

  int n1;
  int n2;

  task_region(ex, [&](task_region_handle_gen<Ex>& trh) // (2)
      {
        trh.run([&]
            {
              n1 = fib_task_region(n - 1);
            });

        n2 = fib_task_region(n - 2);
      });

  return n1 + n2;
}

int main()
{
  boost::basic_thread_pool tp; // (1)
  for (int i = 0; i<10; ++i) {
    std::cout << fib_task_region_gen(tp,i) << " ";
  }
  std::cout << std::endl;
  return 0;
}

特定执行器在第 (1) 行中声明，并在第 (2) 行中使用。

参考 -- 实验性的

Parallel V1
Parallel V2
Header <experimental/exception_list.hpp>
namespace boost
{
namespace experimental
{
namespace parallel
{
inline namespace v1
{

  class exception_list;

} // v1
} // parallel
} // experimental
} // boost

namespace boost
{
namespace experimental
{
namespace parallel
{
inline namespace v1
{

  class exception_list: public std::exception
  {
  public:
    typedef 'implementation defined' const_iterator;

    ~exception_list() noexcept {}

    void add(exception_ptr const& e);
    size_t size() const noexcept;
    const_iterator begin() const noexcept;
    const_iterator end() const noexcept;
    const char* what() const noexcept;

  };

} // v1
} // parallel
} // experimental
} // boost
概念
Header <experimental/task_region.hpp>
namespace boost
{
namespace experimental
{
namespace parallel
{
inline namespace v2
{

  class task_canceled_exception;

  template <class Executor>
  class task_region_handle_gen;

  using default_executor = 'implementation defined';

  class task_region_handle;

  template <typename Executor, typename F>
    void task_region_final(Executor& ex, F&& f);
  template <typename F>
    void task_region_final(F&& f);

  template <typename Executor, typename F>
    void task_region(Executor& ex, F&& f);
  template <typename F>
    void task_region(F&& f);

} // v2
} // parallel
} // experimental
} // boost

namespace boost
{
namespace experimental
{
namespace parallel
{
inline namespace v2
{

  class task_canceled_exception: public std::exception
  {
  public:
    task_canceled_exception() noexcept;
    task_canceled_exception(const task_canceled_exception&) noexcept;
    task_canceled_exception& operator=(const task_canceled_exception&) noexcept;
    virtual const char* what() const noexcept;
  };

} // v2
} // parallel
} // experimental
} // boost

namespace boost
{
namespace experimental
{
namespace parallel
{
inline namespace v2
{

  template <class Executor>
  class task_region_handle_gen
  {
  protected:
    task_region_handle_gen(Executor& ex);

    ~task_region_handle_gen();

  public:
    task_region_handle_gen(const task_region_handle_gen&) = delete;
    task_region_handle_gen& operator=(const task_region_handle_gen&) = delete;
    task_region_handle_gen* operator&() const = delete;

    template<typename F>
    void run(F&& f);

    void wait();
  };

} // v2
} // parallel
} // experimental
} // boost

namespace boost
{
namespace experimental
{
namespace parallel
{
inline namespace v2
{

  using default_executor = 'implementation defined';

} // v2
} // parallel
} // experimental
} // boost

namespace boost
{
namespace experimental
{
namespace parallel
{
inline namespace v2
{

  class task_region_handle :
    public task_region_handle_gen<default_executor>
  {
  protected:
    task_region_handle();
    task_region_handle(const task_region_handle&) = delete;
    task_region_handle& operator=(const task_region_handle&) = delete;
    task_region_handle* operator&() const = delete;

  };

} // v2
} // parallel
} // experimental
} // boost

namespace boost
{
namespace experimental
{
namespace parallel
{
inline namespace v2
{

  template <typename Executor, typename F>
    void task_region_final(Executor& ex, F&& f);
  template <typename F>
    void task_region_final(F&& f);

} // v2
} // parallel
} // experimental
} // boost

namespace boost
{
namespace experimental
{
namespace parallel
{
inline namespace v2
{

  template <typename Executor, typename F>
    void task_region(Executor& ex, F&& f);
  template <typename F>
    void task_region(F&& f);

} // v2
} // parallel
} // experimental
} // boost
版权所有 © 2007 -11 Anthony Williams
版权所有 © 2011 -17 Vicente J. Botet Escriba

根据 Boost 软件许可，版本 1.0 分发。（请参阅随附文件 LICENSE_1_0.txt 或在 https://boost.ac.cn/LICENSE_1_0.txt 复制）

PrevUpHomeNext