DVS: Deterministic Victim Selection to ImprovePerformance in Work-Stealing Schedulers
Georgios Varisteas, Mats Brorsson · KTH Publication Database DiVA (KTH Royal Institute of Technology) · 2014
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.