A carregar...
Publicação
Efficient Synchronization-Light Work Stealing
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 1.13 MB | Adobe PDF |
Orientador(es)
Resumo(s)
Work Stealing (Ws) is a provably efficient scheduler of parallel computations. In WS each processor owns a deque that it uses as a call stack; when out of work, processors try to steal tasks from other processors' deques. Unfortunately, the concurrent nature of processors' deques entails expensive synchronization even when processors access their own deques. Recently, Rito and Paulino have found that the use of split deques allows to provably avoid most synchronization costs while keeping WS's asymptotically optimal expected runtime; in Low-Cost Work Stealing (LCWS) - the variant of WS introduced in their work - processors need not synchronization for most local accesses to their (split) deques. In this paper we assess the concrete efficiency gains of LCWS in practice. More concretely, we implemented LCWS in the Parlay library and show how it compares against Parlay's original work stealing algorithm on the execution of the benchmarks from the Problem-Based Benchmark Suite (PBBS). Experimental results show that our signal-based LCWS implementation obtains speedups with regard to WS for at least 65% of PBBS' benchmarks in three different computers.
Descrição
Funding Information: This work is supported by NOVA LINCS (UIDB/04516/2020) with the financial support of FCT.IP. Publisher Copyright: © 2023 Owner/Author.
Palavras-chave
load balancing runtime systems scheduling synchronization-light work stealing Software Theoretical Computer Science Hardware and Architecture
Contexto Educativo
Citação
Editora
ACM - Association for Computing Machinery