DVS: Deterministic Victim Selection to ImprovePerformance in Work-Stealing Schedulers
2014 (English)Conference paper (Refereed)
Task-centric programming models offer a versatile method for exposing parallelism. Such programs are popularly deployed using work-stealing scheduling runtimes. Work-stealers have traditionally employed randomness dependent techniques, considered optimal for several execution configurations. We have identified certain inefficiencies and leeway for improvement on emerging parallel architectures and workloads of fluctuating parallelism. Our deterministic victim selection (DVS) for work-stealing schedulers was designed to provide controllable and predictable uniform distribution of tasks without degrading performance; stealing is restricted between specific pairs of workers. We experimentally show that DVS offers improved scalability and performance for irregular workloads. We demonstrate DVS on Linux and Barrelfish operating systems, using an 48 core Opteron system and a simulated ideal platform respectively. On real hardware, we observed better scaling and 13% average performance gains, up to 55% for specific irregular workloads.
Place, publisher, year, edition, pages
Research subject SRA - ICT
IdentifiersURN: urn:nbn:se:kth:diva-128183OAI: oai:DiVA.org:kth-128183DiVA: diva2:647136
MULTIPROG 2014: Programmability Issues for Heterogeneous Multicores
QC 201404032013-09-102013-09-102014-04-03Bibliographically approved