Compressed indirect prediction caches

Patent metadata

Field	Value
Publication number	US-9483271-B2
Application number	US-201314145039-A
Country	US
Kind code	B2
Filing date	Dec 31, 2013
Priority date	Dec 31, 2013
Publication date	Nov 1, 2016
Grant date	Nov 1, 2016

Abstract

Provided herein is a compressed cache design to predict indirect branches in a microprocessor based on the characteristics of the addresses of the branch instructions. In one aspect, a method for predicting a branch target T in a microprocessor includes the following steps. A compressed count cache table (CTABLE) of branch targets indexed using a function combining a branch address and a branch history vector for each of the targets is maintained, wherein entries in the CTABLE contain only low-order bits of each of the targets in combination with an index bit(s) I. A given one of the entries is obtained related to a given one of the branch targets and it is determined from the index bits I whether A) high-order bits of the target are equal to the branch address, or B) the high-order bits of the target are contained in an auxiliary cache table (HTABLE).

First claim

What is claimed is:

1. A method for predicting a branch target T in a microprocessor, the method which is performed by a processor device comprises the steps of:
maintaining a compressed count cache table (CTABLE) of branch targets indexed using a function combining a branch address and a branch history vector for each of the branch targets, wherein entries in the CTABLE contain only low-order bits of each of the branch targets in combination with one or more index bits I;
obtaining a given one of the entries from the CTABLE related to a given one of the branch targets;
determining from the index bits I in the given entry whether A) high-order bits of the given branch target are equal to the branch address, or B) the high-order bits of the given branch target are contained in an auxiliary cache table (HTABLE); and
when A applies: predicting the branch target T using only the low-order bits of the given branch target, or when B applies: accessing the high-order bits of the given branch target via the HTABLE and predicting the branch target T using one or more of the low-order bits of the given branch target and the high-order bits of the given branch target.

2. The method of claim 1 , wherein the HTABLE contains the high-order bits of the branch targets indexed using the index bits I.

3. The method of claim 2 , further comprising the step of:
obtaining an entry from the HTABLE containing the high-order bit for the given branch target.

4. The method of claim 1 , wherein A applies when I=0, and B applies when I≠0.

5. The method of claim 1 , further comprising the step of:
inputting entries from the HTABLE into a multiplexer.

6. The method of claim 1 , wherein the branch target T predicted is different from an actual target, the method further comprising the steps of:
determining whether high-order bits of the actual target equal high-order bits of the branch target T predicted; and
determining whether low-order bits of the actual target equal low-order bits of the branch target T predicted.

7. The method of claim 6 , wherein the high-order bits of the actual target do not equal the high-order bits of the branch target T predicted, the method further comprising the steps of:
determining whether the high-order bits of the actual target equal high-order bits of the branch address; and
setting the index bits I in the given entry to 0 if the high-order bits of the actual target equal the high-order bits of the branch address.

8. The method of claim 7 , wherein the high-order bits of the actual target do not equal the high-order bits of the branch address, the method further comprising the steps of:
determining if high-order bits of any given entry X in the HTABLE equal the high-order bits of the actual target; and
setting the index bits I in the given entry to an index of the given entry X if the high-order bits of the given entry X in the HTABLE equal the high-order bits of the actual target.

9. The method of claim 6 , wherein the low-order bits of the actual target do not equal the low-order bits of the branch target T predicted, the method further comprising the step of:
replacing the low-order bits of the given branch target in the CTABLE with the low-order bits of the actual target.

10. The method of claim 1 , wherein the one or more index bits I comprise 2-bits.

11. The method of claim 1 , wherein the one or more index bits I comprise a single bit.

12. An apparatus for predicting a branch target T in a microprocessor, the apparatus comprising:
a memory; and
at least one processor device, coupled to the memory, operative to:
maintain a compressed count cache table (CTABLE) of branch targets indexed using a function combining a branch address and a branch history vector for each of the branch targets, wherein entries in the CTABLE contain only low-order bits of each of the branch targets in combination with one or more index bits I;
obtain a given one of the entries from the CTABLE related to a given one of the branch targets;
determine from the index bits I in the given entry whether A) high-order bits of the given branch target are equal to the branch address, or B) the high-order bits of the given branch target are contained in an auxiliary cache table (HTABLE); and
when A applies: predict the branch target T using only the low-order bits of the given branch target, or when B applies: access the high-order bits of the given branch target via the HTABLE and predict the branch target T using one or more of the low-order bits of the given branch target and the high-order bits of the given branch target.

13. The apparatus of claim 12 , wherein the HTABLE contains the high-order bits of the branch targets indexed using the index bits I.

14. The apparatus of claim 13 , wherein the at least one processor device is further operative to:
obtain an entry from the HTABLE containing the high-order bit for the given branch target.

15. The apparatus of claim 12 , wherein the at least one processor device is further operative to:
input entries from the HTABLE into a multiplexer.

16. The apparatus of claim 12 , wherein the branch target T predicted is different from an actual target, and wherein the at least one processor device is further operative to:
determine whether high-order bits of the actual target equal high-order bits of the branch target T predicted; and
determine whether low-order bits of the actual target equal low-order bits of the branch target T predicted.

17. The apparatus of claim 16 , wherein the high-order bits of the actual target do not equal the high-order bits of the branch target T predicted, and wherein the at least one processor device is further operative to:
determine whether the high-order bits of the actual target equal high-order bits of the branch address; and
set the index bits I in the given entry to 0 if the high-order bits of the actual target equal the high-order bits of the branch address.

18. The apparatus of claim 17 , wherein the high-order bits of the actual target do not equal the high-order bits of the branch address, and wherein the at least one processor device is further operative to:
determine if high-order bits of any given entry X in the HTABLE equal the high-order bits of the actual target; and
set the index bits I in the given entry to an index of the given entry X if the high-order bits of the given entry X in the HTABLE equal the high-order bits of the actual target.

19. The apparatus of claim 16 , wherein the low-order bits of the actual target do not equal the low-order bits of the branch target T predicted, and wherein the at least one processor device is further operative to:
replace the low-order bits of the given branch target in the CTABLE with the low-order bits of the actual target.

20. An article of manufacture for predicting a branch target T in a microprocessor, comprising a non-transitory machine-readable recordable medium containing one or more programs which when executed implement the steps of:
maintaining a compressed count cache table (CTABLE) of branch targets indexed using a function combining a branch address and a branch history vector for each of the branch targets, wherein entries in the CTABLE contain only low-order bits of each of the branch targets in combination with one or more index bits I;
obtaining a given one of the entries from the CTABLE related to a given one of the branch targets;
determining from the index bits I in the given entry whether A) high-order bits of the given branch target are equal

Assignees

• IBM

Inventors

• Karkhanis Tejas
• Levitan David S
• Moreira Jose E
• Serrano Mauricio J

Classifications

• G06F9/3806 Primary

  using address prediction, e.g. return stack, branch history buffer · CPC title

• G06F9/322

  for non-sequential address · CPC title

• G06F9/30061

  Multi-way branch instructions, e.g. CASE · CPC title