Lock-Free, Priority-Aware Work-Stealing Deque

Summary

We intend to build a lock-free, priority-aware work-stealing deque for dynamic task scheduling in parallel computing systems. Each worker thread maintains a priority deque and pushes/pops tasks locally, while stealing tasks from others based on priority. This is achieved using atomic operations (compare_exchange, fetch_add) in OpenMP and optionally MPI. We aim to benchmark the implementation on shared-memory (8–128 cores) and multi-node systems using MPI, testing throughput, steal attempts, and priority correctness.

Background

Work stealing allows idle threads to dynamically balance load by stealing tasks from others. Traditional deques are extended here with priority awareness. Atomic operations replace locks to avoid contention. This system supports fine-grained concurrency, priority-driven task selection, and hybrid OpenMP+MPI environments for full scalability. Benchmarking includes throughput, steal success rate, and accuracy of priority execution.

Pseudocode

while not done:
    task = pop_local_highest_priority_task()
    if task != NULL:
        execute(task)
    else:
        victim = random_other_thread()
        task = steal_lowest_priority_task_from(victim)
        if task != NULL:
            execute(task)
        else:
            spin_wait()

The Challenge

Each thread handles 1000 tasks with mixed priorities. After executing k tasks, it may steal from others. We compare two approaches:

• Thread-local deques: Efficient but synchronization overhead on status propagation.

Stealing with priorities can cause inversion if not carefully controlled. We explore ways to balance fairness, correctness, and efficiency under saturation and priority skew.

Resources

Our implementation will be in C/C++ and optionally MPI (distributed memory). We refer to literature on lock-free data structures and atomics, and consult documentation on std::atomic, __sync_*, and __atomic_* intrinsics. Testing is done on multi-core machines and GHC clusters.

Plan to Achieve

• Amogh + Akshay: Implement a deque with local push/pop and remote steal operations. Initially, the part of stealing the work, updating the queue, and processing elements is done sequentially.
• Akshay + Amogh: Introduce lock-free atomic building blocks (e.g., compare_exchange, fetch_add) to avoid synchronization locks across threads in stealing tasks from the deque.
• Compare different priority-handling approaches: separate deques by priority level vs. single-deque combination of priority tagging.
• Amogh + Akshay: Extend the deque to have n deques per processor, each storing tasks tagged with its priority. Operations should be lock-free, and task stealing should choose the best priority task available in that processor.
• Amogh + Akshay: Extend the stealing logic to choose from the queue populated with the best-priority tasks.
• Akshay: Measure the tradeoff between stealing 1 task vs. n tasks at once, analyzing time taken, synchronization overhead, communication time, and other relevant metrics.
• Amogh: Perform extensive benchmarking on performance characteristics such as task throughput, steal attempts, priority inversion, idle time, and scaling behavior.
• Amogh: Compare tradeoffs when tasks are re-stolen and analyze the resulting overhead and its effect on total execution time.
• Akshay: Benchmark results against a baseline with random (non-priority) stealing to evaluate the benefit of priority-based approaches.
• Nice to have: Amogh + Akshay: Implement batching logic where each processor, after executing n tasks, attempts to steal higher-priority tasks from random processors. Evaluate whether this improves high-priority task completion without harming low-priority tasks.
• Nice to have: Akshay + Amogh: Implement a distributed-memory version using MPI, where each process represents a node with local worker threads and simulates stealing across nodes via message passing.

Platform

x86-64 multi-core architecture C/C++ for implementation.

Rough Schedule

• Week 1: Setup, approach design finalise
• Week 2: Lock free implementation for the dequeue complete
• Week 3 (First Half): Extend implementation to handle n deques in a lock-free way with each deque having tasks of different priority.
• Week 3 (Second Half): Complete the implementation and task stealing logic of stealing the highest priority task from a random processor.
• Week 4 (First Half) (Nice to have): Implement logic where each processor, after performing n tasks, tries to steal higher-priority tasks from a random processor’s queues.
• Week 4 (Full): Benchmark all components, generate visualizations, and prepare the final report and poster-day materials. This runs in parallel with the nice-to-have goal, if possible.