Task scheduling in a GPU

Patent metadata

Field	Value
Publication number	US-10318348-B2
Application number	US-201715713803-A
Country	US
Kind code	B2
Filing date	Sep 25, 2017
Priority date	Sep 23, 2016
Publication date	Jun 11, 2019
Grant date	Jun 11, 2019

Abstract

A method of scheduling tasks within a GPU or other highly parallel processing unit is described which is both age-aware and wakeup event driven. Tasks which are received are added to an age-based task queue. Wakeup event bits for task types, or combinations of task types and data groups, are set in response to completion of a task dependency and these wakeup event bits are used to select an oldest task from the queue that satisfies predefined criteria.

First claim

The invention claimed is:

1. A method of scheduling tasks in a task queue within a processor, the task queue comprising tasks having task type identifiers and associated state data identifying any task specific dependencies, the method comprising:
in response to receiving, at a task scheduling engine, an indication that a dependency for a task in the task queue has completed, updating the state data for the task that relates to the completed dependency to indicate that the dependency has completed and updating wakeup event state data of the processor to indicate a wakeup event for the task type identifier of the task;
identifying one or more candidate task types based on the wakeup event state data indicating a wakeup event;
selecting one of the candidate task types;
identifying an oldest non-executing task of the selected task type in the task queue; and
in response to determining that the identified task of the selected task type has all its dependencies met, selecting the task for execution.

2. The method according to claim 1 , wherein updating state data for the task that relates to the completed dependency comprises clearing a state bit for the task that relates to the completed dependency.

3. The method according to claim 1 , wherein updating wakeup event state data for the task type identifier of the task comprises setting a wakeup event state bit for a task type corresponding to the task type identifier of the task.

4. The method according to claim 1 , wherein a task has a both a task type identifier and a data group identifier,
wherein the wakeup event state data is updated for a combination of the task type corresponding to the task type identifier of the task and the data group corresponding to the data group identifier of the task,
and wherein identifying an oldest non-executing task of the selected task type in the task queue comprises:
identifying an oldest non-executing task in the task queue that is of the selected task type and has a task type identifier and data group identifier that correspond to wakeup event state data that has been updated.

5. The method according to claim 4 , wherein a wakeup event state bit is set for the combination of the task type corresponding to the task type identifier of the task and the data group corresponding to the data group identifier of the task and identifying an oldest non-executing task in the task queue that is of the selected task type and has a task type identifier and data group identifier that correspond to wakeup event state data that has been updated comprises:
identifying an oldest non-executing task in the task queue that is of the selected task type and has a task type identifier and data group identifier that correspond to a wakeup event state bit that has been set.

6. The method according to claim 4 , further comprising:
in response to determining that the identified task of the selected task type does not have all its dependencies met, clearing the wakeup event state data for the task type identifier and data group identifier of the identified task; and
identifying another oldest non-executing task in the task queue that is of the selected task type and has a task type identifier and data group identifier that correspond to wakeup event state data that has been updated.

7. The method according to claim 1 , further comprising:
in response to receiving a task at the task scheduling engine, adding the task to the task queue and setting state data for the task to identify any dependencies for the task.

8. The method according to claim 1 , further comprising:
in response to receiving, at the task scheduling engine, an indication that a task has completed execution, removing the task from the task queue.

9. The method according to claim 1 , further comprising:
in response to receiving, at the task scheduling engine, an indication that a task has completed execution, determining if the task is a first phase task of a multi-phase task;
in response to determining that the task is not a first phase task of a multi-phase task, removing the task from the task queue; and
in response to determining that the task is a first phase task of a multi-phase task, scheduling a second phase task of the multi-phase task.

10. The method according to claim 9 , wherein identifying an oldest non-executing task of the selected task type in the task queue further comprises prioritizing identification of a task that is a second phase task of a multi-phase task over tasks that are not second phase tasks.

11. A scheduler for a processor comprising:
a task scheduling engine;
a task queue comprising tasks having task type identifiers and associated state data identifying any task specific dependencies; and
a data store arranged to store wakeup state data, and wherein the task scheduling engine comprises:
a first hardware logic block arranged, in response to receiving an indication that a dependency for a task in the task queue has completed, to update the state data for the task that relates to the completed dependency to indicate that the dependency has completed by clearing the state data for the task and to update wakeup event state data of the processor to indicate a wakeup event for the task type identifier of the task;
a second hardware logic block arranged to identify one or more candidate task types based on the wakeup event state data indicating a wakeup event, to select one of the candidate task types, to identify an oldest non-executing task of the selected task type in the task queue and in response to determining that the identified task of the selected task type has all its dependencies met, to select the task for execution.

12. The scheduler according to claim 11 , wherein the wakeup state data comprises a plurality of wakeup state bits,
wherein the first hardware logic is arranged, in response to receiving an indication that a dependency for a task in the task queue has completed, to clear a state bit for the task that relates to the completed dependency and to update a wakeup event state bit for a task type corresponding to the task type identifier of the task,
and wherein the second hardware logic block arranged to identify one or more candidate task types based on the wakeup event state bits, to select one of the candidate task types, to identify an oldest non-executing task of the selected task type in the task queue and in response to determining that the identified task of the selected task type has all its dependencies met, to select the task for execution.

13. The scheduler according to claim 12 , wherein a task has a both a task type identifier and a data group identifier,
wherein the first logic block is arranged to set a wakeup event state bit for a combination of the task type corresponding to the task type identifier of the task and the data group corresponding to the data group identifier of the task,
and wherein the second logic block is arranged to identify the oldest non-executing task of the selected task type which has a task type identifier and data group identifier that correspond to a wakeup event state bit that has been updated.

14. The scheduler according to claim 13 , wherein the second logic block is further arranged, in response to determining that the identified task of the selected task type does not have all its dependencies met, to clear the wakeup event state bit for the task type identifier and data group identifier of the identified task and to identify another oldest non-executing task in the task queue that is of the selected task type and has a task type identifier and data group identifier that correspond to a wakeup ev

Assignees

• Imagination Tech Ltd

Inventors

• Nield Simon
• De Grasse Adam
• Iuliano Luca
• Mower Ollie
• Foo Yoong-Chert

Classifications

• G06F9/4893

  taking into account power or heat criteria (power management in computers in general G06F1/3203; thermal management in computers in general G06F1/206) · CPC title

• G06F2209/486

  Scheduler internals · CPC title

• G06F9/4881 Primary

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title

• G06T1/20

  Processor architectures; Processor configuration, e.g. pipelining · CPC title

• G06F2209/483

  Multiproc · CPC title