Out-of-order command execution with sliding windows to maintain completion statuses

Patent metadata

Field	Value
Publication number	US-10241799-B2
Application number	US-83760010-A
Country	US
Kind code	B2
Filing date	Jul 16, 2010
Priority date	Jul 16, 2010
Publication date	Mar 26, 2019
Grant date	Mar 26, 2019

Abstract

Techniques are described for reordering commands to improve the speed at which at least one command stream may execute. Prior to distributing commands in the at least one command stream to multiple pipelines, a multimedia processor analyzes any inter-pipeline dependencies and determines the current execution state of the pipelines. The processor may, based on this information, reorder the at least one command stream by prioritizing commands that lack any current dependencies and therefore may be executed immediately by the appropriate pipeline. Such out of order execution of commands in the at least one command stream may increase the throughput of the multimedia processor by increasing the rate at which the command stream is executed.

First claim

The invention claimed is:

1. A method comprising:
receiving at least one command stream comprising first, second, and third commands, and inter-command dependency information, wherein receiving the inter-command dependency information in the at least one command stream comprises receiving the inter-command dependency information before execution of the first, second, and third commands, wherein the first, second, and third commands in the at least one command stream are in addition to the inter-command dependency information in the at least one command stream, wherein the inter-command dependency information comprises a dependency list for the second command, wherein the dependency list for the second command references, via command count values, any commands in the at least one command stream upon which the second command depends, wherein each command count value represents a respective previous command in the at least one command stream upon which the second command depends, wherein the second and third commands have a first order in the at least one command stream such that the second command precedes the third command;
determining, based on the dependency list for the second command, that the second command depends upon prior execution of the first command;
determining that the first command is associated with a first one of a plurality of processing pipelines and that the second command and third commands are associated with a second, different one of the plurality of processing pipelines;
distributing, by a processor, the third command to the second one of the plurality of processing pipelines based on determining that the second command depends upon prior execution of the first command;
after distributing the third command to the second one of the plurality of processing pipelines, distributing, by the processor and based on determining that the second command depends upon prior execution of the first command, the second command to the second one of the plurality of processing pipelines such that the second command and third command execute in a second order that is different than the first order;
maintaining a first sliding window to represent completion statuses of commands associated with the first one of the plurality of processing pipelines; and
maintaining a second sliding window to represent completion statuses of commands associated with the second one of the plurality of processing pipelines,
wherein the at least one command stream comprises a first set of ordered commands associated with the first one of the plurality of processing pipelines and a second set of ordered commands associated with the second one of the plurality of processing pipelines, and
wherein the first sliding window comprises a command counter that represents a start location of the first sliding window, wherein the start location corresponds to a last command in the first set of ordered commands for which no preceding command remains unexecuted by the first one of the plurality of processing pipelines.

2. The method of claim 1 , wherein the first sliding window comprises an active window mask having a first bit that represents a completion status of the first command.

3. The method of claim 1 , further comprising generating, based on the dependency list for the second command, a dependency mask for the second command, wherein bits in the dependency mask indicate the completion statuses for corresponding commands in the first sliding window.

4. The method of claim 3 , wherein generating the dependency mask for the second command comprises:
determining a completion status of the first command; and
setting a given bit in the dependency mask for the second command when the first command has not been executed, wherein the given bit corresponds to the first command.

5. The method of claim 4 ,
wherein the first sliding window comprises an active window mask having a first bit that represents the completion status of the first command, and
wherein determining the completion status of the first command comprises evaluating the first bit of the active window mask.

6. The method of claim 3 , further comprising:
receiving a notification from the first one of the plurality of processing pipelines that the first command has been executed;
responsive to the notification, clearing a bit in the dependency mask for the second command, wherein the bit corresponds to the first command.

7. The method of claim 3 , further comprising:
receiving a notification from the first one of the plurality of processing pipelines that the first command completed; and
responsive to the notification, right-shifting the dependency mask by one bit when the first command corresponds to a least significant bit in the dependency mask.

8. The method of claim 3 , wherein distributing the second command to the first one of the plurality of processing pipelines comprises:
determining whether a bit in the dependency mask that corresponds to the first command is clear; and
distributing the second command to the first one of the plurality of processing pipelines only when the bit in the dependency mask that corresponds to the first command is clear.

9. The method of claim 1 , further comprising:
receiving a notification from the first one of the plurality of processing pipelines that the first command completed; and
responsive to the notification, advancing the first sliding window.

10. The method of claim 1 ,
wherein the at least one command stream further comprises a fourth command, wherein the inter-command dependency information comprises a dependency list for the fourth command, wherein the dependency list for the fourth command references, via command count values, any commands in the at least one command stream upon which the fourth command depends, wherein each command count value represents a respective previous command in the at least one command stream upon which the fourth command depends, wherein the second command has a priority value and the fourth command has a priority value, and wherein the method further comprises:
determining, based on the dependency list for the fourth command, that the fourth command depends upon prior execution of the first command;
determining that the fourth command is associated with the second one of the plurality of processing pipelines; and
distributing the second command and the fourth command to the second one of the plurality of processing pipelines in an order based on the priority values of the second command and the fourth command.

11. An apparatus comprising:
a command distribution and synchronization processor,
wherein the command distribution and synchronization processor is configured to:
receive at least one command stream comprising first, second, and third commands, and inter-command dependency information;
receive the inter-command dependency information in the at least one command stream before execution of the first, second, and third commands, wherein the first, second, and third commands in the at least one command stream are in addition to the inter-command dependency information in the at least one command stream, wherein the inter-command dependency information comprises a dependency list for the second command, wherein the dependency list for the second command references, via command count values, any commands in the at least one command stream upon which the second command depends, wherein each command count value represents a respective previous command in the at least one command stream, wherein the second and third commands have a first order in the at least one command stream such that the second command precedes the third command;
determine, based on t

Assignees

• Bourd Alexei V
• Jiao Guofang
• Qualcomm Inc

Inventors

• Bourd Alexei V
• Jiao Guofang

Classifications

• G06T1/20

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

• G06F9/3885

  using a plurality of independent parallel functional units · CPC title

• G06F9/3838 Primary

  Dependency mechanisms, e.g. register scoreboarding · CPC title