Instruction cache configured to provide instructions to a microprocessor having a clock cycle time less than a cache access time of said instruction cache

• US 6,167,510 A
• Filed: 04/23/1998
• Issued: 12/26/2000
• Est. Priority Date: 03/26/1996
• Status: Expired due to Term

• Current Assignee: Advanced Micro Devices, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Tran, Thang M.
• Primary Examiner(s): Pan, Daniel H.
• Assistant Examiner(s): Nguyen, Dzung C.
• Application Number:
  US09/065,346
• Time in Patent Office: 978 Days
• Field of Search: 712/205, 712/206, 712/207, 712/233, 712/235, 712/236, 712/239, 712/240, 712/237, 712/238
• US Class Current: 712/239
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06F 9/3802 Instruction prefetching
• CPC Class Codes: G06F 9/3806 using address prediction, e.g. return stack, branch history buffer
• CPC Class Codes: G06F 9/3814 Implementation provisions of instruction buffers, e.g. prefetch buffer; banks

Abstract

An apparatus including a banked instruction cache and a branch prediction unit is provided. The banked instruction cache allows multiple instruction fetch addresses (comprising consecutive instruction blocks from the predicted instruction stream being executed by the microprocessor) to be fetched concurrently. The instruction cache provides an instruction block corresponding to one of the multiple fetch addresses to the instruction processing pipeline of the microprocessor during each consecutive clock cycle, while additional instruction fetch addresses from the predicted instruction stream are fetched. Preferably, the instruction cache includes at least a number of banks equal to the number of clock cycles consumed by an instruction cache access. In this manner, instructions may be provided during each consecutive clock cycle even though instruction cache access time is greater than the clock cycle time of the microprocessor.

Claims

1. An apparatus for performing branch prediction, comprising:

a branch prediction storage coupled to receive a first address of a first instruction block, wherein said branch prediction storage is configured to store a plurality of branch predictions, and wherein said branch prediction storage is configured to select and output a first branch prediction from said plurality of branch predictions responsive to said first address, said first branch prediction predicting a second address of a second instruction block non-consecutive with said first instruction block within a predicted instruction stream, and wherein a branch instruction having said second address as a target address is within a third instruction block between said first instruction block and said second instruction block within said predicted instruction stream; and

a prediction control unit coupled to said branch prediction storage, wherein said prediction control unit is configured to update said plurality of branch predictions responsive to execution of said predicted instruction stream.

2. The apparatus as recited in claim 1 wherein said branch prediction storage is configured to receive a third address of said third instruction block concurrently with receiving said first address, and wherein said branch prediction storage is configured to select and output a second branch prediction responsive to said third address, said second branch prediction predicting a fourth address of a fourth instruction block non-consecutive to said third instruction block within said predicted instruction stream.

3. The apparatus as recited in claim 2 wherein said third instruction block is consecutive to said first instruction block.

4. The apparatus as recited in claim 3 wherein said fourth instruction block is consecutive to said second instruction block.

5. The apparatus as recited in claim 1 wherein said branch prediction storage is further configured to select and output a first consecutive branch prediction from said plurality of branch predictions responsive to said first address, said first consecutive branch prediction predicting said third instruction block consecutive to said first instruction block within said predicted instruction stream.

6. The apparatus as recited in claim 5 further comprising a prediction buffer coupled to said prediction control unit and said branch prediction storage, wherein said prediction control unit is configured to store branch predictions corresponding to instruction blocks outstanding within a microprocessor pipeline in said prediction buffer to facilitate updating said branch predictions within said branch prediction storage, and wherein said prediction control unit is configured to store said first branch prediction in said prediction buffer upon output thereof from said branch prediction storage.

7. The apparatus as recited in claim 6 wherein said prediction control unit is further configured to store a first index for said first branch prediction in said prediction buffer, said first index corresponding to said third instruction block.

8. The apparatus as recited in claim 7 wherein said prediction control unit is further configured to store a second index for said first branch prediction in said prediction buffer, said second index corresponding to said first address.

9. The apparatus as recited in claim 8 wherein said prediction control unit, upon receiving an indication that said first branch prediction is mispredicted, is configured to update said first branch prediction stored in said branch prediction storage at said second index, and wherein said prediction control unit, upon receiving said indication, is further configured to update a consecutive branch prediction stored at said first index.

10. The apparatus as recited in claim 9 wherein said branch prediction storage is set associative, and wherein said prediction control unit is configured to store a first way corresponding to said first index and a second way corresponding to said second index in said prediction buffer, and wherein said prediction control unit is configured to update said first branch prediction stored in said branch prediction storage at said second index and said second way, and wherein said prediction control unit is configured to update said consecutive branch prediction stored at said first index and said first way.

11. A method for performing branch prediction comprising:

storing a first branch prediction for a first branch instruction within a first instruction block in a second storage location within a branch prediction storage, said second storage location corresponding to a second instruction block prior to said first instruction block in a predicted instruction stream;

fetching said second instruction block; and

fetching said first branch prediction from said branch prediction storage responsive to said fetching said second instruction block, whereby a third instruction block subsequent to said first instruction block is predicted in response to fetching said second instruction block.

12. The method as recited in claim 11 further comprising fetching said first instruction block concurrent with said fetching said second instruction block.

13. The method as recited in claim 12 further comprising fetching a third branch prediction corresponding to a third branch instruction within said third instruction block responsive to said fetching said first instruction block.

14. The method as recited in claim 11 further comprising:

detecting a misprediction of said first branch instruction; and

updating said first branch prediction within said second storage location responsive to said detecting.

15. The method as recited in claim 14 further comprising storing said first branch prediction within a first storage location within said branch prediction storage, said first storage location corresponding to said first instruction block.

16. The method as recited in claim 15 further comprising updating said first storage location responsive to said detecting said misprediction.

17. A microprocessor comprising:

a branch prediction unit configured to provide a branch prediction indicating a first instruction block responsive to a fetch address, wherein said first instruction block is non-consecutive to a second instruction block identified by said fetch address within a predicted instruction stream, and wherein a branch instruction having a target address indicating said first instruction block is within a third instruction block between said first instruction block and said second instruction block within said predicted instruction stream; and

an instruction cache coupled to said branch prediction unit, wherein said instruction cache is configured to store instruction bytes.

18. The microprocessor as recited in claim 17 further comprising a functional unit coupled to receive a branch instruction corresponding to said branch prediction, said functional unit configured to executed said branch instruction and detect a misprediction thereof.

19. The microprocessor as recited in claim 18 wherein said branch prediction unit is coupled to receive an indication of said misprediction from said functional unit, and wherein said branch prediction unit is configured to update said branch prediction responsive to said misprediction.

20. A computer system comprising:

a microprocessor configured to provide a branch prediction for a first instruction block responsive to a fetch address, wherein said first instruction block is non-consecutive to a second instruction block identified by said fetch address within a predicted instruction stream, and wherein a branch instruction having a target address indicating said first instruction block is within a third instruction block between said first instruction block and said second instruction block within said prediction instructed stream; and

an input/output (I/O) device coupled to said microprocessor and to another computer system, wherein said I/O device is configured to communicate between said microprocessor and said another computer system.