Many concurrent algorithms require processes to perform fetch-and-add operations on a single memory location, which can be a hot spot of contention. We present a novel algorithm called \emph{Aggregating Funnels} that reduces this contention by spreading the fetch-and-add operations across multiple memory locations. It aggregates fetch-and-add operations into batches so that the batch can be performed by a single hardware fetch-and-add instruction on one location and all operations in the batch can efficiently compute their results by performing a fetch-and-add instruction on a \emph{different} location. We show experimentally that this approach achieves higher throughput than previous combining techniques, such as Combining Funnels, and is substantially more scalable than applying hardware fetch-and-add instructions on a single memory location. We show that replacing the fetch-and-add instructions in the fastest state-of-the-art concurrent queue by our Aggregating Funnels eliminates a bottleneck and greatly improves the queue’s overall throughput.

Mon 3 Mar

Displayed time zone: Pacific Time (US & Canada) change

14:00 - 15:20
Session 3: Concurrent Data Structures and Synchronization I (Session Chair: Yuanhao Wei)Main Conference at Acacia D
14:00
20m
Talk
Reciprocating Locks
Main Conference
Dave Dice Oracle Labs, Alex Kogan Oracle Labs, USA
14:20
20m
Talk
Aggregating Funnels for Faster Fetch&Add and Queues
Main Conference
Younghun Roh MIT, Yuanhao Wei University of British Columbia, Eric Ruppert York University, Panagiota Fatourou FORTH ICS and University of Crete, Greece, Siddhartha Jayanti Google Research, Julian Shun MIT
14:40
20m
Talk
Fairer and More Scalable Reader-Writer Locks by Optimizing Queue Management
Main Conference
Takashi Hoshino Cybozu Labs, Inc., Kenjiro Taura The University of Tokyo
15:00
20m
Talk
Publish on Ping: A Better Way to Publish Reservations in Memory Reclamation for Concurrent Data StructuresDistinguished Paper Award
Main Conference
Ajay Singh FORTH ICS and University of Waterloo, Trevor Brown University of Toronto