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

Question

我正在寻找C/CPP中工作窃取队列的正确实现.我环顾了谷歌,但没有找到任何有用的东西.

也许有人熟悉一个好的开源实现？(我不想实施原始学术论文中的伪代码).

Answer 1

没有免费的午餐.

请看看原始作品偷纸.这篇论文很难理解.我知道那篇论文包含理论证明而不是伪代码.但是,没有比TBB 更简单的版本.如果有的话,它将无法提供最佳性能.工作窃取本身会产生一些开销,因此优化和技巧非常重要.特别是,出列必须是线程安全的.实现高度可扩展和低开销的同步具有挑战性.

我真的很想知道你为什么需要它.我认为适当的实现意味着像TBB和Cilk.再次,工作窃取很难实现.

Answer 2

实施"偷工作"在理论上并不难.您需要一组包含任务的队列,这些任务通过结合计算和生成其他任务来完成更多工作.您需要对队列进行原子访问才能将新生成的任务放入这些队列中.最后,您需要一个每个任务最后调用的过程,以便为执行任务的线程找到更多工作; 该程序需要查找工作队列才能找到工作.

大多数此类工作窃取系统假设存在少量线程(通常由实际处理器核心备份),并且每个线程只有一个工作队列.然后你首先尝试从你自己的队列中窃取工作,如果它是空的,试着从别人那里窃取.棘手的是知道要查找哪些队列; 为了工作而连续扫描它们非常昂贵,并且可能在寻找工作的线程之间产生大量争用.

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

但是,我认为你会发现尝试使用混合汇编程序在C和C++中编写这样的包仍然是相当低效的,并且最终你最终会在汇编程序中编写整个代码.剩下的就是C/C++兼容的入口点: - }

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

对于C和C++,美中不足的是,当你创建一个代表工作的任务时,你分配了多少堆栈空间？串行C/C++程序通过简单地分配大量(例如,10Mb)的一个线性堆栈来避免这个问题,并且没有人关心浪费了多少堆栈空间.但是,如果您可以创建数千个任务并让它们全部在特定时刻生效,那么您无法合理地为每个任务分配10Mb.所以现在你需要静态地确定一个任务需要多少堆栈空间(Turing-hard),或者你需要分配堆栈块(例如,每个函数调用),广泛使用的C/C++编译器不做(例如,您可能使用的那个).最后一条出路是限制任务创建,以便在任何时刻将其限制为几百,并在现场任务中复用几百个非常庞大的堆栈.如果任务可以互锁/暂停状态,则无法执行最后操作,因为您将遇到阈值.因此,只有在任务只进行计算时才能执行此操作.这似乎是一个非常严格的限制.

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