14

为什么我可以找到很多关于“工作窃取”的信息，而没有找到关于“工作耸耸肩”作为动态负载平衡策略的信息？

“工作耸肩”是指将多余的工作从繁忙的处理器推到负载较轻的邻居身上，而不是让空闲的处理器从繁忙的邻居那里拉出工作（“工作窃取”）。

我认为这两种策略的一般可扩展性应该是相同的。但是，我相信，就延迟和功耗而言，在肯定有工作要做时唤醒空闲处理器会更有效，而不是让所有空闲处理器定期轮询所有邻居以寻找可能的工作。

无论如何，一个快速的谷歌没有在“工作耸肩”或类似的标题下显示任何内容，因此任何指向现有技术和该策略的行话的指针都会受到欢迎。

澄清

我实际上设想工作提交处理器（可能是也可能不是目标处理器）负责查看首选目标处理器的直接位置（基于数据/代码位置），以决定是否应该为近邻提供新的而是工作，因为他们没有那么多工作要做。

我认为决策逻辑需要的不仅仅是原子读取此处的直接（通常为 2 到 4 个）邻居的估计 q 长度。我不认为这比盗贼从他们的邻居那里轮询和偷窃所暗示的耦合更多。（我在这两种策略中都假设“无锁、无等待”队列）。

解析度

似乎我的意思（但只是部分描述！）作为“工作耸耸肩”策略是在“正常”前期调度策略的领域，这些策略恰好对处理器、缓存和内存忠诚度以及可扩展性很聪明。

我发现很多关于这些术语的参考文献搜索，其中一些看起来很可靠。当我确定一个最符合（或破坏！）我对“工作耸肩”定义的逻辑时，我将发布一个参考。

4

6 回答 6

19

负载均衡不是免费的；它的代价是上下文切换（到内核）、查找空闲处理器以及选择重新分配的工作。尤其是在一台任务一直切换的机器上，每秒几十次，这个成本加起来。

那么有什么区别呢？工作耸肩意味着您通过负载平衡的开销进一步负担过度配置的资源（繁忙的处理器）。当隔壁有一个处理器无事可做时，为什么要中断一个繁忙的处理器呢？另一方面，工作窃取让空闲处理器运行负载平衡器，而忙碌的处理器继续工作。偷工减料可以节省时间。

例子

考虑：处理器 A 有两个任务分配给它。它们分别需要时间a1和a2。附近的处理器 B（可能是缓存反弹的距离）处于空闲状态。处理器在所有方面都是相同的。我们假设每个任务的代码和内核都在两个处理器的 i-cache 中（在负载平衡上没有添加页面错误）。

任何类型的上下文切换（包括负载平衡）都需要时间c。

无负载平衡

完成任务的时间为a1 + a2 + c。处理器 A 将完成所有工作，并在两个任务之间进行一次上下文切换。

偷工减料

假设 B 窃取a2，导致上下文切换时间本身。这项工作将在max(a1, a2 + c)时间内完成。假设处理器 A 开始处理a1；当它这样做时，处理器 B 将窃取a2并避免 a1 处理中的任何中断。B 上的所有开销都是空闲周期。

如果a2是较短的任务，那么在这里，您有效地隐藏了在这种情况下上下文切换的成本；总时间为a1。

工作耸肩

假设 B 完成了a2，如上所述，但 A 产生了移动它的成本（“耸耸肩”工作）。这种情况下的工作将在max(a1, a2) + c时间内完成；上下文切换现在总是除了总时间之外，而不是被隐藏。处理器 B 的空闲周期在这里被浪费了；取而代之的是，繁忙的处理器 A 将工作交给 B 花费了很多时间。

于 2010-03-31T18:01:23.567 回答
5

我认为这个想法的问题在于它使有实际工作的线程浪费时间不断地寻找空闲的处理器。当然，有一些方法可以提高速度，比如拥有一个空闲处理器队列，但随后该队列成为并发瓶颈。所以最好让那些无事可做的线程坐下来寻找工作。

于 2010-03-31T15:18:04.897 回答
3

“工作窃取”算法的基本优势在于，当每个人都很忙时，移动工作的开销会降至 0。因此，只有在某些处理器本来空闲时才会产生开销，并且该开销成本主要由空闲处理器支付，而繁忙的处理器只有非常小的总线同步相关成本。

于 2010-03-31T17:45:10.330 回答
2

据我了解，工作窃取是为高度并行的系统设计的，以避免让单个位置（单个线程或单个内存区域）负责共享工作。为了避免这个瓶颈，我认为它确实在简单的情况下引入了低效率。

如果您的应用程序不是那么并行以至于单点工作分配导致可伸缩性问题，那么我希望您可以通过按照您的建议明确管理它来获得更好的性能。

恐怕不知道你可能会用谷歌搜索什么。

于 2010-03-31T13:00:22.850 回答
2

一些问题......如果一个繁忙的线程很忙，您是否不希望它花时间处理实际工作而不是推测性地寻找空闲线程来卸载？

您的线程如何决定什么时候它有这么多工作应该停止工作以寻找可以提供帮助的朋友？

你怎么知道其他线程没有那么多工作并且你找不到合适的线程来卸载？

工作窃取似乎更优雅，因为以一种方式解决了相同的问题（争用），保证执行负载平衡的线程只在执行负载平衡，否则它们本来是空闲的。

我的直觉是，从长远来看，您所描述的不仅效率会低得多，而且需要对每个系统进行大量调整才能获得可接受的结果。

尽管在您的编辑中，您建议您希望提交处理器来处理此问题，而不是您之前建议的工作线程以及此处的一些评论。如果提交处理器正在搜索最小的队列长度，您可能会增加提交的延迟，这并不是一个真正可取的事情。

但更重要的是，它是对工作窃取的补充技术，而不是相互排斥的技术。你已经潜在地缓解了一些关于工作窃取是为了控制而发明的争论，但是在你得到好的结果之前你还有很多事情需要调整，这些调整不会对每个系统都是一样的，而且你仍然有可能遇到偷工减料对你有帮助的情况。

我认为您编辑的建议，提交线程执行“智能”工作分配可能是针对工作窃取的过早优化。您的空闲线程是否如此猛烈地撞击总线以致您的非空闲线程无法完成任何工作？然后是优化工作窃取的时候了。

于 2010-04-01T09:14:34.717 回答
0

因此，与“工作窃取”相比，“工作耸耸肩”的真正含义是一种正常的前期工作调度策略，它对处理器、缓存和内存忠诚度以及可扩展性都很聪明。

搜索上述术语/行话的组合会产生许多重要的后续参考。一些解决了机器虚拟化增加的复杂性，这实际上并不是提问者关心的问题，但一般策略仍然是相关的。

于 2010-03-31T21:19:14.533 回答