Combining and Aggregating for Fast Synchronization
summary
Software implements fetch-and-add in software by splitting P threads across m aggregators (k ≈ P/m per aggregator), using per-aggregator AggSum and a global TotalSum with a combiner that applies batched partial sums and linearizes the whole batch at one hardware FAA. Experiments use a two-level design and show up to 4x throughput versus hardware FAA and 2.5x improvement when plugged into LCRQ. Overhead is ~2× in the uncontended case, supports positive/negative via dual aggregators, and is blocking (no fault tolerance).
AI-written summary · about
chapters (23)
- 0:00Introduction
- 0:48Talk overview
- 1:08Synchronization basics
- 3:19Cost of synchronization
- 4:26Shared memory model
- 5:29Software combining algorithms
- 8:04Limitations of combining
- 8:45Aggregating funnels technique
- 9:06Focus on fetch-and-add
- 12:21Fetch-and-add implementation
- 13:47Aggregating funnels overview
- 17:00Correctness in aggregating funnels
- 19:11Challenges in implementation
- 21:44Algorithm explanation
- 29:40Experimental results
- 31:30Related work
- 33:20Conclusion
- 35:54Future research
- 37:19Q&A
- 37:40Overheads in low contention
- 38:21Space overhead
- 40:08Adaptive schemes
- 41:32Final remarks
related talks
01h 02mIntro to Concurrent Programming 2/3: Modern Queues and Flat Combining
01h 05mFusing Efficient Parallel For Loops with a Composable Task Scheduler
39mThe best multicore-parallelization refactoring you've never heard of
48m“Is Parallel Programming still hard? PART 2 of 2”
01h 01mFrom Concurrent to Parallel
25mTackling Contention : The Monster in sync.Locker
01h 22mBeyond Sequential Consistency - Leveraging Atomics for Fun & Profit
58mTurbo Charge CPU Utilization in Fork/Join Using the ManagedBlocker