Branch history cache

• US 6,314,493 B1
• Filed: 02/03/1998
• Issued: 11/06/2001
• Est. Priority Date: 02/03/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Luick, David Arnold
• Primary Examiner(s): Kim, Matthew
• Assistant Examiner(s): TZENG, FRED
• Application Number:
  US09/018,688
• Time in Patent Office: 1,372 Days
• Field of Search: 711/117, 711/119, 711/120, 711/123, 711/128, 711/137, 711/169, 711/203, 711/204, 712/240, 712/215, 712/206, 712/244, 712/24, 712/237, 712/238, 712/239
• US Class Current: 711/137
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06F 9/3804 for branches, e.g. hedging, branch folding
• CPC Class Codes: G06F 9/3806 using address prediction, e.g. return stack, branch history buffer

Abstract

Disclosed is a predictive instruction cache system, and the method it embodies, for a VLIW processor. The system comprises: a first cache; a real or virtual second cache for storing a subset of the instructions in the second cache; and a real or virtual history look-up table for storing relations between first instructions and second instructions in the second cache. If a first instruction is located in a stage of the pipeline, then one of the relations will predict that a second instruction will be needed in the same stage a predetermined time later. The first cache can be physically distinct from the second cache, but preferably is not, i.e., the second cache is a virtual array. The history look-up table can also be physically distinct from the first cache, but preferably is not, i.e., the history look-up table is a virtual look-up table. The first cache is organized as entries. Each entry has a first portion for the first instruction and a second portion for a branch-to address indicator pointing to the second instruction. For a given first instruction, a new branch-to address indicator independently can be stored in the second field to replace an old branch-to address indicator and so reflect a revised prediction. Alternatively, redundant data fields in the parcels of the VLIWs are used to store the branch-to address guesses so that a physically distinct second portion can be eliminated in the entries of the first cache.

Claims

1. A cache system for a processor having a multi-stage execution pipeline, the system comprising:

a first cache for storing instructions that can be executed in said pipeline;

a virtual second cache for storing a subset of said instructions in said first cache; and

a virtual history look-up table for storing a plurality of relations, each one of said relations relating a first instruction in said first cache to a second instruction in said second cache such that if said first instruction is in a stage of said pipeline then said second instruction is predicted to be needed in said stage of said pipeline a predetermined time later;

wherein said history look-up table is operable to represent said relations a plurality of entries, each one of said entries including an address of said first instruction and a branch-to indicator indicating an address of said instruction;

a directory for said first cache connected with said history look-up table and connected so as to receive an actual branch-to address from said pipeline, said directory being operable to provide an output equal to said actual branch-to address if a corresponding branch-to instruction is stored in said first cache, and being operable to set said output equal to a third signal indicating that no instruction corresponding to said actual branch-to address is stored in said first cache if said corresponding branch-to instruction is not stored in said first cache;

a comparator for comparing a guess represented by one of said branch-to address indicators with output from said directory, said comparator indicating a correct guess if said guess matches said output from said directory and an incorrect guess if said guess does not match said output from said directory; and

a selector, connected between said history look-up table and said comparator and connected to receive said actual branch-to address, for selecting either said guess or said actual branch-to address;

said comparator also being operable to compare said actual branch-to address with said output from said directory, said comparator being operable to provide an output indicative of a hit if said actual branch-to address matches said output from said directory, and being operable to provide an output indicative of a miss if said actual branch-to address does not match said output from said directory.

2. A cache system for a processor having a multi-stage execution pipeline, the system comprising:

a first cache for storing instructions that can be executed in said pipeline;

a virtual second cache for storing a subset of said instructions in said first cache; and

a virtual history look-up table for storing a plurality of relations, each one of said relations relating a first instruction in said first cache to a second instruction in said second cache such that if said first instruction is in a stage of said pipeline then said second instruction is predicted to be needed in said stage of said pipeline a predetermined time later;

wherein said processor is a very long instruction word (VLIW) processor and said first and second instructions are VLIWs;

wherein each of one said VLIWs includes a plurality of parcels;

wherein at least a first and a second one of said parcels in each one of said VLIWs are conditionally branching parcels that branch to said second instruction;

wherein each one of said parcels having a plurality of fields including a multipurpose field;

wherein said multipurpose field in first parcel storing a branch-to address indicator pointing toward a third instruction to which said first instruction conditionally will branch; and

wherein said multipurpose field in said second parcel storing a branch-to guess address indicator indicating an address of said second instruction.

3. The system of claim 2, wherein said pocessor is a very long instruction word (VLIW) processor and said instruction are VLIWs.

4. The system of claim 2, wherein said first cache is four-way associative.

5. The system of claim 4, wherein said second cache is four-way associative.

6. The system of claim 2, wherein said predetermined time is one of two cycles and four cycles.

7. The system of claim 2, wherein said first cache has a plurality of entries, each entry having a first portion for said first instruction and a second portion for a branch-to address indicator pointing to said second instruction predicted to be needed in said stage of said pipeline said predetermined time later.

8. The system of claim 7, wherein said second portions can be written to independently of said first portions such that, for a given first instruction, a new branch-to address indicator independently can be stored in said second portions to replace an old branch-to address indicator and so reflect a revised prediction.

9. The system of claim 8, wherein said second portion stores an entire real address as said branch-to address indicator.

10. The system of claim 8, wherein a basic unit of storage in said first cache is a line, and said second portion is sized to store only as many bits as are necessary to uniquely identify one of said basic units of storage in said first cache.

11. The system of claim 2, wherein said multipurpose fields can be written to independently such that, for a given first instruction, a new branch-to address indicator independently can be stored in said second field to replace an old branch-to address indicator and so reflect a revised prediction.

12. The system of claim 11, wherein a basic unit of storage in said first cache is a line, and said multipurpose fields are sized to store only as many bits as are necessary to uniquely identify one of said basic units of storage in said first cache.

13. The system of claim 2, wherein said predetermined time corresponds to an access time of either an L1 or an L2 cache.

14. A method for caching instructions for a processor having a multi-stage execution pipeline, the method:

storing, as a first cache, a main set of instructions that can be executed in said pipeline;

storing, as a virtual second cache, a subset of said instructions stored in said first cache;

storing, as a virtual history look-up table, a plurality of relations, each one of said relations relating a first instruction in said first cache to a second instruction in said second cache such that if said first instruction is in a stage of said pipeline then said second instruction is predicted to be needed in said stage of said pipeline a predetermined time later;

wherein the branch history information is not stored at locations physically distinct from locations where said main set of instructions is stored due to being located in fields of instructions in said main set that would otherwise contain redundant information;

representing said relations as a plurality of entries in said history LUT, each one of said entries including an address of said first instruction and a branch-to address indicator indicating an address of said second instruction;

receiving an actual branch-to address from said pipeline;

providing a directory output equal to said actual branch-to address if a corresponding branch-to instruction is stored in said first cache, and equal to a third signal if said corresponding branch-to instruction is not stored in said Icache;

comparing a branch-guess represented by one of said branch-to address indicators with said directory output;

providing an output indicative of a correct guess if said guess matches said output from said directory, and an output indicative of an incorrect guess if said guess does not match said output from said directory;

selecting either said branch-guess or said actual branch-to address for said step of comparing;

comparing said actual branch-to address with said output from said directory; and

indicating a hit if said actual branch-to address matches said output from said directory and a miss if said actual branch-to address does not match said output from said directory.

15. A method for caching instructions for a processor having a multi-stage execution pipeline, the method:

storing, as a first cache, a main set of instructions that can be executed in said pipeline;

storing, as a virtual second cache, a subset of said instructions stored in said first cache;

storing, as a virtual history look-up table, a plurality of relations, each one of said relations relating a first instruction in said first cache to a second instruction in said second cache such that if said first instruction is in a stage of said pipeline then said second instruction is predicted to be needed in said stage of said pipeline a predetermined time later;

wherein the branch history information is not stored at locations physically distinct from locations where said main set of instructions is stored due to being located in fields of instructions in said main set that would otherwise contain redundant information;

wherein said processor is a very long instruction word (VLIW) processor and said first and second instructions are VLIWs;

wherein each of one said VLIWs includes a plurality of parcels;

wherein at least a first and a second one of said parcels in each one of said VLIWs are conditionally branching parcels that branch to said second instruction;

wherein each one of said parcels having a plurality of fields including a multipurpose field;

storing a branch-to address indicator, pointing toward an address of a third instruction to which said first instruction conditionally will branch, in said multipurpose field of said first parcel; and

storing a branch-to guess address indicator, indicating an address of said second instruction, in said multipurpose field of said second parcel.

16. The method of claim 15, wherein said processor is a very long instruction word (VLIW) processor and said instructions are VLIWs.

17. The method of claim 15, wherein said main set of instructions is stored so as to be four-way associatively searchable.

18. The method of claim 17, wherein said subset of instructions is stored so as to be four-way associatively searchable.

19. The method of claim 15, wherein said predetermined time is one of two cycles and four cycles.

20. The method of claim 15, wherein said plurality of relations is stored at locations that are physically distinct from locations at which said main set of said instructions is stored.

21. The method of claim 15, wherein said first cache is organized as entries, each entry having a first portion for said first instruction and a second portion for a branch-to address indicator pointing to said second instruction predicted to be needed in said stage of said pipeline said predetermined time later.

22. The method of claim 21, further comprising writing data into said second portions independently of writing data to said first portions such that, for a given first instruction, a new branch-to address indicator independently can be stored in said second portion to replace an old branch-to address indicator and so reflect a revised prediction.

23. The method of claim 22, wherein said second portion stores an entire real address as said branch-to address indicator.

24. The method of claim 23, wherein a basic unit of storage in said first cache is a line, and said second field portion is sized to store only as many bits as are necessary to uniquely identify one of said basic units of storage in said first cache.

25. The method of claim 15, further comprising:

writing to said multipurpose fields independently such that, for a given first instruction, a new branch-to address indicator independently can be stored in said second field to replace an old branch-to address indicator and so reflect a revised prediction.

26. The method of claim 25, wherein a basic unit of storage in said first cache is a line, and said multipurpose fields are sized to store only as many bits as are necessary to uniquely identify one of said basic units of storage in said first cache.

27. The method of claim 15, wherein said predetermined time corresponds to an access time of either an L1 or an L2 cache.

28. A cache system for a processor having a multi-stage execution pipeline, the system comprising:

a first cache for storing instructions that can be executed in said pipeline;

a second cache for storing a subset of said instruction in said first cache; and

a history look-up table for storing a plurality of relations, each one of said relations relating a first instruction in said first cache to a second instruction in said second cache such that if said first instruction is in a stage of said pipeline then said second instruction is predicted to be needed in said stage of said pipeline a predetermined time later;

and wherein

said second cache is real or virtual;

said history look-up table is not physically distinct from said first cache, rather said history look-up table is a virtual look-up table;

said processor is a very long instruction word (VLIW) processor and said first and second instructions are VLIWs;

each of one said VLIWs includes a plurality of parcels;

at least a first and a second one of said parcels in each one of said VLIWs are conditionally branching parcels that branch to said second instruction;

each one of said parcels having a plurality of fields including a multipurpose field;

said multipurpose field in first parcel storing a branch-to address indicator pointing toward a third instruction to which said first instruction conditionally will branch; and

said multipurpose field in said second parcel storing a branch-to guess address indicator indicating an address of said second instruction.

29. The system of claim 28, wherein said multipurpose field can be written to independently such that, for a given first instruction, a new branch-to address indicator independently can be stored in said second field to replace an old branch-to address indicator and so reflect a revised prediction.

30. The system of claim 29, wherein a basic unit of storage in said first cache is a line, and said multipurpose fields are sized to store only as many bits as are necessary to uniquely identify one of said basic units of storage in said first cache.

31. A method for caching instructions for a processor having a multi-stage execution pipeline, the method comprising:

storing, as a first cache, a main set of instructions that can be executed in said pipeline;

storing, as a second cache, a subset of said instructions stored in said first cache; and

storing, as a real or virtual history look-up table (look-up table), a plurality of relations, each one of said relations relating a first instruction in said first cache to a second instruction in said second cache such that if said first instruction is in a stage of said pipeline then said second instruction is predicted to be needed in said stage of said pipeline a predetermined time later;

and wherein

said main set of said instructions is not stored at location physically distinct from locations where said plurality of relations is stored, rather said history look-up is a virtual array;

said processor is a very long instruction word (VLIW) processor and said first and second instructions are VLIWs;

each of one said VLIWs includes a plurality of parcels;

at least a first and a second one of said parcels in each one of said VLIWs are conditionally branching parcels that branch to said second instruction;

each one of said parcels having a plurality of fields including a multipurpose field;

storing a branch-to address indicator, pointing toward an address of a third instruction to which said first instruction conditionally will branch, in said multipurpose field of said first parcel; and

storing a branch-to address indicator, indicating an address of said second instruction, in said multipurpose field of said second parcel.

32. The method of claim 31, further comprising:

writing to said multipurpose fields independently such that, for a given first instruction, a new branch-to address indicator independently can be stored in said second field to replace an old branch-to address indicator and so reflect a revised prediction.

33. The method of claim 32, wherein a basic unit of storage in said first cache is a line, and said multipurpose fields are sized to store only as many bits as are necessary to uniquely identify one of said basic units of storage in said first cache.