Stable Adaptive Work-Stealing for Concurrent Many-Core Runtime Systems

Yangjie CAO  Hongyang SUN  Depei QIAN  Weiguo WU  

IEICE TRANSACTIONS on Information and Systems   Vol.E95-D   No.5   pp.1407-1416
Publication Date: 2012/05/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E95.D.1407
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
many-core architectures,  many-core runtime systems,  feedback-driven adaptive scheduling,  

Full Text: PDF>>
Buy this Article

The proliferation of many-core architectures has led to the explosive development of parallel applications using programming models, such as OpenMP, TBB, and Cilk/Cilk++. With increasing number of cores, however, it becomes even harder to efficiently schedule parallel applications on these resources since current many-core runtime systems still lack effective mechanisms to support collaborative scheduling of these applications. In this paper, we study feedback-driven adaptive scheduling based on work stealing, which provides an efficient solution for concurrently executing a set of applications on many-core systems. To dynamically estimate the number of cores desired by each application, a stable feedback-driven adaptive algorithm, called SAWS, is proposed using active workers and the length of active deques, which well captures the runtime characteristics of the applications. Furthermore, a prototype system is built by extending the Cilk runtime system, and the experimental results, which are obtained on a Sun Fire server, show that SAWS has more advantages for scheduling concurrent parallel applications. Specifically, compared with existing algorithms A-Steal and WS-EQUI, SAWS improves the performances by up to 12.43% and 21.32% with respect to mean response time respectively, and 25.78% and 46.98% with respect to processor utilization, respectively.