9

在过去的几天里，我一直在刷新关于排序算法的记忆，我遇到了一种情况，我找不到最好的解决方案是什么。

我写了一个快速排序的基本实现，我想通过并行执行来提高它的性能。

我所拥有的是：

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 工具。

4

3 回答 3

6

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

所以在最大深度之后继续......

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);
      }
    }
  }
}

它将创建最多约 50 个线程，这depth < 5很容易使大多数多核 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，您可以设置全局线程限制，然后仅在未达到限制时创建新线程 - 如果已达到，则按顺序执行。这个线程限制可以是进程范围的，因此对快速排序的并行调用将在创建太多线程时协同退出。

于 2013-04-28T08:46:59.243 回答
1

我不是 C++ 线程专家，但一旦你解决了线程问题，你就会有另一个问题：

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

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

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

它建议以与您的方法大致相同的速度并行化 qsort 的一个简单解决方案是将数组划分为几个子数组（例如，与 CPU 内核一样多），并行排序每个子数组并使用来自的技术合并结果合并排序。

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

于 2013-04-28T08:19:34.203 回答
1

直接使用线程来编写并行算法，尤其是分而治之的算法是一个坏主意，您的扩展性和负载平衡性会很差，而且您知道创建线程的成本很高。线程池可以在不编写额外代码的情况下帮助后者，但不能帮助前者。如今，几乎所有现代并行框架都基于基于任务的工作窃取调度程序，例如 Intel TBB、Microsoft 并发运行时（音乐会）/PPL。

而不是从池中产生线程或重新使用线程，而是将“任务”（通常是闭包+一些簿记数据）放入工作窃取队列中，以在某个点由 X 数量之一运行工作线程。通常，线程数等于系统上可用的硬件线程数，因此如果您生成/排队数百/数千个任务（在某些情况下确实如此，但取决于上下文），这并不重要。对于嵌套/划分和征服/分叉连接并行算法来说，这是一个更好的情况。

对于（嵌套）数据并行算法，最好避免为每个元素生成一个任务，因为通常对单个元素进行操作，工作粒度太小而无法获得任何好处，并且被调度程序管理的开销所抵消，等等较低级别的工作窃取调度程序你有一个更高级别的管理来处理将容器分成块。这仍然比使用线程/线程池好得多，因为您不再根据最佳线程数进行划分。

无论如何，在 C++11 中没有像这样标准化的东西，如果您想要一个纯标准库解决方案而不添加第三方依赖项，那么您可以做的最好的事情是：

A. 尝试使用 std::async，一些像 VC++ 这样的实现会在下面使用一个工作窃取调度程序，但不能保证，C++ 标准也没有强制执行这一点。

B. 在 C++11 附带的标准线程原语之上编写自己的工作窃取调度程序，它是可行的，但正确实现并不那么简单。

我想说的是英特尔 TBB，它主要是跨平台的，并提供各种高级并行算法，如并行排序。

于 2013-04-28T09:49:54.517 回答