问题标签 [work-stealing]

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

也许有人熟悉一个好的开源实现？（我不喜欢实现取自原始学术论文的伪代码）。

我一直在研究我正在实现的线程池的不同调度算法。由于我正在解决的问题的性质，我可以假设并行运行的任务是独立的，不会产生任何新任务。任务的大小可以不同。

我立即选择了最流行的调度算法“工作窃取”，使用本地作业队列的无锁双端队列，我对这种方法比较满意。但是我想知道是否有任何常见的情况下工作窃取不是最好的方法。

对于这个特定的问题，我对每个单独任务的大小有一个很好的估计。工作窃取没有使用这些信息，我想知道是否有任何调度程序可以提供比使用这些信息进行工作窃取更好的负载平衡（显然具有相同的效率）。

注意。这个问题与上一个问题有关。

我正在阅读一篇关于并发运行时的文章，这篇文章中提到了算法work stealing。但我不知道这个算法是什么！所以我想要一点解释或一些好的链接，可以帮助我介绍这个算法。

在我的项目中，我正在构建一个 Java 执行框架，用于接收来自客户端的工作请求。工作（不同大小）被分解为一组任务，然后排队等待处理。有单独的队列来处理每种类型的任务，并且每个队列都与一个 ThreadPool 相关联。ThreadPools 的配置方式使得引擎的整体性能是最佳的。

这种设计有助于我们有效地对请求进行负载平衡，并且大型请求最终不会占用系统资源。但是，有时当某些队列为空并且它们各自的线程池处于空闲状态时，该解决方案变得无效。

为了更好地做到这一点，我正在考虑实施一种工作/任务窃取技术，以便负载重的队列可以从其他线程池中获得帮助。但是，这可能需要实现我自己的 Executor，因为 Java 不允许多个队列与 ThreadPool 相关联，并且不支持工作窃取概念。

阅读有关 Fork/Join 的信息，但这似乎不适合我的需求。构建此解决方案的任何建议或替代方法都可能非常有帮助。

谢谢安迪

在我的程序中，我为内核 lauch 中发布的每个块都有一个工作双端队列。每个块都停留在循环中，在其双端队列中弹出工作，处理它并将动态生成的工作推回。维护了一组双端队列标志，指示哪些双端队列处于活动状态，即有工作。如果双端队列为空，内核进入另一个循环，试图从另一个块的双端队列中窃取工作。当没有更多的双端队列处于活动状态时，达到停止条件。

在测试中，我设置了从 1 个工作项开始的所有双端队列。我的问题是某些块似乎根本没有运行。由于其中一些没有运行，它们保持活动状态，我的程序进入无限循环。

现在到代码。内核和辅助弹出和推送功能：

这是测试：

使用 NSight 调试此代码我已经验证只有前 8 个块正在运行。我想知道这是否是一个调度问题并且 popWork 轮询正在消耗所有资源，或者它只是我程序中的一个错误。任何帮助将不胜感激。

我想改进我的 fork/join 小示例，以表明在 Java Fork/Join 框架执行期间会发生工作窃取。

我需要对以下代码进行哪些更改？示例的目的：只需对多个线程之间的值分解工作进行线性研究。

我将首先进行一些上下文化。我正在尝试使用 CUDA 中的双端队列实现非阻塞工作窃取方法。双端队列 (aDeques) 位于全局内存中的块分段数组中，并且 popWork() 设备函数的目标是弹出工作以提供线程。除了全局双端队列之外，每个块在共享内存（aLocalStack）中都有一个堆栈，它可以在本地工作。流行音乐发生在 3 个级别。第一次尝试在共享堆栈中，第二次尝试在块拥有的双端队列中，第三次尝试是窃取其他双端队列。每个双端队列都有全局底部和弹出指针，它们位于全局内存数组（aiDequesBottoms 和 auiDequesAges）中。我的问题是，当一个块更改全局双端队列指针时，当我在 GTS450 中测试代码时，其他块看不到更改。好像缓存没有被更新。我也在GT520卡上测试过，没有出现这个问题。我在使用 aiDequeFlags 数组时遇到过类似的问题。通过将其声明为 volatile 可以解决这些问题。不幸的是，我不能对双端队列指针数组做同样的事情，因为我以后需要对它们使用原子函数。很抱歉没有把问题放在一个更简单的例子中，但我无法重现这种行为。第一个片段解释了 popWork() 接口。很抱歉没有把问题放在一个更简单的例子中，但我无法重现这种行为。第一个片段解释了 popWork() 接口。很抱歉没有把问题放在一个更简单的例子中，但我无法重现这种行为。第一个片段解释了 popWork() 接口。

第二个片段具有完整的功能。使用该函数的内核以 8 个块、64 个线程启动，一开始只有 deque 0 有 1 个工作，而所有其他 deque 都是空的。有一些调试 printf 调用来生成日志，这将在下一个片段中显示。

}

最后一个片段是生成的日志。推送线（“Block X push.Bottom=Y”）由此处未显示的推送功能生成。请记住，一开始，只有块 0 有 1 个工作。

可以看出，只有block 4可以看到block 0 deque底部指针的变化。我尝试在指针发生任何更改后添加一些 __threadfence() 调用，但没有成功。感谢关注！

以下是正确的吗？

• 如果必须以多种方式（io 操作或注释）处理每个条目，则破坏者模式具有更好的并行性能和可扩展性，因为可以使用多个消费者并行化而不会发生争用。
• 相反，如果每个条目只能以单一方式处理，工作窃取（即在本地存储条目并从其他线程窃取条目）具有更好的并行性能和可伸缩性，因为在中断模式中将条目不相交地分布到多个线程会导致争用。

（当涉及多个生产者（即CAS 操作）时，破坏者模式是否仍然比其他无锁多生产者多消费者队列（例如来自 boost ）快得多？）

我的详细情况：

处理一个条目可以产生几个新条目，最终也必须处理这些条目。性能具有最高优先级，按 FIFO 顺序处理的条目具有第二优先级。

在当前的实现中，每个线程都使用本地 FIFO，并在其中添加新条目。空闲线程从其他线程的本地 FIFO 窃取工作。线程处理之间的依赖关系使用无锁、机械同理哈希表（写入时的 CAS，具有桶粒度）来解决。这导致争用非常低，但 FIFO 顺序有时会被破坏。

使用破坏者模式将保证 FIFO 顺序。但是，将条目分配到线程上会不会导致比具有工作窃取的本地 FIFO 更高的争用（例如，读取光标上的 CAS）（每个线程的吞吐量大致相同）？

我找到的参考资料

关于破坏者的标准技术文件（第 5 + 6 章）中的性能测试不包括不相交的工作分布。

https://groups.google.com/forum/?fromgroups=#!topic/lmax-disruptor/tt3wQthBYd0是我找到的关于破坏者 + 工作窃取的唯一参考。它指出如果有任何共享状态，每个线程的队列会显着变慢，但没有详细说明或解释原因。我怀疑这句话是否适用于我的情况：

• 使用无锁哈希表解析共享状态；
• 必须在消费者之间不连贯地分发条目；
• 除了工作窃取之外，每个线程只在其本地队列中读写。

我是 cilk++ 的新手，我想使用 cilk 的工作窃取调度程序。我找不到太多这方面的信息。有人可以帮我解决这个问题吗？谢谢。

我一直在尝试了解有关 CLR 4.0 的更多详细信息。以及微软推荐的线程池和不同的策略。我认为自己在很多这些主题上都处于最新状态，并且每天都使用线程和并发代码。

最近，我再次回顾了Parallel Patterns and Practices ，对分散式调度技术部分进行了简要介绍，该部分简要概述了“工作窃取”以及本地与全局线程队列。

我的问题是：

1)偷工作是选择加入还是选择退出？使用本地线程队列也一样吗？或者 CLR 4.0 默认情况下会发生这种情况吗？

2）我们是否可以控制我们是使用本地线程队列还是全局线程队列？如果是这样，通过什么 API 调用？