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 MarDisplayed 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 20mTalk | Reciprocating Locks Main Conference | ||
14:20 20mTalk | 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 20mTalk | Fairer and More Scalable Reader-Writer Locks by Optimizing Queue Management Main Conference | ||
15:00 20mTalk | Publish on Ping: A Better Way to Publish Reservations in Memory Reclamation for Concurrent Data StructuresDistinguished Paper Award Main Conference |