Work Stealing Algorithm in C++

Introduction

Task distribution becomes critical in the presence of multiple processors in parallel computing systems performances. The work-stealing algorithm is one effective load balancing approach suited to this environment. The work-stealing approach allows threads that have completed their tasks to 'steal' threads with unfinished tasks, thus maintaining a balanced system and reducing idle processors. It is now well adopted in framework that supports parallelism such as Intel's Threading Building Blocks (TBB) and ForkJoinPool in Java.

In this paper, we will first give a conceptual overview of the work-stealing algorithm and present a C++ code implementing it later on. In addition, work-stealing algorithms will be discussed with regard to their appropriate usage and constraints.

Problem Statement:

In a multi-threaded model, some threads would finish their portions earlier than others and thus, some of the resources would remain unused. This is where the issues of how to efficiently load balance across threads arise in such a way that there is no thread that is idle while other threads have work. Centralized queues are often used in traditional work distribution methods. This approach presents scalability issues as well due to queue bottlenecks that are likely to occur. The goal of the work-stealing algorithm is to create a distributed task queue system where idle threads can "steal" tasks from other threads' queues to maintain balance and improve overall efficiency.

Overview of the Work-Stealing Algorithm

The work-stealing algorithm operates by allowing each thread to have its own double-ended queue (deque) for storing tasks. The threads typically follow these rules:

1. Each thread operates primarily on its own deque, where it pushes and pops tasks in a last-in-first-out (LIFO) order.
2. If a thread completes its tasks and its deque is empty, it attempts to "steal" a task from another thread's deque.
3. Tasks are stolen from the bottom of the deque, allowing the victim thread to maintain its recent local tasks on top.
4. This approach minimizes contention as most accesses are to the thread's own deque.

This decentralized approach allows better scalability and avoids a single point of contention, as each thread manages its own task queue and only interacts with others when it's out of tasks.

Implementation in C++

Below is a simple C++ implementation of a work-stealing algorithm using a deque for each worker thread. This is a minimal example for illustration purposes and lacks some optimizations and error handling that would be necessary in a production environment.

Program 1:

Libraries Required

We will use the C++ Standard Library's thread support and containers for the implementation. You can compile this code with a C++11 or newer compiler.

Output:

Executing task 6 on thread 22639988467392
Executing task 2 on thread 22639988467392
Executing task 0 on thread 22639988467392
Executing task 4 on thread 22639988467392
Executing task 8 on thread 22639988467392
Executing task 1 on thread 22639988467392
Executing task 5 on thread 22639988467392
Executing task 9 on thread 22639988467392
Executing task 3 on thread 22639988467392
Executing task 7 on thread 22639986366144

Explanation of the Code

• Worker Class: Each worker has a deque for its tasks, a mutex to manage concurrent access, and a method to add tasks (push_task). Each worker can attempt to steal tasks from other workers if their deque is empty.
• Task Execution: Each worker runs in a loop, where it pops tasks from its deque and executes them. If no tasks are found, it attempts to steal tasks from other workers. The stop_flag is used to control when the worker should cease operation.
• Task Stealing: When a worker has no tasks in their deque, it iterates over other workers, attempting to steal a task from the bottom of their deque. If no tasks are available, it yields control briefly to reduce CPU load.
• Main function: The main function initializes the workers and starts a set of threads, each running a worker. It also distributes a few initial tasks among the workers. After a brief delay, all workers are stopped, and threads are joined.

Program 2:

Output:

Task 1 executed on thread 140491566859968
Task 4 executed on thread 140491556370112   

Explanation:

1. Task Class:
   • It encompasses dependency, and those dependencies include dependency relationships.
   • An atomic counter is used to keep track of dependencies and to ensure a safe and thread-competent decrement of such dependencies.
2. Worker Class:
   • They maintain a private local deque of tasks which they fetch as per the requirement.
   • The tasks are executed locally or in the absence of tasks, can even be snatched from the rest of the workers.
3. TaskScheduler Class:
   • Oversees the network of worker threads that are spread over the worker honey pot.
   • Keeps a watch on the tasks provided for submission and also resolves these in a on the fly manner.
4. Main Function:
   • Shows how the scheduler can be used through task graphs with dependencies and priorities assigned to them.
   • Tasks are not executed before their dependencies are cleared.

Advantages and Trade-offs

The work-stealing algorithm can nicely supplement threads because it allows for workload balancing and consequently, CPU utilization as well as IDLE time is increased.

• Lock Contention: Even if the algorithm allows for most of the deque accesses to be local, the algorithm does permit most of the accesses to die due to the need to leverage the task-stealing concept.
• Task Overhead: Switching tasks and stealing too much can cause a form of task overhead, which in turn makes work-stealing effectively not very practical for tasks that are very short-lasting or have no computation to carry out.

Conclusion

In conclusion, Work-stealing is an excellent method that can be applied in handling dynamic workloads in a multi-threaded application. It allows parts of work to be assigned out in distributed queues and idle threads to help threads that are working too much. It makes the solutions more resource-efficient and highly scalable. Even though the algorithm has its downsides, it has become trendy and is much more applicable in areas where diverse and adjustable tasks are required, therefore making it a highly utilized algorithm within the parallel computing space.