An adaptive task creation strategy for work-stealing scheduling

Lei Wang, Huimin Cui, Yuelu Duan, Fang Lu, Xiaobing Feng, Pen Chung Yew

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

26 Scopus citations

Abstract

Work-stealing is a key technique in many multi-threading programming languages to get good load balancing. The current work-stealing techniques have a high implementation overhead in some applications and require a large amount of memory space for data copying to assure correctness. They also cannot handle many application programs that have an unbalanced call tree or have no definitive working sets. In this paper, we propose a new adaptive task creation strategy, called AdaptiveTC, which supports effective work-stealing schemes and also handles the above mentioned problems effectively. As shown in some experimental results, AdaptiveTC runs 2.71x faster than Cilk and 1.72x faster than Tascell for the 16-queen problem with 8 threads.

Original languageEnglish (US)
Title of host publicationProceedings of the 2010 CGO - The 8th International Symposium on Code Generation and Optimization
Pages266-277
Number of pages12
DOIs
StatePublished - Jul 1 2010
Event8th International Symposium on Code Generation and Optimization, CGO 2010 - Toronto, ON, Canada
Duration: Apr 24 2010Apr 28 2010

Publication series

NameProceedings of the 2010 CGO - The 8th International Symposium on Code Generation and Optimization

Other

Other8th International Symposium on Code Generation and Optimization, CGO 2010
CountryCanada
CityToronto, ON
Period4/24/104/28/10

Keywords

  • adaptive
  • backtracking search
  • task granularity
  • work-stealing

Fingerprint Dive into the research topics of 'An adaptive task creation strategy for work-stealing scheduling'. Together they form a unique fingerprint.

Cite this