Implementation of an efficient instruction fetch pipeline utilizing a trace cache

• US 7,139,902 B2
• Filed: 02/03/2003
• Issued: 11/21/2006
• Est. Priority Date: 10/29/2002
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Lee, Yung-hsiang
• Primary Examiner(s): Chan, Eddie
• Assistant Examiner(s): Fiegle, Ryan
• Application Number:
  US10/356,984
• Publication Number:
  US 20040083352A1
• Time in Patent Office: 1,387 Days
• Field of Search: 712233-235, 712/205, 712/219, 711/120, 711/125
• US Class Current: 712/234
• CPC Class Codes: G06F 9/3808 for instruction reuse, e.g. trace cache, branch target cache

Abstract

A method and apparatus are disclosed for enhancing the pipeline instruction transfer and execution performance of a computer architecture by reducing instruction stalls due to branch and jump instructions. Trace cache within a computer architecture is used to receive computer instructions at a first rate and to store the computer instructions as traces of instructions. An instruction execution pipeline is also provided to receive, decode, and execute the computer instructions at a second rate that is less than the first rate. A mux is also provided between the trace cache and the instruction execution pipeline to select a next instruction to be loaded into the instruction execution pipeline from the trace cache based, in part, on a branch result fed back to the mux from the instruction execution pipeline.

Claims

1. In a computer architecture for executing computer instructions, a method to reduce the occurrence of instruction execution pipeline stalls due to branch instructions and jump instructions, said method comprising:

providing an instruction transfer bandwidth into a trace cache of said computer architecture that is greater than an instruction execution bandwidth of said computer architecture;

utilizing said instruction transfer bandwidth to provide both the taken and not taken paths of a branch to the trace cache;

feeding back branch results of executed branch instructions to control the transmission of correct next instructions into the execution pipeline; and

using branch delay slots to postpone the execution of said next instruction during said transmission such that the occurrence of instruction execution stalls within said instruction execution pipeline is reduced.

2. The method of claim 1 further comprising providing at least one of said branch delay slots for each of said branch instructions.

3. The method of claim 1 wherein said instruction transfer bandwidth is at least twice said instruction execution bandwidth.

4. The method of claim 1 wherein said instruction execution bandwidth corresponds to one instruction per clock cycle of said computer architecture.

5. The method of claim 1 wherein said instruction transfer bandwidth corresponds to at least two instructions per clock cycle of said computer architecture.

6. The method of claim 1 wherein any fed-back branch result of said branch results determines which of two possible instructions is transferred next into said instruction execution pipeline for subsequent execution.

7. The method of claim 1 wherein at least two instructions are transferred from an instruction cache of said computer architecture to said trace cache of said computer architecture during a single instruction execution time.

8. The method of claim 1 wherein a current pointer is pointing to a current trace of instructions within said trace cache of said computer architecture when an instruction of said current trace is within said instruction execution pipeline.

9. The method of claim 1 wherein a branch pointer is updated to point to a branch trace of instructions within said trace cache based on a branch instruction within a current trace of instructions to be executed.

10. The method of claim 1 wherein any fed-back branch result of said branch results determines which trace in said trace cache is to be loaded next into said instruction execution pipeline.

11. In a computer architecture for executing computer instructions, an apparatus to reduce the occurrence of instruction execution pipeline stalls due to branch instructions and jump instructions, said apparatus comprising:

a trace cache that receives computer instructions at a first rate and stores said computer instructions as traces of instructions, including both taken and not taken paths of branches;

an instruction execution pipeline that receives, decodes, and executes computer instructions at a second rate that is less than said first rate;

a selector that selects a next instruction to be loaded into said instruction execution pipeline from said trace cache based, in part, on a branch result fed back from said instruction execution pipeline as a control to said selector to transmit correct next instructions into the execution pipeline; and

wherein said instruction execution pipeline uses branch delay slots to postpone the execution of said next instruction during said transmission such that the occurrence of instruction execution stalls within said instruction execution pipeline is reduced.

12. The apparatus of claim 11 wherein said instruction execution pipeline comprises:

an instruction register that receives said next instruction from said trace cache by way of said selector;

an instruction decoder that receives said next instruction from said instruction register and generates a decoded instruction; and

an instruction executor that receives said decoded instruction from said instruction decoder and executes said decoded instruction.

13. The apparatus of claim 12 wherein said instruction executor comprises:

a data register that stores data words associated with said decoded instruction; and

a results register that stores a result of executing said decoded instruction using said data words.

14. The apparatus of claim 11 further comprising;

instruction cache that sends said computer instructions to said trace cache at said first rate; and

memory that sends said computer instructions to said instruction cache at said second rate.

15. The apparatus of claim 11 wherein said branch result is generated by the execution of a branch instruction.

16. The apparatus of claim 11 wherein said second rate corresponds to one instruction per clock cycle of said computer architecture.

17. The apparatus of claim 11 wherein said instruction execution pipeline accommodates at least one of said branch delay slots for each branch instruction.

18. The apparatus of claim 11 wherein said first rate corresponds to at least two instructions per clock cycle of said computer architecture.

19. The apparatus of claim 14 wherein at least two instructions are transferred from said instruction cache to said trace cache based on said branch result.

20. The apparatus of claim 12 wherein a current pointer points to a current trace of instructions within said trace cache to be executed and a branch pointer points to a branch trace of instructions within said trace cache based on a branch instruction of said current trace of instructions to be executed.