Starvation free scheduling of prioritized workloads on the GPU

Patent metadata

Field	Value
Publication number	US-9747659-B2
Application number	US-201514851629-A
Country	US
Kind code	B2
Filing date	Sep 11, 2015
Priority date	Jun 7, 2015
Publication date	Aug 29, 2017
Grant date	Aug 29, 2017

Abstract

Embodiments are directed toward systems and methods for scheduling resources of a graphics processing unit that determine, for a number of applications having commands to be issued to the GPU, a static priority level and a dynamic priority level of each application, work iteratively across static priority levels until a resource budget of the GPU is consumed, and starting with a highest static priority identify the applications in a present static priority level, assign a processing budget of the GPU to each of the applications in the present static priority level according to their dynamic priority levels, and admit to a queue commands from the applications in the present static priority level according to their processing budgets, and release the queue to the GPU.

First claim

The invention claimed is:

1. A method for scheduling resources of a graphics processing unit (GPU), comprising:
determining, for a number of applications having commands to be issued to the GPU, a static priority level and a dynamic priority level of each application;
iteratively, working across static priority levels until a resource budget of the GPU is consumed, and starting with a highest static priority level:
identifying the applications in a present static priority level,
assigning a processing budget of the GPU to each of the applications in the present static priority level according to their dynamic priority levels, and
admitting to a queue commands from the applications in the present static priority level according to their processing budgets; and

releasing the queue to the GPU.

2. The method of claim 1 , wherein the method is performed by a central processing unit of a device in which the GPU is located.

3. The method of claim 1 , wherein the method is performed by a processing unit of a device in which the GPU is located that is different from the GPU.

4. The method of claim 1 , further comprising, when the GPU executes a command of a given application, revising the given application's dynamic priority level.

5. The method of claim 1 , further comprising, when a command of a given application is admitted to the queue, revising the given application's dynamic priority level.

6. The method of claim 1 , further comprising, after the admitting:
for a predetermined number of commands in queue, estimating a processing time for each of the commands,
estimating a processing budget for each of the predetermined number of commands, and
if an estimated processing time of a given command exceeds its processing budget, demoting the given command within the queue in favor of another command.

7. The method of claim 1 , further comprising, after the admitting:
estimating a processing time for a command currently being executed by the GPU,
estimating a processing budget for the command currently being executed, and
if the estimated processing time of the command currently being executed exceeds the processing budget of the command currently being executed, suspending execution of the command currently being executed in favor of another command.

8. A electronic device comprising:
a processing system, including a graphics processing unit (GPU) and a second processor; and
a memory storing one or more programs for execution by the processing system, the one or more programs including instructions for:
determining, for a number of applications having commands to be issued to the GPU, a static priority level and a dynamic priority level of each application;
iteratively, working across static priority levels until a resource budget of the GPU is consumed, and starting with a highest static priority:
identifying the applications in a present static priority level,
assigning a processing budget of the GPU to each of the applications in the present static priority level according to their dynamic priority levels, and
admitting to a queue commands from the applications in the present static priority level according to their processing budgets; and

releasing the queue to the GPU.

9. The electronic device of claim 8 , wherein the instructions are executed by the second processor, which is a central processing unit of the device.

10. The electronic device of claim 8 , wherein the one or more programs further include instructions for revising a given applications' dynamic priority level in response to the GPU executing a command of the given application.

11. The electronic device of claim 8 , wherein the one or more programs further include instructions for revising a given application's dynamic priority level in response to a command of the given application being admitted to the queue.

12. The electronic device of claim 8 , wherein the one or more programs further include instructions for, after the admitting:
for a predetermined number of commands in queue, estimating a processing time for each of the commands,
estimating a processing budget for each of the predetermined number of commands, and
if the estimated processing time of a given command exceeds its estimated processing budget, demoting the given command within the queue in favor of another command.

13. The electronic device of claim 8 , wherein the one or more programs further include instructions for, after the admitting:
estimating a processing time for a command currently being executed by the GPU,
estimating a processing budget for the command currently being executed, and
if the estimated processing time of the command currently being executed exceeds the estimated processing budget of the command currently being executed, suspending execution of the command currently being executed in favor of another command.

14. A system, comprising:
a graphics processing unit (GPU) operable to read commands from a queue data structure and to execute the commands read therefrom; and
a central processing unit (CPU) that, responsive to program instructions, maintains a queue of commands for execution by the GPU, the CPU admitting commands to the queue by:
determining, for a number of applications having commands to be issued to the GPU, a static priority level and a dynamic priority level of each application;
iteratively, working across static priority levels until a resource budget of the GPU is consumed, and starting with a highest static priority level:
identifying the applications in a present static priority level,
assigning a processing budget of the GPU to each of the applications in the present static priority level according to their dynamic priority levels, and
admitting to a queue commands from the applications in the present static priority level according to their processing budgets.

15. The system of claim 14 , wherein the CPU further is responsive to program instructions to reschedule commands in the queue by:
estimating a processing budget of each command in the queue;
determining, for each command within the queue, whether the command violates its processing budget; and
if the processing budget of a respective command is violated, demoting the violating command in favor of at least one other command in the queue.

16. The system of claim 14 , wherein the CPU further is responsive to program instructions to report the GPU performance by:
during each processing window of the GPU, identifying a command that violates its allotted resource budget;
storing information relating to the resource budget violation; and
periodically transmitting violation information to a graphics server.

17. The system of claim 14 , further comprising a memory system storing the queue.

18. A method for generating performance data, the method comprising:
during each processing window of a graphical processing unit (GPU), identifying, from a plurality of commands processed during the window, a command that violates its allotted resource budget;
storing information relating to the resource budget violation for the identified command; and
periodically transmitting violation information to a graphics server.

19. The method according to claim 18 , further comprising:
estimating a processing budget for each command in a graphical processing unit (GPU) queue;
determining, for each command within the queue, whether the command violates its processing budget; and
if the processing budget of a respective command is violated, demoting the violating comman

Assignees

• Apple Inc

Inventors

• Banerjee Kutty
• Sunalp Eric O
• Iwamoto Tatsuya

Classifications

• G06F9/505

  considering the load · CPC title

• G06F2209/5021

  Priority · CPC title

• G06T2200/28

  involving image processing hardware · CPC title

• G06F9/5044

  considering hardware capabilities · CPC title

• G06T1/20 Primary

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