TY - GEN
T1 - Stable adaptive work-stealing for concurrent multi-core runtime systems
AU - Cao, Yangjie
AU - Sun, Hongyang
AU - Qian, Depei
AU - Wu, Weiguo
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
KW - Feedback-driven adaptive scheduling
KW - Multi-core architectures
KW - Multi-core runtime systems
UR - https://www.scopus.com/pages/publications/81555221719
U2 - 10.1109/HPCC.2011.24
DO - 10.1109/HPCC.2011.24
M3 - 会议稿件
AN - SCOPUS:81555221719
SN - 9780769545387
T3 - Proc.- 2011 IEEE International Conference on HPCC 2011 - 2011 IEEE International Workshop on FTDCS 2011 -Workshops of the 2011 Int. Conf. on UIC 2011- Workshops of the 2011 Int. Conf. ATC 2011
SP - 108
EP - 115
BT - Proc.- 2011 IEEE International Conference on HPCC 2011 - 2011 IEEE International Workshop on FTDCS 2011 - Workshops of the 2011 Int. Conf. on UIC 2011- Workshops of the 2011 Int. Conf. ATC 2011
T2 - 13th IEEE International Workshop on FTDCS 2011, the 8th International Conference on ATC 2011, the 8th International Conference on UIC 2011 and the 13th IEEE International Conference on HPCC 2011
Y2 - 2 September 2011 through 4 September 2011
ER -