在C / C ++中实现工作窃取队列？
我正在寻找在C / CPP中正确实施工作窃取队列。 我浏览过Google，但没有发现任何有用的东西。
也许有人熟悉一个好的开源实现？ （我不想实施从原始学术论文中获得的伪代码）。
没有免费的午餐。
请看看原来的偷书工作。 这篇文章很难理解。 我知道纸张包含理论证明而不是伪代码。 然而，没有比TBB更简单的版本。 如果有的话，它不会提供最佳性能。 偷工作本身会产生一些开销，所以优化和窍门非常重要。 尤其是，出队是必须是线程安全的。 实现高度可扩展性和低开销的同步是具有挑战性的。
我真的好奇你为什么需要它。 我认为正确的实施意味着TBB和Cilk。 再一次，盗窃工作很难实施。
看看英特尔的线程构建模块。
http://www.threadingbuildingblocks.org/
实施“偷工减料”理论上并不难。 您需要一组包含通过组合计算和生成其他任务来完成更多工作的任务的队列。 而且您需要对队列进行原子访问才能将新生成的任务放入这些队列中。 最后，你需要一个程序，每个任务在最后调用，为执行任务的线程找到更多的工作; 该程序需要在工作队列中查找工作。
大多数这样的工作窃取系统假设有少量线程（通常由真实处理器核心备份），并且每个线程只有一个工作队列。 然后，你首先尝试从你自己的队列中窃取工作，如果它是空的，则尝试从别人那里偷窃。 棘手的是知道要查找哪些队列; 连续扫描它们的工作非常昂贵，并且可能在寻找工作的线程之间创建大量的争用。
到目前为止，这是所有非常普通的东西，只有两个主要的例外：1）切换上下文（例如，设置处理器上下文寄存器，如“堆栈”）不能在纯C或C ++中声明。 您可以通过同意在目标平台特定的机器代码中编写部分软件包来解决此问题。 2）对多处理器队列的原子访问不能纯粹用C或C ++（忽略Dekker算法）完成，因此需要使用汇编语言同步原语（如X86 LOCK XCH或Compare和Swap）对其进行编码。 现在，一旦你有安全的访问权限，涉及到更新quese的代码并不是很复杂，你可以很容易地在几行C中写入。
不过，我认为你会发现试图用C和C ++编写这样一个包含混合汇编程序的软件包仍然效率不高，最终你最终会用汇编语言编写整个代码。 所有剩下的都是C / C ++兼容的入口点： - }
我为我们的PARLANSE并行编程语言做了这个，它提供了在任何时刻任意大量并行计算的实时和交互（同步）的想法。 它在X86的幕后实现，每个CPU只有一个线程，实现完全是汇编。 盗窃工作代码大概有1000行，其代码非常复杂，因为您希望它在非争用情况下非常快速。
对于C和C ++来说，美中不足的是，当你创建一个代表工作的任务时，你分配了多少堆栈空间？ 串行C / C ++程序通过简单地分配大量（例如10Mb）的一个线性堆栈来避免这个问题，并且没有人关心堆栈空间被浪费了多少。 但是，如果您可以创建数千个任务并让它们全部生活在特定时刻，则无法合理地为每个任务分配10Mb。 所以现在你需要静态地确定一个任务需要多少堆栈空间（图灵硬件），或者你需要分配堆栈块（例如，每个函数调用），哪些广泛可用的C / C ++编译器不会做（例如，你可能使用的那个）。 最后的出路是限制任务创建，以便在任何时候将其限制为几百个，并且在活动任务中复用几百个真正巨大的堆栈。 如果任务可以互锁/暂停状态，则无法完成最后一个任务，因为您会遇到您的阈值。 所以你只能做这个，如果任务只做计算。 这似乎是一个非常严格的约束。
对于PARLANSE，我们构建了一个编译器，为每个函数调用在堆上分配激活记录。
链接地址: http://www.djcxy.com/p/6779.html