如何高效地并行化分治算法？

Question

最近几天，我一直在复习排序算法，并遇到了一个找不到最佳解决方案的情况。我编写了一个基本的快速排序实现，并希望通过并行执行来提高其性能。

我所拥有的是：

template <typename IteratorType>
void quicksort(IteratorType begin, IteratorType end)
{
  if (distance(begin, end) > 1)
  {
    const IteratorType pivot = partition(begin, end);

    if (distance(begin, end) > 10000)
    {
      thread t1([&begin, &pivot](){ quicksort(begin, pivot); });
      thread t2([&pivot, &end](){ quicksort(pivot + 1, end); });

      t1.join();
      t2.join();
    }
  }
}

虽然这比朴素的“无线程”实现效果更好，但它有严重的限制，即：

• 如果要排序的数组太大或递归层数过深，系统可能会耗尽线程，导致执行失败。
• 在每个递归调用中创建线程的成本可能是可以避免的，特别是考虑到线程不是无限的资源。

我想使用线程池来避免晚期线程创建，但我面临另一个问题：

• 我创建的大部分线程在开始时都完成了它们的工作，然后在等待子调用完成时什么也不做。这导致许多线程只是等待子调用完成，这似乎相当次优。

是否有一种技术/实体可以用来避免浪费线程(允许它们的重新使用)?

我可以使用boost或任何C++11设施。

- ereOn

---

你正在寻找一个“工作窃取”库。但我怀疑C++11或Boost是否有这样的库。 - Mysticial

我相信有一个原地、迭代实现快速排序的方法。或许这将成为处理线程等待并消除递归限制的简单方式。 - rliu

请查看此链接中的并行快速排序 http://stackoverflow.com/questions/16248321/parallel-quick-sort-outdone-by-single-threaded-quicksort。这是A.Williams（boost线程实现者）在《C++并发编程实战》一书中提供的并行快速排序实现。而这本书则是该领域的*权威之作*。 - SChepurin

你可能想要看一下 Intel Cilk-Plus，它使用了工作窃取技术。有一个特殊的gcc 4.8分支。 - TemplateRex

一个好的任务池不需要使用 join -- 相反，你创建任务并获取 std::future。要完成的任务将被分派到线程中，生成答案并退出。对于你的代码，你需要划分，创建一个任务来排序前半部分和后半部分，然后安排 "我完成了" 消息 当这两个任务都完成时（可能通过在两个 future 上使用 then 机制或从任务池获得帮助）。然后你的代码将退出，返回构造的 future。 - Yakk - Adam Nevraumont

Answer 1

如果要排序的数组太大或递归深度过深，系统可能会耗尽线程并且执行失败。

所以在达到最大深度后改为顺序执行...

template <typename IteratorType>
void quicksort(IteratorType begin, IteratorType end, int depth = 0)
{
  if (distance(begin, end) > 1)
  {
    const IteratorType pivot = partition(begin, end);

    if (distance(begin, end) > 10000)
    {
      if (depth < 5) // <--- HERE
      { // PARALLEL
        thread t1([&begin, &pivot](){ quicksort(begin, pivot, depth+1); });
        thread t2([&pivot, &end](){ quicksort(pivot + 1, end, depth+1); });

        t1.join();
        t2.join();
      }
      else
      { // SEQUENTIAL
        quicksort(begin, pivot, depth+1);
        quicksort(pivot + 1, end, depth+1);
      }
    }
  }
}

当 depth < 5 时，它会创建最多约50个线程，这将轻松饱和大多数多核CPU-进一步并行处理不会产生任何好处。

在每个递归调用中创建线程的成本可能可以避免，尤其是考虑到线程不是无限的资源。

睡眠线程实际上没有人们想象的那么昂贵，但没有必要在每个分支处创建两个新线程，可以重复使用当前线程，而不是将其置于睡眠状态...

template <typename IteratorType>
void quicksort(IteratorType begin, IteratorType end, int depth = 0)
{
  if (distance(begin, end) > 1)
  {
    const IteratorType pivot = partition(begin, end);

    if (distance(begin, end) > 10000)
    {
      if (depth < 5)
      {
        thread t1([&begin, &pivot](){ quicksort(begin, pivot, depth+1); });
        quicksort(pivot + 1, end, depth+1);   // <--- HERE

        t1.join();
      } else {
        quicksort(begin, pivot, depth+1);
        quicksort(pivot + 1, end, depth+1);
      }
    }
  }
}

除了使用depth之外，您还可以设置全局线程限制，然后只有在限制尚未达到时才创建新线程 - 如果已经达到，则顺序执行。这个线程限制可以是进程范围的，因此快速排序的并行调用会从协作创建太多线程中退回。

- Andrew Tomazos

---

谢谢。我得出了与“为什么每次调用都要创建两个线程？”这部分相同的结论。如果我确实要为我的线程使用全局计数器，你会用什么来使这个计数器线程安全？ - ereOn

即使有这些建议，也不要直接使用原始线程或线程池来处理嵌套数据/递归并行算法。 - snk_kid

@user1131467 如果你只处理纯粹的平面数据并行性，那没问题，但这不是我们在这里处理的内容，也不是我所说的。使用这种方法编写递归/嵌套数据并行算法是低效的方法，而且众所周知会有各种问题，如过度订阅、负载不均衡等。因此，在这种情况下，你可以做得更好，这并不是“魔术”（我觉得这非常侮辱人），有关该主题的各种论文和实现，目前领先的是工作窃取算法。 - snk_kid

@user1131467，但这种方法并不是最优的！（你发布的代码）而且不具有良好的可扩展性，这就是我的观点！即使OP也知道这一点。线程池只有在减少线程创建成本方面有所帮助，但您仍然会使用变量数量的线程，具体取决于递归的广度/深度。如果您使用基于作业/任务的系统，则始终存在固定数量的工作线程，而不管生成多少任务。线程计数是固定的，并且通常等于硬件线程数。我在游戏行业工作，我们从不像您的代码中编写并行算法。 - snk_kid

这种方法过于复杂，可能会花费更多的时间来处理线程而不是真正的工作。我会选择更高级别的并行处理方式。但在某些情况下（如游戏行业），@snk_kid所说的并不适用。 - Trax

@TraxNet：启动32个线程不会对性能造成太大影响。内核可以轻松管理上下文切换，使其接近最优。NPTL 可以在不到一秒钟内启动100,000个线程。请在做出荒谬的假设之前先测试代码。 - Andrew Tomazos

Answer 2

我不是C++线程专家，但一旦解决了线程问题，您将面临另一个问题：

对输入进行分区的调用未并行化。该调用非常昂贵（需要对数组进行顺序迭代）。

您可以在维基百科上阅读qsort的并行部分：

http://en.wikipedia.org/wiki/Quicksort#Parallelization

这表明一种简单的解决方案是将数组分成几个子数组（例如与CPU核心数量相同），并在并行中对每个子数组进行排序，然后使用合并排序技术合并结果，从而以与您的方法大致相同的速度并行化qsort。

有更好的并行排序算法，但它们可能会变得非常复杂。

- Palo

---

好的，对于quicksort的调用（它又调用了partition），是并行化的，因此partition的调用也是并行化的。感谢提供文章链接。 - ereOn

@ereOn：是的，但是你有一个严重的负载不平衡问题。你的递归只有o（lg（N））深度（例如1M项的20个级别），而你的第一级完全是顺序的，你的第二级仅具有并行性2，等等。通过使用顺序partition（），你严重限制了最大加速比（远低于可能的加速比）。 - Wandering Logic

Answer 3

直接使用线程编写并行算法，特别是分而治之类型的算法是一个糟糕的主意，你将会有较差的可扩展性、负载平衡以及线程创建成本高昂。线程池可以帮助解决后者，但不加额外代码无法解决前者。现在几乎所有现代并行框架都基于基于任务的工作窃取调度器，例如Intel TBB、Microsoft并发运行时（concert）/PPL等。

与其生成线程或从池中重新使用线程，实际上是将“任务”（通常是闭包+一些簿记数据）放入工作窃取队列中，由X个工作者线程中的一个在某个时间点运行。通常线程数等于系统上可用的硬件线程数，因此如果您生成/排队了数百/数千个任务，也不会有太大问题（在某些情况下会有问题，但这取决于上下文）。这对于嵌套/分而治之/分叉-合并并行算法来说是一个更好的情况。

对于（嵌套）数据并行算法，最好避免为每个元素生成一个任务，因为单个元素的操作粒度过小，无法获得任何好处，并被调度程序管理的开销所压倒。因此，在低级工作窃取调度程序之上，您需要一个更高级别的管理来处理将容器分成块。这仍然比使用线程/线程池要好得多，因为您不再基于最佳线程计数进行划分。

无论如何，在C++11中没有标准化的东西，如果您想要一个纯标准库解决方案而不添加第三方依赖项，则最好的选择是：

A. 尝试使用std::async，一些实现（例如VC++）会在底层使用工作窃取调度程序，但没有保证，C++标准也没有强制执行此功能。

B. 在C++11提供的标准线程原语之上编写自己的工作窃取调度程序，这是可行的，但实现起来并不简单。

我建议只需使用Intel TBB，它大多跨平台，并提供各种高级并行算法，如并行排序。

- snk_kid

---

基本上，在这种情况和类似情况下，您建议不要自己管理线程，而是允许某种调度程序（显式或隐式）来完成工作。不幸的是，所有这些实现都需要对非常困难的主题有深入的了解。 - SChepurin

在这里值得一提的是OpenMP。我发现它比TBB更容易使用。 - Jakub M.

Intel TBB、OpenMP等都是用户空间库。在底层，它们像std::thread和其他库一样调用创建线程方法（Linux上的clone，Windows上的CreateThread等）。了解线程的实际含义以及操作系统如何管理它们对于理解它们的性能影响非常重要。许多人不了解创建线程的成本以及内核在它们之间切换时所做的出色工作，因此他们担心微不足道的优化会带来很少的好处。 - Andrew Tomazos