Systems and methods for dynamic priority control

Patent metadata

Field	Value
Publication number	US-9146690-B2
Application number	US-201313750053-A
Country	US
Kind code	B2
Filing date	Jan 25, 2013
Priority date	Jan 27, 2012
Publication date	Sep 29, 2015
Grant date	Sep 29, 2015

Abstract

System and methods are provided for dynamically managing a first-in/first-out (FIFO) command queue of a system controller. One or more commands are received into the command queue, a command being associated with a priority parameter. A current command first in line to be executed in the command queue is determined, the current command being associated with a first priority parameter. A second command associated with a second priority parameter is determined, the second priority parameter being largest among priority parameters associated with the one or more commands. A final priority parameter for the current command is computed based at least in part on the second priority parameter.

First claim

What is claimed is:

1. A method for dynamically scheduling execution of a command from a first-in/first-out (FIFO) queue, the method comprising:
receiving a plurality of commands into the FIFO queue, each command of the plurality of commands respectively having a priority, wherein the plurality of commands include
a current command that corresponds to a command that is currently first in line in the FIFO queue to be executed,
a highest-priority command that is later in the FIFO queue than the current command and whose priority is the highest priority in the FIFO queue, and
at least one additional command;

determining a priority for the FIFO queue as an average of (i) the priority of the highest priority command and (ii) the priority of the current command; and
scheduling execution of the current command from the FIFO queue based on the priority of the FIFO queue.

2. The method of claim 1 , wherein the current command is followed by a second command in the FIFO queue, and wherein the method further comprises, subsequent to scheduling the execution of the current command from the FIFO queue:
executing the current command and removing the current command from the FIFO queue, resulting in the second command in the FIFO queue becoming the current command; and
in response to the executing and the removing, repeating the determining step with the second command as the current command.

3. The method of claim 1 , wherein the highest priority command is a first highest-priority command, and wherein the commands include a second highest-priority command that is later in the FIFO queue than the first highest-priority command and whose priority is the highest priority from among the commands that follow the first highest-priority command, and wherein the method further comprises, after the scheduling:
executing the first highest-priority command and removing the first highest-priority command from the FIFO queue, resulting in the priority of the second highest-priority command becoming the highest priority; and
repeating the determining step, resulting in a new queue priority that is lower than the previously determined queue priority.

4. The method of claim 1 , further comprising:
adding, to the FIFO queue, a new command that has a priority that is higher than said highest priority; and
repeating the determining step with the priority of the new command as the highest priority, resulting in an increase in the queue priority.

5. The method of claim 1 , wherein the method further comprises:
determining a wait time indicating an amount of time the highest priority command has been in the FIFO queue;
determining the queue priority as an average of (i) the priority of the highest priority command and (ii) the priority of the current command if the wait time does not exceed a threshold; and
determining the queue priority as equal to the priority of the highest priority command in the queue if the wait time does exceed the threshold.

6. The method of claim 1 , further comprising:
maintaining, for each command of the plurality of commands, a wait time indicating an amount of time the respective command has been in the FIFO queue;
wherein the determining of the queue priority is at least partially based on the wait time of one of the commands.

7. The method of claim 6 , wherein the determining of the queue priority is at least partially based on wait times of two or more of the commands.

8. The method of claim 6 , wherein the maintaining of the wait times is hardware implemented.

9. An integrated circuit for dynamically scheduling execution of a command from a first-in/first-out (FIFO) queue, the integrated circuit comprising:
a memory configured to receive a plurality of commands into the FIFO queue, each command of the plurality of commands respectively having a priority, wherein the plurality of commands include
a current command that corresponds to a command that is currently first in line in the FIFO queue to be executed,
a highest-priority command that is later in the FIFO queue than the current command and whose priority is the highest priority in the FIFO queue, and
at least one additional command;

an arbitrator configured to determine a priority for the FIFO queue as an average of (i) the priority of the highest priority command and (ii) the priority of the current command; and
a scheduler configured to schedule execution of the current command from the FIFO queue based on the priority of the FIFO queue.

10. The integrated circuit of claim 9 , wherein the current command is followed by a second command in the FIFO queue, and wherein the integrated circuit further comprises a processor configured to, subsequent to the scheduler scheduling the execution of the current command from the FIFO queue, execute the current command and remove the current command from the FIFO queue, resulting in the second command in the FIFO queue becoming the current command; and
wherein the arbitrator is further configured to, in response to the executing and the removing, repeat the determining with the second command as the current command.

11. The integrated circuit of claim 9 , wherein the highest priority command is a first highest-priority command, and wherein the commands include a second highest-priority command that is later in the FIFO queue than the first highest-priority command and whose priority is the highest priority from among the commands that follow the first highest-priority command, and
wherein the integrated circuit further comprises a processor configured to execute the first highest-priority command and remove the first highest-priority command from the FIFO queue, resulting in the priority of the second highest-priority command becoming the highest priority; and
wherein the arbitrator is further configured to repeat the determining, resulting in a new queue priority that is lower than the previously determined queue priority.

12. The integrated circuit of claim 9 , wherein the integrated circuit is configured to add, to the FIFO queue, a new command that has a priority that is higher than said highest priority; and
wherein the arbitrator is further configured to repeat the determining with the priority of the new command as the highest priority, resulting in an increase in the queue priority.

13. The integrated circuit of claim 9 , wherein the integrated circuit is configured to determine a wait time indicating an amount of time the highest priority command has been in the FIFO queue, and
the arbitrator is configured to
determine the queue priority as an average of (i) the highest priority of the highest priority command and (ii) the priority of the current command if the wait time does not exceed a threshold; and
determine the queue priority as equal to the priority of the highest priority command in the queue if the wait time does exceed the threshold.

14. The integrated circuit of claim 9 , wherein the integrated circuit is configured to maintain, for each command of the plurality of commands, a wait time indicating an amount of time the respective command has been in the FIFO queue; and
wherein the arbitrator is configured for the determining of the queue priority to be at least partially based on the wait time of one of the commands.

15. The integrated circuit of claim 14 , wherein the arbitrator is configured for the determining of the queue priority to be at least partially based on wait times of two or more of the commands.

16. The integrated circuit of claim 14 , wherein the maintaining of the wait times is hardware implemented.

Assignees

• Marvell World Trade Ltd

Inventors

• Zhu Jun
• Cao Joseph Jun
• Yang Tsung-Ju
• Lu Ruoyang

Classifications

• G06F3/0673

  Single storage device · CPC title

• G06F3/061

  Improving I/O performance · CPC title

• G06F13/1642 Primary

  with request queuing · CPC title

• G06F3/0659 Primary

  Command handling arrangements, e.g. command buffers, queues, command scheduling · CPC title