BWS: Balanced work stealing for time-sharing multicores

Xiaoning Ding, Kaibo Wang, Phillip B. Gibbons, Xiaodong Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

20 Scopus citations

Abstract

Running multithreaded programs in multicore systems has become a common practice for many application domains. Work stealing is a widely-adopted and effective approach for managing and scheduling the concurrent tasks of such programs. Existing work-stealing schedulers, however, are not effective when multiple applications time-share a single multicore-their management of steal-attempting threads often causes unbalanced system effects that hurt both workload throughput and fairness. In this paper, we present BWS (Balanced Work Stealing), a work-stealing scheduler for time-sharing multicore systems that leverages new, lightweight operating system support. BWS improves system throughput and fairness via two means. First, it monitors and controls the number of awake, steal-attempting threads for each application, so as to balance the costs (resources consumed in steal attempts) and benefits (available tasks get promptly stolen) of such threads. Second, a steal-attempting thread can yield its core directly to a peer thread with an unfinished task, so as to retain the core for that application and put it to better use. We have implemented a prototype of BWS based on Cilk++, a state-of-the-art work-stealing scheduler. Our performance evaluation with various sets of concurrent applications demonstrates the advantages of BWS over Cilk++, with average system throughput increased by 12.5% and average unfairness decreased from 124% to 20%.

Original languageEnglish (US)
Title of host publicationEuroSys'12 - Proceedings of the EuroSys 2012 Conference
Pages365-378
Number of pages14
DOIs
StatePublished - May 9 2012
Externally publishedYes
Event7th ACM European Conference on ComputerSystems, EuroSys'12 - Bern, Switzerland
Duration: Apr 10 2012Apr 13 2012

Publication series

NameEuroSys'12 - Proceedings of the EuroSys 2012 Conference

Other

Other7th ACM European Conference on ComputerSystems, EuroSys'12
CountrySwitzerland
CityBern
Period4/10/124/13/12

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Hardware and Architecture
  • Electrical and Electronic Engineering

Keywords

  • Fairness
  • Multicore
  • Time sharing
  • Work stealing

Fingerprint Dive into the research topics of 'BWS: Balanced work stealing for time-sharing multicores'. Together they form a unique fingerprint.

Cite this