A simple load balancing scheme for task allocation in parallel machines
A simple load balancing scheme for task allocation in parallel machines
复制标题
DOI：
10.1145/113379.113401
复制
发表时间：
1991-06
期刊：
影响因子：
--
通讯作者：
L. Rudolph;M. Allalouf;E. Upfal
中科院分区：
文献类型：
--
作者：
L. Rudolph;M. Allalouf;E. Upfal
本地工作堆（任务队列）的集合和简单的负载平衡方案非常适合在共享内存并行机中调度任务。在这样的机器上的任务调度通常是通过一个单一的，全球可访问的，工作堆。在本文中介绍的计划实现了平衡的全球工作堆，同时最大限度地减少了开销。在许多并行计算机体系结构中，每个处理器都有一些它可以更有效地访问的存储器，因此希望任务不频繁地进行镜像。负载平衡是简单和分布式的：每当处理器访问其本地工作堆时，它执行与其工作堆大小成反比的概率的平衡操作。平衡操作由检查随机处理器的工作堆和交换任务组成，以便均衡两个工作堆的大小。对负载均衡方案性能的概率分析证明，系统中的每个任务都得到了公平的计算时间分配。具体地，每个本地任务队列的预期大小在平均值的小常数因子内，即系统中的任务总数除以处理器的数量。
A collection of local workpiles (task queues) and a simple load balancing scheme is well suited for scheduling tasks in shared memory parallel machines. Task scheduling on such machines has usually been done through a single, globally accessible, workpile. The scheme introduced in this paper achieves a balancing comparable to that of a global workpile, while minimizing the overheads. In many parallel computer architectures, each processor has some memory that it can access more efficiently, and so it is desirable that tasks do not mirgrate frequently. The load balancing is simple and distributed: Whenever a processor accesses its local workpile, it performs a balancing operation with probability inversely proportional to the size of its workpile. The balancing operation consists of examining the workpile of a random processor and exchanging tasks so as to equalize the size of the two workpiles. The probabilistic analysis of the performance of the load balancing scheme proves that each tasks in the system receives its fair share of computation time. Specifically, the expected size of each local task queue is within a small constant factor of the average, i.e. total number of tasks in the system divided by the number of processors.