Name Task Queue Problem

Some applications can be broken down into variable length tasks to be executed concurrently. How do we efficiently load balance the tasks among processing elements in such applications? Context Many problems can be expressed as a set of tasks where the number of tasks is input-dependent. Tasks denote an independent unit of work that can be executed in parallel with other tasks. Some examples of such application include branch-and-bound algorithms (see Branch-and-Bound pattern) and graph traversal algorithms (see Graph Algorithms pattern). These applications have large amounts of tasks and large compute demands that we need to exploit for efficient parallel execution. In such applications, the number of tasks and sometimes the length of each task can vary dynamically. In order to effectively parallelize such applications and exploit concurrency, we must take care of issues that influence scalability. Good parallel scaling requires load balancing among the participating processors. Task queue is a well-known mechanism that is primarily designed to address the load imbalance problem [1]. Task Queue is defined as a mechanism to synchronously distribute a sequence of tasks among parallel threads of execution. The global problem is broken down into tasks and the tasks are enqueued onto the queue. Parallel threads of execution pull tasks from the queue and perform computations on th