Scheduling independent and dependent operations for processing

Patent metadata

Field	Value
Publication number	US-10339063-B2
Application number	US-201615213981-A
Country	US
Kind code	B2
Filing date	Jul 19, 2016
Priority date	Jul 19, 2016
Publication date	Jul 2, 2019
Grant date	Jul 2, 2019

Abstract

A processor includes an operations scheduler to schedule execution of operations at, for example, a set of execution units or a cache of the processor. The operations scheduler periodically adds sets of operations to a tracking array, and further identifies when an operation in the tracked set is blocked from execution scheduling in response to, for example, identifying that the operation is dependent on another operation that has not completed execution. The processor further includes a counter that is adjusted each time an operation in the tracking array is blocked from execution, and is reset each time an operation in the tracking array is executed. When the value of the counter exceeds a threshold, the operations scheduler prioritizes the remaining tracked operations for execution scheduling.

First claim

What is claimed is:

1. A method, comprising:
adding a first operation to a tracking array of a processor in response to the first operation being received for scheduling for execution at the processor and assigning the first operation a first age value;
adjusting the first age value in response to scheduling a second operation from the tracking array;
selecting the first operation for execution based on the first age value;
after selecting the first operation for execution, blocking the first operation from being issued to an execution unit responsive to identifying that the first operation is dependent on a third operation;
in response to blocking the first operation, resetting the first age value to an initial value and maintaining the first operation at the tracking array;
adjusting a value of a counter by a first adjustment in response to blocking the first operation from being scheduled for execution while the first operation is stored at the tracking array; and
in response to the value of the counter exceeding a threshold, suppressing scheduling of execution operations not stored the tracking array.

2. The method of claim 1 , further comprising resetting the counter in response to the first operation being scheduled for execution while the first operation is stored at the tracking array.

3. The method of claim 1 , wherein:
the value of the counter is adjusted by a second adjustment in response to an operation stored at the tracking array being scheduled for execution.

4. The method of claim 1 , wherein the first operation is an operation awaiting scheduling for execution at an execution unit of the processor.

5. The method of claim 1 , wherein the first operation is a memory access request awaiting scheduling for execution at a cache of the processor.

6. The method of claim 1 , wherein the adding includes adding a plurality of operations ready for scheduling for execution at the processor to the tracking array, the plurality of operations including the first operation.

7. A method, comprising:
adding to a tracking array a plurality of operations ready for scheduling for execution at a processor;
adjusting a first age value associated with a first operation of the plurality of operations in response to scheduling a second operation of the plurality of operations for execution at the processor;
selecting the first operation for execution based on the first age value;
after selecting the first operation for execution, blocking the first operation from execution in response to identifying that the first operation is dependent on a third operation;
in response to blocking the first operation, resetting the first age value to an initial value and maintaining the first operation at the tracking array;
adjusting a counter in response to the first operation of the plurality of operations being blocked for scheduling for execution while the first operation is stored at the tracking array; and
in response to the counter exceeding a threshold, prioritizing operations stored at the tracking array for execution at the processor.

8. The method of claim 7 , further comprising removing the first operation from the tracking array in response to the first operation being scheduled for execution at the processor.

9. The method of claim 8 , further comprising:
resetting the counter in response to the first operation being scheduled for execution at the processor.

10. The method of claim 8 , wherein:
the prioritizing comprises suppressing operations ready for scheduling and not stored at the tracking array from being scheduled for execution.

11. The method of claim 8 , wherein the second operation is stored at the tracking array.

12. A processor, comprising:
an operations scheduler configured to schedule operations for execution at the processor;
a tracking array configured to store a set of operations at the operations scheduler;
a counter configured to adjust a value by a first adjustment in response to a first operation stored at the tracking array being blocked from being scheduled for execution at the operations scheduler; and
wherein the operations scheduler is configured to:
adjust a first age value associated with the first operation in response to scheduling a second operation stored at the tracking array for execution;
select the first operation for execution based on the first age value;
after selecting the first operation for execution, block the first operation in response to identifying the first operation is dependent on a third operation;
in response to blocking the first operation, resetting the first age value to an initial age value and maintaining the first operation at the tracking array; and
in response to the value of the counter exceeding a threshold, prioritize operations stored at the tracking array for execution.

13. The processor of claim 12 , wherein the counter is configured to reset the value in response to the first operation being scheduled for execution while the first operation is stored at the tracking array.

14. The processor of claim 12 , wherein the counter is configured to adjust the value of the counter by a second adjustment in response to an operation stored at the tracking array being scheduled for execution.

15. The processor of claim 12 , wherein the first operation is an operation awaiting scheduling for execution at an execution unit of the processor.

16. The processor of claim 12 , wherein the first operation is a memory access request awaiting scheduling for execution at a cache of the processor.

17. The processor of claim 12 , wherein the set of operations comprises a set of operations concurrently ready for scheduling at the operations scheduler.

Assignees

• Advanced Micro Devices Inc

Inventors

• Moyer Paul James
• Born Richard Martin

Classifications

• G06F9/3836 Primary

  Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution · CPC title

• G06F2212/60

  Details of cache memory · CPC title

• G06F12/0877 Primary

  Cache access modes · CPC title

• G06F9/3855

  Physics · mapped topic

• G06F9/3814 Primary

  Implementation provisions of instruction buffers, e.g. prefetch buffer; banks · CPC title