Way prediction unit and a method for operating the same

A mechanism for predicting the way of an instruction cache containing a block of instructions currently being fetched and for predicting the index of a next block of instructions required by a program, comprising:

• a fetch control unit configured to produce a fetch address and an update value wherein said update value includes an update way value, and wherein said fetch control unit is coupled to receive a next fetch address and a current way value;
• a way prediction unit coupled to said fetch control unit wherein said way prediction unit is coupled to receive said fetch address and said update value from said fetch control unit, and wherein said way prediction unit includes an array including a plurality of storage locations wherein each of said plurality of storage locations is configured to store a plurality of branch prediction addresses and a way value, and wherein said array further includes a mechanism to select one of said plurality of storage locations indexed by said fetch address, and
• wherein said way prediction unit is configured to convey an output address and an output way value, and wherein said output address and said output way value are conveyed to fetch control unit, and wherein said output address is said next fetch address, and wherein said output way value is said current way value, and wherein said way prediction unit concurrently provides said output address corresponding to said fetch address and said output way value corresponding to said fetch address;
• and
• an instruction cache configured to store blocks of contiguous instruction bytes wherein said instruction cache is coupled to receive said fetch address from said fetch control unit concurrent with said way prediction unit receiving said fetch address and is further coupled to receive said current way value, and wherein said instruction cache selects said block of instructions in response to said fetch address and said current way value, and wherein said block of instructions includes a branch instruction corresponding to one of said plurality of branch predictions, and wherein said one of said plurality of branch prediction is stored within said one of said plurality of storage locations indexed by said fetch address;
• wherein said fetch control unit is configured to validate said next fetch address and said current way value provided in a clock cycle wherein said validate occurs in a first subsequent clock cycle following said clock cycle, and wherein said next fetch address and said current way value are validated if said previous fetch address is a bit in said instruction cache in a way equal to said current way value and if index bits of a branch prediction generated from a plurality of instruction stored at said previous fetch address matches index bits of said next fetch address, and wherein said fetch control unit generates a corrected fetch address if said next fetch address and said current way value are not validated as correct.

A mechanism for performing way prediction and branch prediction comprising:

• a fetch control unit configured to generate a fetch address during a first clock cycle;
• an instruction cache coupled to receive said fetch address from said fetch control unit during said first clock cycle, wherein said instruction cache is configured to store a cache line of instruction bytes corresponding to said fetch address within one of a plurality of cache line storage locations indexed by said fetch address, and wherein said cache line of instructions bytes includes a branch instruction;
• and
• a branch prediction unit configured to store a first plurality of branch prediction addresses, a second plurality of branch prediction addresses, and a plurality of way predictions, wherein said branch prediction unit is coupled to receive said fetch address from said fetch control unit during said first clock cycle, and wherein said branch prediction unit is configured to select one of said first plurality of branch prediction addresses, one of said second plurality of branch prediction addresses, and one of said plurality of way predictions in response to said fetch address, and wherein either said one of first plurality of branch prediction addresses or said one of said second plurality of branch prediction addresses corresponds to said branch instruction;
• a way prediction storage including a plurality of storage locations wherein each of said plurality of storage locations is configured to store a branch prediction address and a way value identifying a first way of said instruction cache, and wherein said way prediction storage further includes a mechanism to select one of said plurality of storage locations indexed by an input address, whereby a first branch prediction address corresponding to said input address and a first way values corresponding to aid input address are concurrently provided;
• an address selection device coupled to said way prediction storage, wherein said address selection device is configured to select an address from said group of addresses stored within said one of said storage locations, and wherein said selection device receives plurality of selection control bits, and wherein said plurality of selection controls bits control said selection by said address selection device;
• wherein said instruction is configured to select which one of said plurality of cache line storage locations is storing said cache line of instruction bytes in response to said one of said plurality of way predictions.