DocumentCode :
3575037
Title :
Efficient Work-Stealing with Blocking Deques
Author :
Chi Liu ; Ping Song ; Yi Liu ; Qinfen Hao
Author_Institution :
Sino-German Joint Software Inst., Beihang Univ., Beijing, China
fYear :
2014
Firstpage :
149
Lastpage :
152
Abstract :
Work stealing is a popular and effective approach to implement load balancing in modern multi-/many-core systems, where each parallel thread has its local deque to maintain its own work-set of tasks and performs load balancing by stealing tasks from other deques. Unfortunately, the existing concurrent deques have two limitations. Firstly, these algorithms require memory fences in the owner´s critical path operations to ensure correctness, which is expensive in modern weak-memory architectures. Secondly, the concurrent deques are difficult to extend to support various flexible forms of task distribution strategies, which can be more sufficient to optimize computation in some special applications, such as steal-half strategy in solving large, irregular graph problems. This paper proposes a blocking work-stealing deque. We optimize work stealing task deques through effective ways of accessing the deques to decrease the synchronization overhead. These ways can reduce the frequency of races when different threads need to operate on the same deque, especially using massive threads. We present implementation of the algorithm as a C++ library and the experiment results show that it behaves well to Cilk plus on a series of benchmarks. Since our approach relies on blocking deques, it is easy to extend to support flexible task creation and distribution strategies and also reduces the memory fences impact on performance.
Keywords :
C++ language; multi-threading; resource allocation; software libraries; C++ library; Cilk plus; blocking work-stealing deque; load balancing; many-core systems; memory fences impact reduction; multicore systems; parallel thread; synchronization overhead; Algorithm design and analysis; Benchmark testing; Containers; Instruction sets; Processor scheduling; Synchronization; deque; load balancing; scheduling strategies; work stealing;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
High Performance Computing and Communications, 2014 IEEE 6th Intl Symp on Cyberspace Safety and Security, 2014 IEEE 11th Intl Conf on Embedded Software and Syst (HPCC,CSS,ICESS), 2014 IEEE Intl Conf on
Print_ISBN :
978-1-4799-6122-1
Type :
conf
DOI :
10.1109/HPCC.2014.28
Filename :
7056731
Link To Document :
بازگشت