Title :
An empirical evaluation of work stealing with parallelism feedback
Author :
Agrawal, Kunal ; He, Yuxiong ; Leiserson, Charles E.
Author_Institution :
Massachusetts Institute of Technology
Abstract :
A-STEAL is a provably good adaptive work-stealing thread scheduler that provides parallelism feedback to a multiprocessor job scheduler. A-STEAL uses a simple multiplicative-increase, multiplicative-decrease algorithm to provide continual parallelism feedback to the job scheduler in the form of processor requests. Although jobs scheduled by A-STEAL can be shown theoretically to complete in near-optimal time asymptotically while utilizing at least a constant fraction of the allotted processors, the constants in the analysis leave it open on whether A-STEAL works well in practice. This paper confirms with simulation studies that A-STEAL performs well when scheduling adaptively parallel work-stealing jobs on large-scale multiprocessors. Our studies monitored the behavior of A-STEAL on a simulated multiprocessor system using synthetic workloads. We measured the completion time and waste of A-STEAL on over 2300 job runs using a variety of processor availability profiles. Linear-regression analysis indicates that ASTEAL provides almost perfect linear speedup. In addition, A-STEAL typically wasted less than 20% of the processor cycles allotted to the job. We compared A-STEAL with the ABP algorithm, an adaptive work-stealing thread scheduler developed by Arora, Blumofe, and Plaxton which does not employ parallelism feedback. On moderately to heavily loaded large machines with predetermined availability profiles, A-STEAL typically completed jobs more than twice as quickly, despite being allotted the same or fewer processors on every step, while wasting only 10% of the processor cycles wasted by ABP. We compared the utilization of A-STEAL and ABP when many jobs with varying characteristics are using the same multiprocessor. These experiments provide evidence that A-STEAL consistently provides higher utilization than ABP for a variety of job mixes.
Keywords :
Adaptive scheduling; Availability; Feedback; Large-scale systems; Monitoring; Multiprocessing systems; Processor scheduling; Scheduling algorithm; Time measurement; Yarn;
Conference_Titel :
Distributed Computing Systems, 2006. ICDCS 2006. 26th IEEE International Conference on
Conference_Location :
Lisboa, Portugal
Print_ISBN :
0-7695-2540-7
DOI :
10.1109/ICDCS.2006.14