Queue management for task graphs
In accordance with the described techniques, a command processor processes a fiber graph that includes fibers each having one or more tasks and indicates dependencies between the fibers and between tasks within the fibers. As part of this, the command processor dispatches a task from a fiber for execution by a processing element array based on the fiber being enqueued in a ready queue and the dependencies of the task being resolved. While the task is dispatched and unexecuted by the processing element array, the command processor enqueues the fiber in a sleep queue. Further, the command processor enqueues the fiber in a check queue based on the one or more tasks of the fiber having been executed by the processing element array. Based on the fiber being in the check queue, the command processor enqueues a dependent fiber in the ready queue that depends from the fiber.
1 . An accelerator device, comprising:
a processing element array;
a memory configured to store a fiber graph that includes fibers each having one or more tasks, the fiber graph indicating dependencies between the fibers and between the tasks within the fibers; and
a command processor including a first thread that manages a ready queue and a second thread that manages a sleep queue and a check queue, the command processor configured to perform operations including:
dispatching a task from a fiber for execution by the processing element array based on the fiber being enqueued in the ready queue and the dependencies of the task being resolved;
enqueueing the fiber in the sleep queue while the task is dispatched and unexecuted by the processing element array;
enqueueing the fiber in the check queue based on the one or more tasks of the fiber having been executed by the processing element array; and
enqueuing a dependent fiber that depends from the fiber in the ready queue based on the fiber being enqueued in the check queue.
2 . The accelerator device of claim 1 , the operations further including dispatching an additional task from the dependent fiber based on the dependent fiber being enqueued in the ready queue and the dependencies of the additional task being resolved.
3 . The accelerator device of claim 1 , wherein an additional fiber is enqueued ahead of the fiber in the ready queue and the dependencies of an additional task in the additional fiber are resolved, the task being dispatched before the additional task based on the fiber being assigned a higher priority than the additional fiber.
4 . The accelerator device of claim 1 , wherein enqueuing the fiber in the check queue includes:
moving the fiber from the sleep queue to the ready queue responsive to receiving a completion signal indicating that the task has been executed by the processing element array;
dispatching an additional task from the fiber based on the fiber being in the ready queue and the dependencies of the additional task being resolved;
moving the fiber from the ready queue to the sleep queue while the additional task is dispatched and unexecuted by the processing element array;
moving the fiber from the sleep queue to the ready queue responsive to receiving an additional completion signal indicating that the additional task has been executed by the processing element array; and
moving the fiber from the ready queue to the check queue based on the one or more tasks of the fiber having been executed by the processing element array.
5 . The accelerator device of claim 4 , wherein an additional fiber is enqueued ahead of the fiber in the sleep queue, and moving the fiber to the ready queue includes waiting for a dispatched task of the additional fiber to be executed before processing the completion signal of the task.
6 . The accelerator device of claim 4 , wherein an additional fiber is enqueued ahead of the fiber in the sleep queue, and moving the fiber to the ready queue includes processing the completion signal of the task before a dispatched task of the additional fiber has been executed.
7 . The accelerator device of claim 1 , wherein enqueuing the dependent fiber in the ready queue includes:
retrieving the dependent fiber from the memory based on the dependent fiber being identified using the fiber graph; and
enqueueing the dependent fiber in the ready queue based on the dependent fiber having a resolved dependency on the one or more tasks of the fiber.
8 . The accelerator device of claim 1 , wherein management of the ready queue by the first thread and management of the sleep queue and the check queue by the second thread causes the ready queue, the sleep queue, and the check queue to be single-producer, single-consumer queues.
9 . The accelerator device of claim 1 , wherein dispatching the task includes selecting, in accordance with a load balancing policy, a processing element of the processing element array to which the task is to be dispatched, the load balancing policy indicating to balance workloads dispatched to each processing element of the processing element array.
10 . The accelerator device of claim 1 , wherein dispatching the task includes selecting, in accordance with a locality policy, a processing element of the processing element array to which the task is to be dispatched, the locality policy indicating to dispatch the one or more tasks of each respective fiber to a same respective processing element of the processing element array.
11 . The accelerator device of claim 1 , wherein enqueuing the fiber in the sleep queue includes:
placing the fiber in a sleep pool while the task is dispatched and unexecuted by the processing element array; and
enqueuing, by the processing element array and responsive to the task being executed, a wakeup command in the sleep queue that identifies the fiber.
12 . The accelerator device of claim 11 , wherein enqueuing the fiber in the check queue includes:
looking up the fiber in the sleep pool based on the wakeup command being enqueued in the sleep queue; and
retrieving the fiber from the sleep pool.
13 . The accelerator device of claim 1 , wherein the ready queue, the sleep queue, and the check queue are first-in-first-out queues.
14 . The accelerator device of claim 1 , wherein the first thread manages the ready queue by moving fibers from the ready queue to the sleep queue and the check queue, and the second thread manages the ready queue and the sleep queue by moving fibers from the ready queue and the sleep queue to the ready queue.
15 . A method, comprising:
receiving, by a command processor, a fiber including one or more tasks and dependencies between the one or more tasks, the command processor including a first thread that manages a ready queue and a second thread that manages a sleep queue;
dispatching, by the command processor, a task from the fiber for execution by a processing element array based on the fiber being enqueued in the ready queue and the dependencies of the task being resolved;
enqueueing, by the command processor, the fiber in the sleep queue while the task is dispatched and unexecuted by the processing element array;
enqueueing, by the command processor, the fiber in the ready queue based on receiving a completion signal indicating that the task has been executed by the processing element array; and
enqueueing, by the command processor, a dependent fiber that depends from the fiber in the ready queue based on the fiber being enqueued in the ready queue and the one or more tasks of the fiber having been executed by the processing element array.
16 . The method of claim 15 , wherein the fiber includes a set of operations instructing the command processor to process the fiber, and the dependent fiber is enqueued in the ready queue based on a wake fiber operation in the set of operations that identifies the dependent fiber.
17 . The method of claim 16 , wherein the wake fiber operation is placed within the set of operations after an operation to enqueue the fiber in the ready queue based on a final task of the fiber having been executed by the processing element array.
18 . A system, comprising:
an accelerator device that includes a command processor and a processing element array, the command processor including a first thread that manages a ready queue and a second thread that manages a check queue; and
a host configured to compile operations for executing a fiber graph that includes fibers each having one or more tasks, the fiber graph indicating dependencies between the fibers and between the tasks within the fibers, the operations instructing the command processor to:
dispatch a task from a fiber for execution by the processing element array based on the fiber being enqueued in the ready queue and the dependencies of the task being resolved;
push the fiber to a tail of the ready queue based on the task being dispatched and unexecuted by the processing element array;
enqueue the fiber in the check queue based on the fiber being enqueued in the ready queue and the one or more tasks of the fiber having been executed by the processing element array; and
enqueue a dependent fiber that depends from the fiber in the ready queue based on the fiber being enqueued in the check queue.
19 . The system of claim 18 , wherein the fiber includes a barrier representing the dependencies of the dependent fiber, and the command processor maintains a barrier table that includes a value representing a number of unresolved dependencies associated with the barrier.
20 . The system of claim 19 , wherein to enqueue the fiber in the check queue, the operations instruct the command processor to:
receive a completion signal indicating that the task has been executed by the processing element array;
enqueue the completion signal in a signal queue;
decrement the value associated with the barrier in the barrier table based on the completion signal being in the signal queue; and
enqueue the fiber in the check queue based on the value associated with the barrier being decremented to zero.