Paper Info
Title
SALSA: scalable and low synchronization NUMA-aware algorithm for producer-consumer pools
Abstract
We present a highly-scalable non-blocking producer-consumer task pool, designed with a special emphasis on lightweight synchronization and data locality. The core building block of our pool is SALSA, Scalable And Low Synchronization Algorithm for a single-consumer container with task stealing support. Each consumer operates on its own SALSA container, stealing tasks from other containers if necessary. We implement an elegant self-tuning policy for task insertion, which does not push tasks to overloaded SALSA containers, thus decreasing the likelihood of stealing. SALSA manages large chunks of tasks, which improves locality and facilitates stealing. SALSA uses a novel approach for coordination among consumers, without strong atomic operations or memory barriers in the fast path. It invokes only two CAS operations during a chunk steal. Our evaluation demonstrates that a pool built using SALSA containers scales linearly with the number of threads and significantly outperforms other FIFO and non-FIFO alternatives.
Year
DOI
Venue
2012
10.1145/2312005.2312035
SPAA
Keywords
Field
DocType
cas operation,task insertion,overloaded salsa container,data locality,core building block,low synchronization numa-aware algorithm,single-consumer container,producer-consumer task pool,low synchronization algorithm,producer-consumer pool,salsa containers scales linearly,own salsa container,multi core,concurrent data structures
Synchronization,Locality,FIFO (computing and electronics),Computer science,Parallel computing,Concurrent data structure,Multi-core processor,SALSA,Fast path,Distributed computing,Scalability
Conference
Citations 
PageRank 
References 
4
0.39
21
Authors
4
Name
Order
Citations
PageRank
Elad Gidron140.39
Idit Keidar21892155.01
Dmitri Perelman31207.40
Yonathan Perez440.39