A Lock-Free Work-Stealing Algorithm for Bulk Operations

This paper presents a specialized lock-free work-stealing queue designed for a master-worker framework in mixed-integer programming solvers that leverages restricted concurrency assumptions to support native bulk operations and achieve constant-latency push performance, significantly outperforming general-purpose implementations like C++ Taskflow in batch processing scenarios.

The Gist

Imagine you are running a massive, high-stakes construction project. You have a team of workers (the computer cores) and a foreman (the master thread). Their job is to build a complex structure by breaking it down into thousands of tiny tasks (like laying bricks or pouring concrete).

In a perfect world, every worker would have exactly the same amount of work. But in reality, some tasks are quick, and some take forever. This creates a problem: some workers finish early and sit idle, while others are drowning in work.

The Problem: The Old Way of Sharing Work

To fix this, computer scientists use a technique called "Work Stealing."
Think of it like a buffet. Each worker has their own private plate (a queue).

• The Owner: A worker puts new tasks they create onto the top of their plate.
• The Stealer: If a worker runs out of food, they look at their neighbor's plate and "steal" a few tasks from the bottom to keep working.

The Issue: Most existing systems are built like a chaotic, crowded cafeteria.

1. One at a time: If you need 100 tasks, you have to walk over, grab one, walk back, grab another, and repeat 100 times. This is slow and tiring.
2. Too many thieves: In general systems, anyone can steal from anyone at any time. This causes a traffic jam at the buffet counter (contention), where everyone is bumping into each other.
3. Fragile plates: Some plates are fixed size. If you get too much food, the plate breaks and you have to find a bigger one and move everything over (resizing), which wastes time.

The Solution: A Specialized "Bulk" Conveyor Belt

The authors of this paper built a brand new, specialized conveyor belt just for their specific type of construction project (solving complex math problems called Mixed-Integer Programming).

Here is how their new system works, using simple analogies:

1. The "Bulk" Delivery (Native Bulk Operations)

Instead of grabbing one brick at a time, imagine a worker creates a whole pallet of 100 bricks.

• Old Way: The worker has to carry one brick, drop it, go back, carry another.
• New Way: The worker slides the entire pallet onto the conveyor belt in one smooth motion.
• Result: The time it takes to deliver 100 bricks is almost the same as delivering 1. This is called constant latency. It doesn't matter how big the batch is; the speed stays the same.

2. The "Single Thief" Rule (One Owner, One Stealer)

In their specific project, there is only one foreman responsible for balancing the load.

• Old Way: Imagine 50 people trying to grab food from the same buffet line at once. It's a mess.
• New Way: Only the foreman is allowed to steal. He walks down the line, sees a worker with too much, and takes a big chunk.
• Result: Because there's only one thief, there's no fighting or traffic jams. The system doesn't need heavy locks or security guards (synchronization) to keep order. It's much faster and lighter.

3. The "Infinite" Conveyor (Unbounded Growth)

Sometimes, a single task explodes into hundreds of new tasks instantly.

• Old Way: The plate is too small. You have to stop, find a bigger plate, and carefully move every single item to the new one.
• New Way: The conveyor belt is made of magic links. It can grow infinitely long without ever needing to stop and reorganize. You just keep adding links.

The Results: Why It Matters

The authors tested their new conveyor belt against the standard ones used in big software libraries (like C++ Taskflow).

• Pushing Tasks: When they added huge batches of tasks, the old systems got slower and slower (like a traffic jam). The new system stayed fast and steady, no matter how big the batch was.
• Stealing Tasks: When the foreman needed to steal a large portion of work (say, 50% of a worker's plate), the old systems got very slow. The new system was stable and fast.
• The "Optimized" Trick: They found that if the worker wasn't busy, the foreman could steal even faster by skipping a step. This made the process 3 times faster in common situations.

The Bottom Line

This paper isn't about building a better tool for every job in the world. It's about building the perfect tool for a very specific, messy job.

By realizing that their specific problem only needed one foreman and bulk deliveries, they were able to throw away all the heavy, complicated rules that general systems need. The result is a system that is incredibly efficient for their specific type of math-solving, proving that sometimes, the best way to be fast is to stop trying to be a "one-size-fits-all" solution and just build exactly what you need.

Technical Summary

Here is a detailed technical summary of the paper "A Lock-Free Work-Stealing Algorithm for Bulk Operations."

1. Problem Statement

The paper addresses the inefficiencies of existing general-purpose lock-free work-stealing queues when applied to specialized parallel solvers, specifically those based on Decision Diagrams (DDs) for Mixed-Integer Programming (MIP).

• Context: Modern parallel runtimes (e.g., Cilk, Intel TBB, Taskflow) use work-stealing deques to balance loads. These typically assume multiple concurrent stealers and single-task operations.
• The Mismatch: The authors' solver operates in a Master-Worker framework where:
  1. Bulk Operations: New nodes are generated in large batches (hundreds at once), and the master steals large proportions of tasks, not single items. Existing queues simulate this via repeated single-task calls, incurring high overhead.
  2. Unbounded Growth: The workload generates massive numbers of nodes dynamically. Fixed-size arrays or resizing arrays (which require costly copying) are unsuitable.
  3. Restricted Concurrency: The architecture enforces a strict model with one owner (worker) and one stealer (master). General-purpose algorithms support multiple concurrent stealers, introducing unnecessary synchronization complexity and overhead for this specific use case.
  4. Irregular Workloads: Solver nodes have highly variable processing times, making efficient load balancing critical.

2. Methodology

The authors propose a new Lock-Free Work-Stealing Queue tailored to the Master-Worker model with the following design choices:

• Data Structure: A singly linked list with an atomic head pointer and an atomic size counter. Nodes are padded to prevent false sharing.
• API Operations:
  • push (Owner): Accepts a linked list of new nodes. It atomically links the end of the new batch to the current head and updates the head pointer. It uses release semantics for the head update and acquire-release for the size update to ensure memory ordering.
  • pop (Owner): Removes the head node, advances the head pointer, and decrements the size.
  • steal (Master):
    • Takes a proportion parameter (e.g., steal 50% of the queue).
    • Calculates a "cut point" based on the current size.
    • Traverses the list to find the cut point.
    • Consistency Check: Re-checks the size to ensure the queue hasn't been drained too rapidly by the owner during traversal.
    • Severing: Sets the next pointer of the cut node to null, detaching the suffix (the stolen portion) from the list.
    • Optimization: Includes a variant that skips the second traversal (to count stolen nodes) if it can be guaranteed the owner did not modify the queue during the steal.
• Correctness: The algorithm is proven to be linearizable and lock-free. The single-stealer constraint simplifies the proof, as the owner never rewires internal links, only prepends or shortens the prefix.

3. Key Contributions

1. Specialized Algorithm: Introduction of a lock-free queue designed specifically for bulk operations and a single-stealer concurrency model, eliminating the overhead of general-purpose designs.
2. Native Bulk Support: The queue natively supports pushing and stealing batches of tasks, avoiding the $O(N)$ overhead of $N$ individual operations.
3. Unbounded Growth: The linked-list implementation grows without bounds and without expensive resizing/copying operations.
4. Correctness Sketch: A formal argument demonstrating linearizability and lock-freedom under the restricted concurrency model.
5. Optimized Steal Variant: An optimization that reduces steal latency by up to 3x in scenarios where the owner is idle during the steal by avoiding a full tail traversal.

4. Experimental Results

The authors benchmarked their LF Queue against C++ Taskflow's Unbounded Queue (UB) and Bounded Queue (BD).

• Push Latency (Bulk):
  • LF Queue: Maintains constant latency (<500 ns) regardless of batch size (tested up to 1024 nodes).
  • Taskflow Queues: Latency increases sharply with batch size, reaching ~5000 ns for 1024 nodes due to repeated atomic operations and resizing.
• Steal Latency:
  • LF Queue: Stable latency (~40 µs) regardless of the proportion stolen.
  • Taskflow Queues: Latency grows linearly with the proportion stolen, exceeding 112 µs for 60% steals.
  • Optimization: The optimized steal variant reduced latency from ~38 µs to ~12.5 µs for 60% steals.
• Pop Latency: All implementations performed similarly (~213–216 ns).
• Scalability (DAG Workload):
  • A pseudo-workload simulating large-graph exploration (2.5M and 300M nodes) showed near-linear scalability (speedup) for all queues as thread count increased from 1 to 128.
  • Note: The authors note that in this uniform-cost DAG benchmark, queue overhead was not the bottleneck. They argue that in their actual solver (with irregular node processing times), the advantages of their bulk operations and simplified synchronization will be even more pronounced.

5. Significance

• Domain-Specific Optimization: The paper demonstrates that tailoring concurrency primitives to specific workload characteristics (bulk operations, single-stealer) yields significant performance gains over "one-size-fits-all" solutions.
• Efficiency in MIP Solvers: By reducing synchronization overhead and enabling efficient bulk task transfer, this algorithm directly addresses scalability bottlenecks in parallelizing Decision Diagram-based solvers for complex combinatorial problems.
• Practical Trade-offs: The work highlights that relaxing the "multiple concurrent stealers" assumption allows for simpler, faster algorithms that are better suited for centralized master-worker architectures common in optimization solvers.

In conclusion, the proposed algorithm offers a superior alternative for parallel solvers requiring bulk task management and centralized load balancing, achieving constant-latency bulk pushes and stable steal performance where state-of-the-art general-purpose libraries degrade.