Boost C++ 库

……是世界上备受推崇且设计精良的 C++ 库项目之一。 Herb SutterAndrei Alexandrescu, C++ Coding Standards

并行 - Fork-Join -- 实验性 - Boost C++ 函数库
PrevUpHomeNext
[Warning] 警告

这些功能是实验性的,未来版本可能会更改。目前测试不多,因此可能会发现一些小bug :(

[Note] 注意

这些特性基于 P. Halpern、A. Robison、A. Laksberg、H. Sutter 等人于 2014 年提出的 C++1y 提案 n4088 - Task Region R3。接下来的文本改编自该提案,以展示差异。

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

[Note] 注意

到目前为止,Boost.Thread 尚未实现 n4105 - 信息技术 – 编程语言、其环境及系统软件接口 – C++ 并行扩展技术规范 中定义的并行算法。

本模块介绍了一个 C++11/c++14 库函数模板 task_region 和一个库类 task_region_handle,后者具有成员函数 runwait,它们共同使开发人员能够编写富有表现力和可移植的分叉-合并并行代码。

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

本库提供的 task_regionrunwait 函数基于 PPL 和 TBB 库的公共子集中的 task_group 概念。

考虑一个并行遍历树的例子,其中用户提供的函数 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_regiontask_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(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) 行使用。

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
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

PrevUpHomeNext