问工作窃取队列在C/C++中的实现

EN

没有免费的午餐。

请看一下the original work stealing paper。这篇论文很难理解。我知道论文包含的是理论证明，而不是伪代码。然而，没有比TBB更简单的版本了。如果有的话，它不会提供最佳的性能。窃取工作本身会带来一些开销，因此优化和技巧非常重要。特别是，出队必须是线程安全的。实现高可伸缩性和低开销的同步是具有挑战性的。

我真的想知道你为什么需要它。我认为正确的实现意味着像TBB和Cilk这样的东西。同样，窃取工作很难实现。

从理论上讲，实现“窃取工作”并不难。您需要一组包含任务的队列，这些任务通过组合执行计算和生成其他任务来完成更多工作。而且您需要对队列进行原子访问，以便将新生成的任务放入这些队列中。最后，您需要一个每个任务在结束时都会调用的过程，以便为执行该任务的线程找到更多工作；该过程需要在工作队列中查找工作。

大多数这样的工作窃取系统都假设有少量的线程(通常由真正的处理器核心支持)，并且每个线程恰好有一个工作队列。然后，您首先尝试从自己的队列中窃取工作，如果队列为空，则尝试从其他队列中窃取工作。棘手的是要知道要查看哪些队列；顺序地扫描它们的工作是相当昂贵的，并且会在寻找工作的线程之间产生大量的争用。

到目前为止，这都是非常通用的东西，只有两个主要的例外: 1)切换上下文(例如，设置处理器上下文寄存器，如“堆栈”)不能用纯C或C++来声明。您可以通过同意以特定于目标平台的机器代码编写包的一部分来解决此问题。2)对多处理器队列的原子访问不能完全在C或C++中完成(忽略Dekker的算法)，因此您需要使用汇编语言同步原语(如X86锁XCH或比较和交换)来编写代码。现在，一旦您有了安全的访问权限，更新queuse所涉及的代码就不是很复杂了，您可以很容易地用几行C语言来编写它。

然而，我想你会发现，试图用C和C++混合汇编程序来编写这样的包仍然是相当低效的，而且你最终还是会用汇编程序来编写整个程序。剩下的都是与C/C++兼容的入口点:-}

我这样做是为了我们的PARLANSE并行编程语言，它提供了在任何时刻进行任意数量的并行计算和交互(同步)的想法。它是在X86上的幕后实现的，每个CPU只有一个线程，而且完全是用汇编语言实现的。窃取工作的代码可能总共有1000行，它的代码很棘手，因为您希望它在非争用情况下非常快。

对于C和C++来说，真正的美中不足之处在于，当你创建一个代表工作的任务时，你分配了多少堆栈空间？串行C/C++程序通过简单地过度分配大量(例如，10Mb)的线性堆栈来避免这个问题，并且没有人太关心这些堆栈空间浪费了多少。但是，如果你可以创建数千个任务，并让它们都在特定的瞬间运行，那么你就不能合理地为每个任务分配10Mb。因此，现在你要么需要静态地确定一个任务需要多少堆栈空间(图灵硬)，要么你需要分配堆栈块(例如，每个函数调用)，而广泛使用的C/C++编译器不会这样做(例如，你可能会使用的)。THe的最后一条出路是限制任务创建，使其在任何时刻都限制在几百个任务中，并在活动的任务中多路复用数百个真正巨大的堆栈。如果任务可以互锁/挂起状态，你就不能做最后一个，因为你会达到你的阈值。所以你只能在任务只做计算的情况下这样做。这似乎是一个相当严格的限制。

对于PARLANSE，我们构建了一个编译器，为每个函数调用分配堆上的激活记录。

有一个工具可以简单地以一种非常优雅的方式做到这一点。这是一种非常有效的方法，可以在很短的时间内并行化你的程序。

Cilk project

高性能计算挑战奖

我们的高性能计算挑战赛2级奖的Cilk参赛作品赢得了2006年最佳优雅与性能组合奖。该奖项于2006年11月14日在坦帕举行的SC'06大会上颁发。