Title :
Stable Adaptive Work-Stealing for Concurrent Multi-core Runtime Systems
Author :
Cao, Yangjie ; Sun, Hongyang ; Qian, Depei ; Wu, Weiguo
Author_Institution :
Sch. of Electron. & Inf. Eng., Xi´´an Jiaotong Univ., Xi´´an, China
Abstract :
The proliferation of multi-core architectures has led to explosive development of parallel applications using programming models, such as OpenMP, TBB, and Cilk, etc. With increasing number of cores, however, it becomes harder to efficiently schedule parallel applications on these resources since current multi-core runtime systems still lack efficient 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 multi-core systems. To dynamically estimate the number of cores desired by each application, a stable feedback algorithm, called A-Deque, is proposed using the length of active deques, which more precisely captures the parallelism variation of the applications. Furthermore, a prototype system is built by extending the Cilk runtime system, and the experimental results show that feedback-driven scheduling algorithms have more advantages for scheduling parallel applications with dynamic changing parallelism, and better overall performances are achieved with more accurate and stable feedback mechanism. Compared with existing algorithms, A-Deque improves the performances by up to 19.13% and 28.96% with respect to average response time and processor utilization respectively.
Keywords :
adaptive systems; multiprocessing systems; parallel programming; scheduling; A-Deque algorithm; Cilk runtime system; collaborative scheduling; concurrent multicore runtime systems; dynamic changing parallelism; feedback-driven adaptive scheduling; multicore architectures; parallel applications; stable adaptive work-stealing; Adaptive scheduling; Multicore processing; Process control; Processor scheduling; Resource management; Runtime; Feedback-driven adaptive scheduling; Multi-core architectures; Multi-core runtime systems;
Conference_Titel :
High Performance Computing and Communications (HPCC), 2011 IEEE 13th International Conference on
Conference_Location :
Banff, AB
Print_ISBN :
978-1-4577-1564-8
Electronic_ISBN :
978-0-7695-4538-7
DOI :
10.1109/HPCC.2011.24