Double-Width Instruction Queue for Instruction Execution

• US 20070288734A1
• Filed: 06/08/2006
• Published: 12/13/2007
• Est. Priority Date: 06/08/2006
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Luick, David A.
• Application Number:
  US11/422,930
• Publication Number:
  US 20070288734A1
• Time in Patent Office: Days
• US Class Current: 712/237
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 9/30021 Compare instructions, e.g. Greater-Than, Equal-To, MINMAX
• CPC Class Codes: G06F 9/30101 Special purpose registers
• CPC Class Codes: G06F 9/3804 for branches, e.g. hedging, branch folding
• CPC Class Codes: G06F 9/3812 with instruction modification, e.g. store into instruction stream
• CPC Class Codes: G06F 9/3814 Implementation provisions of instruction buffers, e.g. prefetch buffer; banks
• CPC Class Codes: G06F 9/382 Pipelined decoding, e.g. using predecoding
• CPC Class Codes: G06F 9/3824 Operand accessing
• CPC Class Codes: G06F 9/3828 with global bypass, e.g. between pipelines, between clusters
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/3846 using static prediction, e.g. branch taken strategy
• CPC Class Codes: G06F 9/3848 using hybrid branch prediction, e.g. selection between prediction techniques
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/3853 of compound instructions
• CPC Class Codes: G06F 9/3869 Implementation aspects, e.g. pipeline latches; pipeline synchronisation and clocking
• CPC Class Codes: G06F 9/3889 controlled by multiple instructions, e.g. MIMD, decoupled access or execute
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A method and apparatus for executing branch instructions is provided. In one embodiment, the method includes receiving a branch instruction, issuing instructions for a first path of the branch instruction to a first queue of a dual instruction queue, and issuing instructions for a second path of the branch instruction to a second queue of a dual instruction queue. The method further includes determining if the branch instruction follows the first path or the second path. Upon determining that the branch instruction follows the first path, the instructions for the first path are provided from the first queue are provided to a first execution unit. Upon determining that the branch instruction follows the second path, instructions for the second path are provided from the second queue to the first execution unit.

Claims

1. A method of executing instructions, the method comprising:

receiving a branch instruction;

issuing instructions for a first path of the branch instruction to a first queue of a dual instruction queue;

issuing instructions for a second path of the branch instruction to a second queue of a dual instruction queue;

determining if the branch instruction follows the first path or the second path;

upon determining that the branch instruction follows the first path, providing instructions for the first path from the first queue to a first execution unit; and

upon determining that the branch instruction follows the second path, providing instructions for the second path from the second queue to the first execution unit.

2. The method of claim 1, wherein the first path corresponds to a predicted path of the branch instruction and wherein the second path corresponds to a non-predicted path of the branch instruction.

3. The method of claim 1, wherein a determination of whether the branch instruction follows the first path or the second path is made within a predetermined time period, and wherein the instructions for the first path of the branch instruction and the instructions for the second path of the branch instruction are maintained in the dual instruction queue for at least the predetermined time period.

4. The method of claim 1, wherein instructions for the first path of the branch instruction and instructions for the second path of the branch instruction are both issued to the dual instruction queue only if a predictability value for the branch instruction is below a threshold value for predictability.

5. The method of claim 1, wherein instructions for the first path of the branch instruction and instructions for the second path of the branch instruction are both in a first thread.

6. The method of claim 5, wherein instructions for the first path of the branch instruction and instructions for the second path of the branch instruction are both issued to the dual instruction queue only if a second thread is quiesced.

7. The method of claim 1, wherein instructions for the first path issued to the first queue and instructions for the second path issued to the second queue are each maintained in the dual instruction queue for a same amount of time.

8. The method of claim 1, wherein determining if the branch instruction follows the first path or the second path comprises executing the branch instruction in a second execution unit.

9. A processor comprising:

a cache;

a dual instruction queue comprising a first queue and a second queue;

a first execution unit; and

circuitry configured to”

receive a branch instruction;

issue instructions for a first path of the branch instruction to the first queue of a dual instruction queue;

issue instructions for a second path of the branch instruction to a second queue of a dual instruction queue;

determine if the branch instruction follows the first path or the second path;

upon determining that the branch instruction follows the first path, provide the instructions for the first path from the first queue to a first execution unit; and

upon determining that the branch instruction follows the second path, provide the instructions for the second path from the second queue to the first execution unit.

10. The processor of claim 9, wherein the first path corresponds to a predicted path of the branch instruction and wherein the second path corresponds to a non-predicted path of the branch instruction.

11. The processor of claim 9, wherein a determination of whether the branch instruction follows the first path or the second path is made within a predetermined time period, and wherein the dual instruction queue is configured to maintain the instructions for the first path of the branch instruction and the instructions for the second path of the branch instruction in the dual instruction queue for at least the predetermined time period.

12. The processor of claim 9, wherein instructions for the first path of the branch instruction and instructions for the second path of the branch instruction are both issued to the dual instruction queue only if a predictability value for the branch instruction is below a threshold value for predictability.

13. The processor of claim 9, wherein instructions for the first path of the branch instruction and instructions for the second path of the branch instruction are both in a first thread executed by the processor.

14. The processor of claim 13, wherein instructions for the first path of the branch instruction and instructions for the second path of the branch instruction are both issued to the dual instruction queue only if a second thread is quiesced.

15. The processor of claim 9, wherein instructions for the first path issued to the first queue and instructions for the second path issued to the second queue are each maintained in the dual instruction queue for a same amount of time.

16. The processor of claim 9, wherein determining if the branch instruction follows the first path or the second path comprises executing the branch instruction in a second execution unit.

17. A processor comprising:

an execution unit;

a dual instruction queue comprising a first queue and a second queue;

issue circuitry configured to;

issue instructions for a first path of a branch instruction to the first queue of the dual instruction queue; and

issue instructions for a second path of the branch instruction to the second queue of the dual instruction queue;

branch execution circuitry configured to;

determine if the branch instruction follows the first path or the second path of the branch instruction;

upon determining that the branch instruction follows the first path, provide a first selection signal; and

upon determining that the branch instruction follows the second path, provide a second selection signal; and

selection circuitry configured to;

provide the instructions for the first path from the first queue to the execution unit upon detecting the first selection signal; and

provide the instructions for the second path from the second queue to the execution unit upon detecting the second selection signal.

18. The processor of claim 17, further comprising:

first scheduling circuitry configured to receive and schedule execution of the instructions for the first path of the branch instruction;

second scheduling circuitry configured to receive and schedule execution of the instructions for the second path of the branch instruction.

19. The processor of claim 18, wherein the first scheduling circuitry is further configured to schedule execution of instructions from a first thread and wherein the second scheduling circuitry is further configured to schedule execution of instructions from a second thread.

20. The processor of claim 17, wherein a determination of whether the branch instruction follows the first path or the second path is made within a predetermined time period, and wherein the dual instruction queue is configured to maintain the instructions for the first path of the branch instruction and the instructions for the second path of the branch instruction in the dual instruction queue for at least the predetermined time period.

21. The processor of claim 17, wherein instructions for the first path issued to the first queue and instructions for the second path issued to the second queue are each maintained in the dual instruction queue for a same amount of time.