Branch prediction mechanism using multiple hash functions

Abstract

In one embodiment, the branch prediction mechanism includes a first storage including a first plurality of locations for storing a first set of partial prediction information. The branch prediction mechanism also includes a second storage including a second plurality of locations for storing a second set of partial prediction information. Further, the branch prediction mechanism includes a control unit that performs a first hash function on input branch information to generate a first index for accessing a selected location within the first storage. The control unit also performs a second hash function on the input branch information to generate a second index for accessing a selected location within the second storage. Lastly, the control unit further provides a prediction value based on corresponding partial prediction information in the selected locations of the first and the second storages.

1 . A branch prediction mechanism comprising: 
 a first storage including a first plurality of locations for storing a first set of partial prediction information;    a second storage including a second plurality of locations for storing a second set of partial prediction information; and    a control unit configured to perform a first hash function on input branch information to generate a first index for accessing a selected location within said first storage and to perform a second hash function on said input branch information to generate a second index for accessing a selected location within said second storage;    wherein said control unit is further configured to provide a prediction value based on corresponding partial prediction information in said selected locations of said first and said second storages.    
   
   
       2 . The branch prediction mechanism as recited in  claim 1 , wherein said prediction value provides a strongly/weakly taken/not taken branch prediction indication that is indicative of whether a current branch instruction is taken upon execution.  
   
   
       3 . The branch prediction mechanism as recited in  claim 1 , wherein said input branch information includes branch history information corresponding to an outcome of a number of preceding branch instructions.  
   
   
       4 . The branch prediction mechanism as recited in  claim 3 , wherein each of said first hash function and said second hash function is configured to operate on a portion of said branch history information.  
   
   
       5 . The branch prediction mechanism as recited in  claim 1 , wherein said input branch information includes address information corresponding to a fetch address of a current branch instruction.  
   
   
       6 . The branch prediction mechanism as recited in  claim 5 , wherein each of said first hash function and said second hash function is configured to operate on a portion of said fetch address.  
   
   
       7 . The branch prediction mechanism as recited in  claim 1 , wherein each of said first and said second sets of partial prediction information includes a plurality of counter values each corresponding to a strongly/weakly taken/not taken branch prediction indication that is indicative of whether a current branch instruction is taken upon execution.  
   
   
       8 . The branch prediction mechanism as recited in  claim 7 , wherein said control unit is further configured to use said prediction value to determine whether a current branch instruction is taken upon execution, wherein said prediction value is generated by summing respective counter values stored within said selected location within said first storage and said selected location within said second storage.  
   
   
       9 . The branch prediction mechanism as recited in  claim 1 , wherein said control unit is further configured to use said prediction value to control whether a branch prediction is performed in accordance with a branch prediction hint encoded within a current branch instruction.  
   
   
       10 . The branch prediction mechanism as recited in  claim 9 , wherein each of said first and said second sets of partial prediction information includes a plurality of counter values each corresponding to a strongly/weakly agree/disagree indication that is indicative of whether said branch prediction hint bit embedded within said current branch instruction is to be used by said control unit.  
   
   
       11 . The branch prediction mechanism as recited in  claim 10 , wherein said prediction value is generated by summing respective counter values stored within said selected location within said first storage and said selected location within said second storage.  
   
   
       12 . The branch prediction mechanism as recited in  claim 1 , wherein said control unit is further configured to update said selected locations of said first and said second storages dependent on whether said prediction value yields an accurate branch prediction.  
   
   
       13 . The branch prediction mechanism as recited in  claim 1  further comprising a third storage including a third plurality of locations for storing a third set of partial prediction information and wherein said control unit is further configured to perform a third hash function on input branch information to generate a third index for accessing a selected location within said third storage.  
   
   
       14 . A method of predicting branches, said method comprising: 
 storing a first set of partial prediction information within a first storage including a first plurality of locations;    storing a second set of partial prediction information within a second storage including a second plurality of locations;    performing a first hash function on input branch information to generate a first index for accessing a selected location within said first storage and performing a second hash function on said input branch information to generate a second index for accessing a selected location within said second storage; and    providing a prediction value based on corresponding partial prediction information in said selected locations of said first and said second storages.    
   
   
       15 . The method as recited in  claim 14 , wherein said prediction value provides a strongly/weakly taken/not taken branch prediction indication that is indicative of whether a current branch instruction is taken upon execution.  
   
   
       16 . The method as recited in  claim 14 , wherein said input information includes branch history information corresponding to an outcome of a number of preceding branch instructions.  
   
   
       17 . The method as recited in  claim 16  further comprising each of said first hash function and said second hash function operating on a portion of said branch history information.  
   
   
       18 . The method as recited in  claim 14 , wherein said input information includes branch address information corresponding to a fetch address of a current branch instruction.  
   
   
       19 . The method as recited in  claim 18  further comprising each of said first hash function and said second hash function operating on a portion of said branch address information.  
   
   
       20 . The method as recited in  claim 14 , wherein each of said first and said second sets of partial prediction information includes a plurality of counter values each corresponding to a strongly/weakly taken/not taken branch prediction indication that is indicative of whether a current branch instruction is taken upon execution.  
   
   
       21 . The method as recited in  claim 20  further comprising using said prediction value to determine whether a current branch instruction is taken upon execution and generating said prediction value by summing respective counter values stored within said selected location within said first storage and said selected location within said second storage.  
   
   
       22 . The method as recited in  claim 14  further comprising controlling whether a branch prediction is performed in accordance with a branch prediction hint encoded within a current branch instruction using said prediction value.  
   
   
       23 . The method as recited in  claim 22 , wherein each of said first and said second sets of partial prediction information includes a plurality of counter values each corresponding to a strongly/weakly agree/disagree indication that is indicative of whether said branch prediction hint bit embedded within said current branch instruction is to be used by said control unit.  
   
   
       24 . The method as recited in  claim 23  further comprising generating said prediction value by summing respective counter values stored within said selected location within said first storage and said selected location within said second storage.  
   
   
       25 . The method as recited in  claim 14  further comprising updating said selected locations of said first and said second storages dependent on whether said prediction value yields an accurate branch prediction.  
   
   
       26 . The method as recited in  claim 14  further comprising storing a third set of partial prediction information within a third storage including a third plurality of locations and performing a third hash function on input branch information to generate a third index for accessing a selected location within said third storage.  
   
   
       27 . A branch prediction mechanism comprising: 
 means for storing a first set of partial prediction information within a first storage including a first plurality of locations;    means for storing a second set of partial prediction information within a second storage including a second plurality of locations;    means for performing a first hash function on input branch information to generate a first index for accessing a selected location within said first storage and performing a second hash function on said input branch information to generate a second index for accessing a selected location within said second storage; and    means for providing a prediction value based on corresponding partial prediction information in said selected locations of said first and said second storages.