c++ - 如何有效地并行化分而治之算法？

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

Answer 1

If the array to sort is too big or the recursion goes too deep, the system can run out of threads and the execution fails miserably.

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

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 饱和 - 进一步的并行性不会产生任何好处。

The cost of creating threads in each recursive call could probably be avoided, especially given that threads are not an infinite resource.

休眠线程并没有人们想象的那么昂贵，但是在每个分支上创建两个新线程是没有意义的，还不如重用当前线程，而不是让它休眠...

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 ，您可以设置全局线程限制，然后仅在未达到限制时才创建新线程 - 如果已达到，则按顺序执行。此线程限制可以是进程范围的，因此对快速排序的并行调用将从创建过多线程的协作中退出。