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

Question

过去几天我一直在清理我对排序算法的记忆,而且我遇到了一个我无法找到最佳解决方案的情况.

我写了一个quicksort的基本实现,我想通过并行执行来提高性能.

我得到的是:

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

如果要排序的数组太大或者递归太深,系统可能会用尽线程并且执行失败.

所以在最大深度后顺序...

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,您可以设置全局线程限制,然后仅在未达到限制时创建新线程(如果有),而不是按顺序执行.这个线程限制可以是进程范围的,因此对quicksort的并行调用将从创建太多线程的协同退避.