Integrated single structure branch prediction cache

• US 5,093,778 A
• Filed: 02/26/1990
• Issued: 03/03/1992
• Est. Priority Date: 02/26/1990
• Status: Expired due to Term

• Current Assignee: Nexgen Incorporated (Advanced Micro Devices, Inc.)
• Original Assignee: Nexgen Microsystems
• Inventors: Van Dyke, Korbin, Favor, John G., Stiles, David R., Smith, Walstein B. III
• Primary Examiner(s): Heckler, Thomas M.
• Application Number:
  US07/485,307
• Time in Patent Office: 736 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 712/240
• CPC Class Codes: G06F 9/3806 using address prediction, e.g. return stack, branch history buffer
• CPC Class Codes: G06F 9/3844 using dynamic branch prediction, e.g. using branch history tables

Abstract

The present invention provides an improved branch prediction cache (BPC) structure that combines various separate structures into one integrated structure. In conjunction with doing this, the present invention is able to share significant portions of hardware cost and design complexity overhead. As a result, the cost-performance trade-off for implementing dynamic branch prediction for target address, branch direction, and target instructions aspects of branches shifts to where "full" branch prediction is now more practical.

Claims

1. An integrated branch prediction cache structure comprising:

a program counter content addressable memory (PcCAM) for storing branch instruction addresses;

a valid bit (Vbit) memory associated with said PcCAM;

a branch address cache (BAC) for storing branch target instruction addresses;

a branch history cache (BHC) for storing data indicating the direction of past branches;

a branch target cache (BTC) for storing instruction data at said branch target instruction addresses;

a target instruction valid (TIV) memory associated with said BTC;

each of said PcCAM, Vbit memory, BAC, BHC, BTC, and TIV memory containing N entries;

each of said BAC, BHC, BTC, and TIV memory having N read select inputs, corresponding to its N entries, the appearance of an active signal at one of which allows the corresponding entry to be read;

said PcCAM having associated means, responsive to an address input, for determining whether any entry corresponds to input, and for asserting a read select signal corresponding to any match of a specific PcCAM entry that corresponds to the address input;

means for applying said read select signal to the read select input of each of said BAC, BHC, BTC, and TIV memory entries that correspond to the specific PcCAM entry to allow such corresponding entries to be read.

2. The integrated structure of claim 1 further comprising means for performing a content addressable match of said BAC.

3. The integrated structure of claim 1 further comprising address selection logic having, for each of said N entries, write enable outputs to said PcCAM, BAC, BTC, BHC and TIV memory and an input bus coupled to said address selection logic for all of said N

4. The integrated cache structure of claim 1 said PcCAM is a content addressable memory (CAM) having N memory words for storing said N PCC entries;

and

said associated means for determining comprises

N comparators, each associated with a respective one of said N memory words, each comparator having a first input responsive to the PC input, a second input responsive to the content of its associated memory word, and an output on which is asserted said read select signal when the values at said first and second inputs agree.

5. The integrated cache structure of claim 1 wherein each of said PcCAM, Vbit memory, BAC, BHC, BTC, and TIV memory has N write select inputs corresponding to its N entries, and further comprising:

a plurality of address selection logic means, each responsive to a respective index input representing a desired entry number, for asserting a write select signal corresponding to the desired entry number; and

means for applying each of said plurality of write select inputs to a selected subset of said read select inputs and write select inputs.

6. The integrated cache structure of claim 1 wherein said BAC comprises:

N memory words for storing N BAC entries, each BAC entry containing target address information including at least a portion of at least one target address associated with the corresponding BTC entry;

means for receiving a check address input;

N comparator means, each associated with a respective one of said N memory words, for comparing at least a portion of said check address input with said target address information stored in its associated memory word; and

N means, each associated with one of said N entries, operative in response to an output of one of said N comparator means, for setting the corresponding entry in said Vbit memory to signify invalid.