Granted Patent B2

US 8,904,150 · App. 13/116,325 · Granted Dec 2, 2014

Abstract

Claims (51)

1. A processor, comprising:

an instruction unit which provides instructions for execution by the processor;

a decode/issue unit which decodes instructions received from the instruction unit and issues the instructions;

a plurality of execution queues coupled to the decode/issue unit, wherein each issued instruction from the decode/issue unit is stored into an entry of at least one queue of the plurality of execution queues, and wherein each entry of the plurality of execution queues is configured to store an issued instruction and a duplicate indicator corresponding to the issued instruction which indicates whether or not a duplicate instruction of the issued instruction is also stored in an entry of another queue of the plurality of execution queues.

2. The processor of claim 1 , wherein each entry of the plurality of execution queues is configured to store a dependency indicator corresponding to the issued instruction of the entry which indicates whether or not an issued instruction of an immediately subsequent entry of a same queue of the plurality of execution queues includes a dependency on the issued instruction of the entry.

3. The processor of claim 1 , wherein the duplicate indicator corresponding to the issued instruction indicates how many duplicate instructions of the issued instruction are stored in other queues of the plurality of queues.

4. The processor of claim 1 , wherein the decode/issue unit, in response to receiving a first instruction from the instruction unit, decodes the first instruction to determine operands of the first instruction, wherein when the decode/issue unit determines that the first instruction include a dependency on a second instruction already present in a first queue of the plurality of execution queues and include a dependency on a third instruction already present in a second queue of the plurality of execution queues:

the first instruction is stored in a first entry of the first queue and a duplicate indicator of the first entry of the first queue is set to indicate that the first instruction is also stored in another execution queue of the plurality of execution queues, and

the first instruction is also stored in a first entry of the second queue and a duplicate indicator of the first entry of the second selected queue is set to indicate that the second instruction is also stored in another execution queue of the plurality of execution queues.

5. The processor of claim 4 , wherein the decode/issue unit, in response to receiving a fourth instruction from the instruction unit, decodes the fourth instruction and determines that the fourth instruction include a dependency on the first instruction:

the fourth instruction is stored in a second entry of the first queue and to a second entry of the second queue,

a dependency indicator of the first entry of the first queue is set to indicate that the fourth instruction stored in the second entry of the first queue, which is immediately subsequent to the first entry of the first queue, is dependent upon the first instruction stored in the first entry of the first queue; and

a dependency indicator of the first entry of the second queue is set to indicate that the fourth instruction stored in the second entry of the second queue, which is immediately subsequent to the first entry of the second queue, is dependent upon the first instruction stored in the first entry of the second queue.

6. The processor of claim 1 , further comprising:

duplicate control circuitry coupled to each queue of the plurality of execution queues, wherein when a first instruction located in a bottom entry of a first queue of the plurality of execution queues has a duplicate indicator which indicates that the first instruction located in the bottom entry of the first queue is also stored in a second queue of the plurality of execution queues, the duplicate control circuitry of the second queue modifies a duplicate indicator of the first instruction stored in the second queue.

7. The processor of claim 6 , wherein the duplicate control circuitry of the first queue sends a signal based on the duplicate indicator of the first instruction located in the bottom entry of the first queue to the duplicate control circuitry of the second queue, and the duplicate control circuitry of the second queue performs the modification based on the received signal.

8. The processor of claim 6 , wherein when there is no collision present with the first instruction in the bottom entry of the first queue, the duplicate control circuitry of the first queue invalidates the first instruction located in the bottom entry of the first queue.

9. The processor of claim 6 , wherein when a dependency indicator of the first instruction in the first queue indicates that an immediately subsequent entry of the first queue has a second instruction which is dependent on the first instruction and no collision is present with the first instruction in the bottom entry of the queue, the duplicate control circuitry of the first queue invalidates the first instruction located in the bottom entry of the first queue and invalidates the second instruction in the immediately subsequent entry of the first queue.

10. The processor of claim 6 , wherein when the first instruction is located in the bottom entry of the first queue and has a duplicate indicator which indicates that the first instruction located in the bottom entry of the first queue is also stored in the second queue of the plurality of execution queues and the first instruction is located in a bottom entry of the second queue, the duplicate control circuitry of the first queue invalidates the first instruction located in the bottom entry of the first queue if the second queue is a higher-order execution queue than the first queue.

11. The processor of claim 1 , further comprising:

an execution unit; and

an arbiter coupled to each of the plurality of execution queues and to the execution unit, wherein the execution unit executes instructions of a first instruction type, wherein the arbiter selects a first instruction of the first instruction type from a bottom entry of a selected queue of the plurality of execution queues for execution by the execution unit, wherein a duplicate indicator of the bottom entry of any selected queue indicates that the first instruction is not stored in any other queue of the plurality of execution queues.

12. In a processor having an instruction unit, a decode/issue unit, and a plurality of execution queues, a method comprising:

receiving a first instruction;

decoding the first instruction by a decode/issue unit to determine operands of the first instruction;

determining that the first instruction include a dependency on a second instruction stored in a first queue of the plurality of execution queues and on a third instruction stored in a second queue of the plurality of execution queues;

storing the first instruction in a first entry of the first queue;

storing a first duplicate indicator in the first entry of the first queue to indicate that a duplicate instruction of the first instruction is stored in another queue of the plurality of execution queues;

storing the first instruction in a first entry of the second queue; and

storing a second duplicate indicator in the first entry of the second queue to indicate that a duplicate instruction of the second instruction is stored in another queue of the plurality of execution queues.

13. The method of claim 12 , further comprising:

receiving a fourth instruction;

decoding the fourth instruction by the decode/issue unit to determine at least one operand of the fourth instruction;

determining that the fourth instruction includes a dependency on the first instruction;

storing the fourth instruction in a second entry of the first queue;

storing the fourth instruction in a second entry of the second queue;

storing a first dependency indicator in the first entry of the first queue to indicate that the fourth instruction stored in the second entry of the first queue, which is immediately subsequent to the first entry of the first queue, is dependent upon the first instruction stored in the first entry of the first queue; and

storing a second dependency indicator in the first entry of the second queue to indicate that the fourth instruction stored in the second entry of the second queue, which is immediately subsequent to the first entry of the second queue, is dependent upon the first instruction stored in the first entry of the second queue.

14. The method of claim 12 , wherein the step of determining further comprises determining that the first instruction include a dependency on a fourth instruction stored in a third queue of the plurality of execution queues, wherein the method further comprises:

storing the first instruction in a first entry of the third queue; and

storing a third duplicate indicator in the first entry of the third queue to indicate that a duplicate instruction of the first instruction is stored in another queue of the plurality of execution queues, wherein each of the first duplicate indicator, second duplicate indicator, and third duplicate indicator indicate how many duplicate instructions of the first instruction are stored in other queues of the plurality of execution queues.

15. The method of claim 14 , wherein each of the first, second, and third duplicate indicators have a different value.

16. A processor, comprising:

an instruction unit which provides instructions for execution by the processor;

a decode/issue unit which decodes instructions received from the instruction unit and issues the instructions; and

a plurality of execution queues coupled to the decode/issue unit, wherein each instruction issued from the decode/issue unit is stored into an entry of at least one queue of the plurality of execution queues, wherein each of the plurality of execution queues comprises:

duplicate control circuitry, wherein when a first instruction located in a bottom entry of a first queue of the plurality of execution queues has a corresponding duplicate indicator which indicates that the first instruction located in the bottom entry of the first queue is also stored in another queue of the plurality of execution queues, the duplicate control circuitry of the first queue sends a signal based on the corresponding duplicate indicator to the duplicate control circuitries of the other queues of the plurality of execution queues.

17. The processor of claim 16 , wherein the duplicate control circuitry of the first queue receives signals from duplicate control circuitries of the other queues of the plurality of execution queues based on duplicate indicators corresponding to instructions in bottom entries of the other queues, and based on the received signals, the duplicate control circuitry of the first queue modifies any duplicate indicators corresponding to any duplicate instruction stored in the first queue which is a duplicate of an instruction stored in any of the bottom entries of the other queues.

18. The processor of claim 16 , wherein when a duplicate instruction of the first instruction located in the bottom entry of the first queue is not present in any bottom entries of any of the other queues of the plurality of execution queues, the duplicate control circuitry of the first queue invalidates the first instruction located in the bottom entry of the first queue.

19. The processor of claim 16 , wherein when a dependency indicator of the first instruction in the first queue indicates that an immediately subsequent entry to the bottom entry of the first queue has a second instruction which is dependent on the first instruction and a duplicate instruction of the first instruction located in the bottom entry of the first queue is not present in any bottom entries of any of the other queues of the plurality of queues, the duplicate control circuitry of the first queue invalidates the first instruction located in the bottom entry of the first queue and the second instruction located in the immediately subsequent entry to the bottom entry.

20. The processor of claim 16 , wherein when the first instruction located in the bottom entry of the first queue is also stored in a bottom entry of a second queue of the plurality of execution queues, the duplicate control circuitry of the first queue invalidates the first instruction in the bottom entry of the first queue if the second queue is a higher-order execution queue than the first queue.

Assignments (23)