A simple load balancing scheme for task allocation in parallel machines

摘要: 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 on such machines has usually been done through single, globally accessible, workpile. The introduced this paper achieves comparable to that global workpile, while minimizing the overheads. In many computer architectures, each processor some it can access more efficiently, so desirable do not mirgrate frequently. distributed: Whenever accesses its performs operation with probability inversely proportional size consists examining workpile random exchanging as equalize two workpiles. probabilistic analysis performance proves system receives fair share computation time. Specifically, expected task queue within small constant factor average, i.e. total number divided by processors.