执行工作，偷走队列在C/C++？
https://stackoverflow.com/questions/2101789
-
21-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我在寻找一个适当的执行工作，偷走队列在C/CPP。我看了看四周谷歌但是还没有找到任何有用的。
也许有人熟悉的一个良好的开放源码的执行？(我不喜欢实施的伪码取自原来的学术论文).
解决方案
否免费的午餐。
请看看原来的工作窃取纸。本文是很难理解。我知道，纸包含了理论依据，而不是伪代码。然而，根本就没有这样的更简单的版本比TBB。如果有，它不会给最优的性能。工作窃取本身会带来额外开销的一些量，从而优化和技巧是非常重要的。特别是，出队都必须是线程安全的。实施高度可扩展的和低开销的同步是具有挑战性。
我真的不知道为什么你需要它。我认为的正确实施的手段类似TBB和Cilk的。再次，工作窃取是很难实现的。
其他提示
看看英特尔线程构建模块。
要落实“工作窃取”也不是很难在理论上。你需要一组包含通过做计算和生成其他任务做更多的工作的组合做的工作任务队列。而你需要的原子访问队列地方新生成任务到这些队列。最后，你需要一个过程，在最后每个任务调用，找到该所执行的任务的线程，更多的工作;该过程需要寻找在工作队列找工作。
大多数这样的工作窃取系统使得有螺纹（由实处理器内核备份通常）的数量少的假设，并且存在每一个线程正好一个工作队列。然后，你先试着从自己的队列中窃取的工作，如果是空的，试着从别人窃取。什么得到棘手的是知道在看哪个队列;扫描他们连续工作是相当昂贵的，可以找工作线程之间创造了巨大的竞争的量。
到目前为止，这是所有相当通用的东西与一个两个主要的例外：1）切换上下文（例如，设置处理器上下文作为“堆栈”寄存器等）不能在纯C或C中说明++。您可以通过同意写入目标平台的特定机器代码的软件包的一部分解决这个问题。 2）原子进入队列多处理器不能在C或C纯粹做++（忽略德克尔的算法），所以你需要的代码使用汇编这些语言同步原语像X86 LOCK XCH或比较和交换。现在，参与更新queuse一旦你有安全访问代码不是很复杂的，你可以很容易地写在C几行。
不过，我想你会发现是试图用混合汇编C和C ++代码，这样的方案仍然是相当低效，你会最终结束了反正编码汇编整个事情。留下所有的是C / C ++兼容入口点： - }
我这样做是为我们的 PARLANSE 并行编程语言，它提供了一个任意大的想法并行计算的数目和生活在任何时刻进行交互（synchonizing）。它在x86幕后实现正好与每个CPU有一个线程，且实现完全汇编。该工作窃取代码可能是1000行合计，其棘手的代码，因为你希望它是非常快的非竞争情况。
美中不足真正的飞C和C ++，当你创建一个表示工作任务，多少堆栈空间，你的工作？串行C / C ++程序避免这个问题通过简单地overallocating巨额（例如，10MB），一个线性堆栈，并且无人问津许多关于多，堆栈空间的如何被浪费了。但如果你能创造数千个任务，并让他们都住在一个特定时刻，你不能合理分配10MB增加到每一个。所以，现在你要么需要确定静态任务将堆栈需要多少空间（图灵硬），或者你需要分配堆栈块（例如，每个函数调用），其广泛使用的C / C ++编译器不这样做（例如，一个你很可能使用）。最后的出路是节流任务创建将其限制在几百个在任何时刻，那是活的任务中复几百真是巨大的堆栈。你不能做最后如果任务可以互锁/暂停状态，因为你会遇到你的门槛。所以，你只能这样做，如果该任务的只有的做计算。这似乎是一个相当严重的制约。
有关PARLANSE，我们建立了一个编译器，激活分配在堆中每个功能的呼叫记录。
有存在的工具，简单地做它以非常优雅的方式。它是在一个很短的时间内parrallelize程序中的一个真正有效的方法。
HPC挑战奖
我们的Cilk的条目为HPC挑战 第2类奖荣获2006年奖 ``优雅的最佳结合 性能''。该奖项是在做 SC'06在Tampa于2006年11月14日
如果你正在寻找一个在C ++中一个独立的workstealing队列类的实现建立在并行线程或升压::线程，运气好的话，据我所知，没有一个。
然而，正如其他人所说的Cilk，TBB和微软的PPL都已经引擎盖下workstealing实现。
现在的问题是你想使用workstealing队列或实现一个？如果你只是想用一个那么，上述的选择是很好的出发点，只需在任何一个就足够了调度“任务”。
由于BlueRaja说PPL的task_group＆structured_task_group将做到这一点，还请注意，这些类在英特尔TBB的最新版本也是可用的。的并行循环（parallel_for时，parallel_for_each）也与workstealing实现。
如果你一定要看看源，而不是使用一个实现，TBB是开源和微软发布其CRT的来源，所以你可以去洞穴探险。
您也可以看看乔·达菲的博客的C＃实现（但它的C＃和内存模型是不同的）。
-Rick
的 structured_task_group 类的 PPL 使用的工作，偷走队列为其执行情况。如果你需要一个劳动力技能资格，用于线，我将建议。
如果你是真的在寻找源，我不知道如果代码是鉴于在人.h或者如果有一个编译对象；我会检查的时候我今晚回家。
的OpenMP很可能支持工作窃取虽然其称为递归并行
OpenMP规范定义任务的构建体（其可以是嵌套的，因此非常适合于递归并行），但不指定他们如何它们是如何实现的细节。 OpenMP的实现方式中，包括gcc，通常使用某种形式的工作窃取为任务，虽然确切的算法（以及所得到的性能）可能会有所不同！
请参阅#pragma omp task和#pragma omp taskwait
<强>更新
此开源库 https://github.com/cpp-taskflow/cpp-taskflow 支撑工作窃取线程池自2018年12月。
看一看的WorkStealingQueue类，它实现工作窃取队列如在论文中描述“动态循环工作窃取的Deque，” SPAA，2015。
威尔打破你的工作任务分解成更小的单位消除偷工作摆在首位的需求？
我有移植本C项目以C ++。
当阵列被扩展原始Steal可能会遇到一个脏读取。我试图修正错误，但最终放弃了，因为我没有实际需要动态扩展堆栈。而不是试图分配空间时，Push方法简单地返回false。然后主叫方可以执行旋转等待，即while(!stack->Push(value)){}。
#pragma once
#include <atomic>
// A lock-free stack.
// Push = single producer
// Pop = single consumer (same thread as push)
// Steal = multiple consumer
// All methods, including Push, may fail. Re-issue the request
// if that occurs (spinwait).
template<class T, size_t capacity = 131072>
class WorkStealingStack {
public:
inline WorkStealingStack() {
_top = 1;
_bottom = 1;
}
WorkStealingStack(const WorkStealingStack&) = delete;
inline ~WorkStealingStack()
{
}
// Single producer
inline bool Push(const T& item) {
auto oldtop = _top.load(std::memory_order_relaxed);
auto oldbottom = _bottom.load(std::memory_order_relaxed);
auto numtasks = oldbottom - oldtop;
if (
oldbottom > oldtop && // size_t is unsigned, validate the result is positive
numtasks >= capacity - 1) {
// The caller can decide what to do, they will probably spinwait.
return false;
}
_values[oldbottom % capacity].store(item, std::memory_order_relaxed);
_bottom.fetch_add(1, std::memory_order_release);
return true;
}
// Single consumer
inline bool Pop(T& result) {
size_t oldtop, oldbottom, newtop, newbottom, ot;
oldbottom = _bottom.fetch_sub(1, std::memory_order_release);
ot = oldtop = _top.load(std::memory_order_acquire);
newtop = oldtop + 1;
newbottom = oldbottom - 1;
// Bottom has wrapped around.
if (oldbottom < oldtop) {
_bottom.store(oldtop, std::memory_order_relaxed);
return false;
}
// The queue is empty.
if (oldbottom == oldtop) {
_bottom.fetch_add(1, std::memory_order_release);
return false;
}
// Make sure that we are not contending for the item.
if (newbottom == oldtop) {
auto ret = _values[newbottom % capacity].load(std::memory_order_relaxed);
if (!_top.compare_exchange_strong(oldtop, newtop, std::memory_order_acquire)) {
_bottom.fetch_add(1, std::memory_order_release);
return false;
}
else {
result = ret;
_bottom.store(newtop, std::memory_order_release);
return true;
}
}
// It's uncontended.
result = _values[newbottom % capacity].load(std::memory_order_acquire);
return true;
}
// Multiple consumer.
inline bool Steal(T& result) {
size_t oldtop, newtop, oldbottom;
oldtop = _top.load(std::memory_order_acquire);
oldbottom = _bottom.load(std::memory_order_relaxed);
newtop = oldtop + 1;
if (oldbottom <= oldtop)
return false;
// Make sure that we are not contending for the item.
if (!_top.compare_exchange_strong(oldtop, newtop, std::memory_order_acquire)) {
return false;
}
result = _values[oldtop % capacity].load(std::memory_order_relaxed);
return true;
}
private:
// Circular array
std::atomic<T> _values[capacity];
std::atomic<size_t> _top; // queue
std::atomic<size_t> _bottom; // stack
};
全部要点（包括单元测试）。的我只强大的体系结构进行的测试（86/64），这样就虚弱的架构去，如果你尝试使用此对例如，您的里程可能会有所不同氖/ PPC。
我不认为 JobSwarm 使用工作窃取，但它是第一步。我不知道为了这个目的其他的开源库。
说不上这是否会是对你有些帮助，但看看的 AMD的开发者网络，其简单对这个的文章，但应该给你一些有用的东西。
