Scheduler for vector processing operator allocation

• US 10,452,449 B1
• Filed: 05/10/2017
• Issued: 10/22/2019
• Est. Priority Date: 05/01/2017
• Status: Active Grant

• Current Assignee: Ambarella International LP (Ambarella Incorporated)
• Original Assignee: Ambarella Incorporated
• Inventors: Verplaetse, Peter
• Primary Examiner(s): Kessler, Gregory A
• Application Number:
  US15/591,352
• Time in Patent Office: 895 Days
• Field of Search: None
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 2209/5021 Priority
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: G06F 9/5044 considering hardware capabilities
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451

Abstract

An apparatus includes a plurality of hardware engines and a scheduler circuit. The hardware engines may be configured to process a plurality of vectors using a plurality of operators. The scheduler circuit may be configured to (i) parse a directed acyclic graph into one or more of the operators, (ii) track a plurality of unscheduled operators that have not been allocated to the hardware engines, (iii) track a plurality of statuses of the hardware engines and (iv) allocate at least one of the unscheduled operators to at least one of the hardware engines based on the statuses. The at least one unscheduled operator may be processed in the at least one hardware engine. The scheduler circuit may be implemented solely in hardware.

Claims

1. An apparatus comprising:

a plurality of hardware engines configured to process a plurality of vectors using a plurality of operators; and

a scheduler circuit configured to (i) parse a directed acyclic graph into one or more of said operators, (ii) track a plurality of first status signals indicating a readiness state of a plurality of unscheduled operators that have not been allocated to said hardware engines, (iii) track a plurality of second status signals indicating a readiness state of said hardware engines, and (iv) for each operator, track a resource type parameter, a priority parameter, and an offset parameter; and

an operator allocation circuit implemented solely in hardware and configured to (a) select a resource type from a list of resource types in use, (b) determine available hardware engines corresponding to the selected resource type based on the second status signals, (c) generate scores for the unscheduled operators based on (i) the selected resource type, (ii) the first status signals, (iii) the resource type parameters, (iv) the priority parameters, and (v) the offset parameters, and (d) allocate at least one of said unscheduled operators to at least one of said available hardware engines based on said scores.

2. The apparatus according to claim 1, wherein said directed acyclic graph defines a computer vision process.

3. The apparatus according to claim 1, wherein (i) said scheduler circuit is further configured to generate said list of resources in use by tracking a plurality of resource types corresponding to said operators and (ii) said resource types identify said hardware engines suitable to process said operators.

4. The apparatus according to claim 1, wherein said unscheduled operators are allocated to said available hardware engines based on highest score.

5. The apparatus according to claim 4, wherein said offset parameters are updated in response to allocation of said unscheduled operators to said available hardware engines.

6. The apparatus according to claim 5, wherein said unscheduled operators having similar priority are allocated to said hardware engines according to an arbitration scheme.

7. The apparatus according to claim 1, wherein said scheduler circuit is further configured to track a plurality of preemption thresholds corresponding to said operators.

8. The apparatus according to claim 7, wherein said scheduler circuit is further configured to preempt a scheduled operator being used in favor of a ready one of said unscheduled operators based on said preemption thresholds.

9. The apparatus according to claim 7, wherein said scheduler circuit is further configured to stall allocation of a ready one of said unscheduled operators while all of said hardware engines are busy processing based on said preemption thresholds.

10. The apparatus according to claim 1, wherein said hardware engines and said scheduler circuit are part of a computer vision system.

11. The apparatus according to claim 1, wherein said hardware engines and said scheduler circuit are part of a digital camera.

12. A method for allocating operators, comprising the steps of:

parsing a directed acyclic graph into one or more operators using a scheduler circuit comprising an operator allocation circuit implemented solely in hardware;

tracking a plurality of first status signals indicating a readiness state of a plurality of unscheduled operators that have not been allocated to a plurality of hardware engines;

tracking a plurality of second status signals indicating a readiness state of said hardware engines;

tracking a resource type parameter, a priority parameter, and an offset parameter for each operator;

utilizing said operator allocation circuit to (a) select a resource type from a list of resource types in use, (b) determine available hardware engines corresponding to the selected resource type based on the plurality of second status signals, (c) generate scores for the unscheduled operators based on (i) the selected resource type, (ii) the plurality of first status signals, (iii) the resource type parameters, (iv) the priority parameters, and (v) the offset parameters, and (d) allocate at least one of said unscheduled operators to at least one of said available hardware engines based on said scores; and

processing a plurality of vectors in said hardware engines using said operators.

13. The method according to claim 12, further comprising;

generating said list of resources in use by tracking a plurality of resource types corresponding to said operators, wherein said resource types identify said hardware engines suitable to process said operators.

14. The method according to claim 12, wherein said unscheduled operators are allocated to said available hardware engines based on highest score.

15. The method according to claim 13, further comprising:

updating said offset parameters in response to allocation of said unscheduled operators to said available hardware engines.

16. The method according to claim 15, wherein said unscheduled operators having similar priority are allocated to said hardware engines according to an arbitration scheme.

17. The method according to claim 12, further comprising:

tracking a plurality of preemption threshold parameters corresponding to said operators.

18. The method according to claim 17, further comprising:

preempting a scheduled operator being used in favor of a ready one of said unscheduled operators based on comparison of said preemption threshold parameters with a preemption priority value of said hardware engines.

19. The method according to claim 18, wherein said preemption threshold parameters comprise statically set values.

20. The method according to claim 18, wherein said unscheduled operators are allocated based on said preemption threshold parameter having a value greater than said preemption priority value.