terminology - "Work stealing"与 "Work shrugging"?

Question

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

通过“工作耸肩”，我的意思是将多余的工作从繁忙的处理器转移到负载较低的邻居上，而不是让空闲的处理器从忙碌的邻居那里拉工作(“工作窃取”)。

我认为这两种策略的总体可扩展性应该相同。但是，我相信，在延迟和功耗方面，当空闲处理器确实有工作要做时唤醒它会更有效率，而不是让所有空闲处理器定期轮询所有邻居以进行可能的工作。

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

澄清

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

我不认为决策逻辑需要的不仅仅是对直接(通常是 2 到 4 个)邻居的估计 q 长度的原子读取。我不认为这比窃贼从邻居那里进行民意调查和偷窃所暗示的更耦合。 (我在这两种策略中都假设“无锁、无等待”队列)。

解析度

似乎我的意思(但只是部分描述!)作为“工作耸肩”策略属于“正常”预先调度策略的领域，这些策略恰好在处理器、缓存和内存忠诚度以及可扩展性方面很聪明。

我发现有很多关于这些术语的引用文献，其中一些看起来非常可靠。当我确定一个最符合(或破坏!)我对“工作耸肩”的定义的逻辑时，我会发布一个引用。

Answer 1

负载均衡不是免费的；它具有上下文切换(到内核)、查找空闲处理器和选择要重新分配的工作的成本。尤其是在任务一直切换，每秒数十次的机器中，这种成本加起来。

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

例子

考虑:处理器 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 上。