Heterogeneous system on a chip scheduler

Patent metadata

Field	Value
Publication number	US-11704155-B2
Application number	US-202016917975-A
Country	US
Kind code	B2
Filing date	Jul 1, 2020
Priority date	Jul 1, 2020
Publication date	Jul 18, 2023
Grant date	Jul 18, 2023

Abstract

Described are techniques for scheduling tasks on a heterogeneous system on a chip (SoC). The techniques including receiving a directed acyclic graph at a meta pre-processor associated with a heterogeneous SoC and communicatively coupled to a scheduler, wherein the directed acyclic graph corresponds to a control flow graph of tasks associated with an application executed by the heterogeneous SoC. The techniques further including determining a rank for a respective task in the directed acyclic graph, wherein the rank is based on a priority of the respective task and a slack in the directed acyclic graph. The techniques further including providing the respective task to the scheduler for execution on the heterogeneous SoC according to the rank.

First claim

What is claimed is:

1. A computer-implemented method comprising:
receiving a directed acyclic graph at a meta pre-processor associated with a heterogeneous system on a chip (SoC) and communicatively coupled to a scheduler, wherein the directed acyclic graph corresponds to a control flow graph of tasks associated with an application executed by the heterogeneous SoC;
determining a rank for a respective task in the directed acyclic graph, wherein the rank is based on a priority of the respective task and a slack in the directed acyclic graph;
providing the respective task to the scheduler for execution on the heterogeneous SoC according to the rank;
executing, by the heterogenous SoC, the respective task according to the rank;
determining that respective priorities of additional tasks in the directed acyclic graph are non-critical;
determining that an updated slack in the directed acyclic graph is negative;
canceling the additional tasks in the directed acyclic graph; and
proceeding to a next directed acyclic graph.

2. The method of claim 1 , wherein determining the rank for the respective task further comprises:
determining a critical path in the directed acyclic graph;
determining a critical path time associated with the critical path;
determining a sub-deadline for the respective task;
determining the slack by subtracting a computational cost of the respective task from the sub-deadline; and
determining the rank by dividing the priority of the task by the slack.

3. The method of claim 2 , wherein the critical path comprises a longest execution path through the directed acyclic graph.

4. The method of claim 2 , wherein the computational cost is an average computational cost of the respective task.

5. The method of claim 1 , further comprising:
receiving heuristics associated with completed tasks from the scheduler;
determining an updated critical path in the directed acyclic graph and an updated critical path time; and
updating ranks for remaining tasks in the directed acyclic graph.

6. The method of claim 5 , wherein the heuristics include information regarding performance of respective processing elements.

7. The method of claim 1 , wherein determining the rank for the respective task in the directed acyclic graph further comprises:
determining a processing element of the heterogeneous SoC for executing the respective task; and
providing an indication of the processing element for executing the respective task to the scheduler.

8. The method of claim 7 , wherein the processing element is based on
time constraints associated with the directed acyclic graph and a processing speed of the processing element.

9. The computer-implemented method of claim 1 , wherein the method is performed by the heterogeneous SoC according to software that is downloaded to the heterogeneous SoC from a remote data processing system, wherein the method further comprises:
metering a usage of the software; and
generating an invoice based on metering the usage.

10. The method of claim 1 , wherein the rank is further based on traffic in the scheduler, dependencies in the directed acyclic graph, and application constraints.

11. The method of claim 1 , wherein providing the respective task to the scheduler for execution on the heterogeneous SoC according to the rank further comprises providing a plurality of tasks to the scheduler for execution on the heterogeneous SoC in an order according to a plurality of ranks associated with the plurality of tasks.

12. A system comprising:
one or more processors; and
one or more computer-readable storage media storing program instructions which, when executed by the one or more processors, are configured to cause the one or more processors to perform a method comprising:
receiving a directed acyclic graph at a meta pre-processor associated with a heterogeneous system on a chip (SoC) and communicatively coupled to a scheduler, wherein the directed acyclic graph corresponds to a control flow graph of tasks associated with an application executed by the heterogeneous SoC;
determining a rank for a respective task in the directed acyclic graph, wherein the rank is based on a priority of the respective task and a slack in the directed acyclic graph;
providing the respective task to the scheduler for execution on the heterogeneous SoC according to the rank;
executing, by the heterogenous SoC, the respective task according to the rank;
determining that respective priorities of additional tasks in the directed acyclic graph are non-critical;
determining that an updated slack in the directed acyclic graph is negative;
canceling the additional tasks in the directed acyclic graph; and
proceeding to a next directed acyclic graph.

13. The system of claim 12 , wherein the program instructions for determining the rank for the respective task include further program instructions configured to cause the one or more processors to perform the method further comprising:
determining a critical path in the directed acyclic graph;
determining a critical path time associated with the critical path;
determining a sub-deadline for the respective task;
determining the slack by subtracting a computational cost of the respective task from the sub-deadline; and
determining the rank by dividing the priority of the task by the slack.

14. The system of claim 12 , wherein the program instructions include further program instructions configured to cause the one or more processors to perform the method further comprising:
receiving heuristics associated with completed tasks from the scheduler;
determining an updated critical path in the directed acyclic graph and an updated critical path time; and
updating ranks for remaining tasks in the directed acyclic graph.

15. A computer program product comprising one or more computer readable storage media, and program instructions collectively stored on the one or more computer readable storage media, the program instructions comprising instructions configured to cause one or more processors to perform a method comprising:
receiving a directed acyclic graph at a meta pre-processor associated with a heterogeneous system on a chip (SoC) and communicatively coupled to a scheduler, wherein the directed acyclic graph corresponds to a control flow graph of tasks associated with an application executed by the heterogeneous SoC;
determining a rank for a respective task in the directed acyclic graph, wherein the rank is based on a priority of the respective task and a slack in the directed acyclic graph;
providing the respective task to the scheduler for execution on the heterogeneous SoC according to the rank;
executing, by the heterogenous SoC, the respective task according to the rank;
determining that respective priorities of additional tasks in the directed acyclic graph are non-critical;
determining that an updated slack in the directed acyclic graph is negative;
canceling the additional tasks in the directed acyclic graph; and
proceeding to a next directed acyclic graph.

16. The computer program product of claim 15 , wherein the program instructions for determining the rank for the respective task further comprise additional program instructions configured to cause the one or more processors to perform the method further comprising:
determining a critical path in the directed acyclic graph;
determining a critical path time associated with the critical path;
determining a sub-deadline for the respective task;
determining the slack by subtracting a computational cost of the respective task from the sub-deadl

Assignees

• IBM
• Int Business Machine Corporation

Inventors

• Vega Augusto
• Buyuktosunoglu Alper
• Franke Hubertus
• Wellman John-David
• Bose Pradip
• Senger Robert Matthew
• Amarnath Aporva

Classifications

• G06F9/4893 Primary

  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

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06Q20/145

  Payments according to the detected use or quantity · CPC title

• G06F2209/486

  Scheduler internals · CPC title

• G06F9/4887 Primary

  involving deadlines, e.g. rate based, periodic · CPC title