Joh*_*ohn 14 terminology load-balancing scheduling scheduled-tasks multiprocessor
为什么我能找到很多关于"工作窃取"的信息,而没有关于"工作耸肩"的信息作为动态负载均衡策略？
通过"工作耸肩",我的意思是将多余的工作从繁忙的处理器推到负载较小的邻居,而不是让闲置的处理器从繁忙的邻居那里拉工作("偷工作").
我认为两种策略的一般可扩展性应该相同.但是我认为,就延迟和功耗而言,在确实有工作要做的时候唤醒空闲处理器,而不是让所有空闲处理器周期性地轮询所有邻居以进行可能的工作,它会更有效率.
无论如何,一个快速谷歌没有出现在"工作耸肩"或类似标题下的任何东西,所以任何指向现有技术的指针和这个策略的行话将是受欢迎的.
澄清
我实际上设想工作提交处理器(可能是或可能不是目标处理器)负责查看首选目标处理器的直接位置(基于数据/代码位置)以决定是否应该给予近邻相反,因为他们没有那么多的工作要做.
我不认为决策逻辑在这里需要的不仅仅是对立即(通常是2到4个)邻居的估计q长度的原子读数.我不认为这种情况不会超过盗贼从他们的邻居那里进行民意调查和偷窃所暗示的.(我在两种策略中都假设"无锁,无等待"队列).
解析度
似乎我的意思(但只是部分描述!)作为"工作耸肩"策略是在"正常"的前期调度策略领域,恰好是关于处理器,缓存和内存忠诚以及可扩展的.
我发现很多参考文献都在搜索这些术语,其中一些看起来非常可靠.当我发现一个最符合(或拆除!)逻辑时,我会用我的"工作耸肩"的定义发表参考文献.
And*_*ack 18
负载平衡不是免费的; 它具有上下文切换(到内核),查找空闲处理器以及选择重新分配工作的成本.特别是在任务一直切换的机器中,每秒数十次,这个成本加起来.
那有什么区别？工作耸肩意味着您进一步负担过度配置资源(繁忙的处理器)负担均衡负担.为什么当隔壁的处理器没有任何关系时,用administrivia中断繁忙的处理器？另一方面,工作窃取使空闲处理器运行负载均衡器,而繁忙的处理器继续工作.偷工作可以节省时间.
考虑:处理器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.
我认为这个想法的问题在于它使得实际工作的线程浪费时间不断寻找空闲的处理器.当然有一些方法可以加快速度,比如拥有一个空闲处理器队列,但随后该队列成为并发瓶颈.所以最好让线程没有更好的事情坐下来寻找工作.
据我了解，工作窃取是为高度并行的系统设计的，以避免由单个位置（单线程或单个内存区域）负责共享工作。为了避免这个瓶颈，我认为它确实会在简单的情况下引入低效率。
如果您的应用程序不是那么并行，以至于单点工作分配会导致可伸缩性问题，那么我希望您可以通过按照您的建议显式管理它来获得更好的性能。
恐怕不知道你可能会在谷歌上搜索什么。