线程池如何处理C++中的高递归任务？

Hi：我计划用C++写一个线程池，允许用户提交任务并执行。例如，在8核机器上，理想情况下8个工人可以并行执行。然而，当我仔细思考时，我发现了一个问题。假设我有一个像计算斐波那契这样的任务：

int fib(int n) {
  if (n <= 1) {
    return 1;
  }
  return fib(n-1) + fib(n-2);
}

如果我使用线程池来做这件事，我可能会写这样的代码：

int fib(int n) {
  if (n <= 1) {
    return 1;
  }
  // in form of std::future you can wait upon
  auto fut_n_1 = pool.submit(fib, n-1);
  auto fut_n_2 = pool.submit(fib, n-2);
  return fut_n_1.get() + fut_n_2.get();
}

但是当fib（n）在一个线程worker上计算时，它会产生另外两个任务要由其他worker完成。它必须等待fut_n_1和fut_n_2。这样，很快所有8个线程worker都卡住了。即使我们允许产生更多的线程worker，线程重写的代价也会迅速恶化系统性能。
我不是在问如何“更好地写斐波那契函数”，我是在想如何设计线程池，以便在处理quicksort这样的高递归任务时，您可以以某种方式记住“上下文”并自行销毁。我已经看到一些古老的系统可以使用sys_set_jump来完成Clik这样的任务。但我不太喜欢使用太低级的细节。**有没有任何现代C++技术可以达到或多或少相同的效果？
我在这里粘贴我当前的线程池实现以供参考：
一个二个一个一个

这不是关于C++的，而是关于通过复用真实的的线程来管理伪线程的。
你要做的是提供一组队列，每个真实的线程一次。队列基本上是需要完成的工作的集合，例如，它是一个延续列表（通过存储机器状态（PC，ESP，...）实现）。
然后，每当程序的一部分想要分叉时，“分叉”艾德代码的延续被放置在线程队列中。这是一个由每个线程分配器分配的小块，所以它非常快。
当一个程序用完了工作时，底层线程检查它的队列，如果它包含一些东西，则从队列中提取该延续，并且线程“成为”该延续（通常意味着加载密钥寄存器，PC，ESP...）
如果一个线程的队列为空，它必须从另一个线程的队列中窃取工作。是的，这意味着在队列周围加锁。如果它在任何队列中都没有发现工作，那么线程可以进入睡眠状态，并以不同的时间间隔重复检查自己的队列和其他队列。
如果没有任何控制，这可能会产生大量的延续。数百万应该不是问题，但这确实会使用大量的内存，然后该高速缓存行为并不像你希望的那样好。
但是如果你需要一个大小的限制，那么fork逻辑只需要检查队列大小;如果大于阈值，则它简单地“调用”“分叉”代码，并且在返回时，执行分叉代码的继续。
你想要的概念和实现细节叫做“工作窃取调度器”;请参阅https://en.wikipedia.org/wiki/Work_stealing。Cilk（不是Clik）也会这样做。
你可能会觉得这篇文章很有趣;它描述了一种语言PARLANSE，它可以做到：http://semanticdesigns.com/Company/Publications/Parallelism-in-symbolic-computation.pdf
这是你在PARLANSE中的斐波那契函数（是的，它真的运行了）：

(define fibonacci
   (lambda (function natural natural )function 
   `Given n, computes nth fibonacci number'
   (ifthenelse (<= ? 1)
               ?
               (let (;; [n natural ] [m natural ]  )
                       (value (|| (= m (fibonacci (-- ?)) )=
                                  (= n (fibonacci (- ? 2)) )=
                              )||
                              (+ m n)
                       )value
               )let
   )ifthenelse  
   )lambda
)define

该“（||……）||operator表示“并行运行这些”。支持分叉/管理队列的所有有趣的机制都在PARLANSE运行时系统中，并且在遇到并行操作符时由来自PARLANSE编译器的调用调用。
我们将其作为一个玩具/测试运行，通常作为（fibonacci 45），这将产生相当多的并行粒度。PARLANSE运行时将队列大小限制为一个适度的数字，如16。这与小队列并行运行。
这样做的fibonacci不是非常有效，因为每个分叉的颗粒的工作量非常小，并且管理颗粒的工作淹没了并行性的优势。但是如果你实现递归排序并在排序小列表时终止递归（比如，大小为8或更大），那么并行性工作得很好。

线程池如何处理C++中的高递归任务？

1条答案

相关问题

热门标签

最新问答