Patent ID: 7383418

Claim:
A method for prefetching data to a lower level cache in the event of a miss to the lower level cache and a subsequent hit to a next level cache memory comprising: comparing a linear address that has been hashed to a plurality of entries in a prefetch match queue; if the comparison is a miss to the prefetch match queue, incrementing and decrementing the linear address and hashing both incremented and decremented addresses and storing entries in the prefetch match queue for the hashed incremented and decremented addresses and updating a PlusMinus vector with a first value for the incremented address and updating the PlusMinus vector with a second value for the decremented address; and if instead the comparison is a hit to the prefetch match queue, incrementing or decrementing the linear address based on a value of the PlusMinus Vector, wherein the lower level cache is closer to an execution unit than the next level cache memory, and wherein the hashing is as follows: DEFINE PREFETCH HASH 42 TO 10(Hash, LA) =[ Hash[ 9 ]:=LA[ 47 ]XOR LA[ 37 ]XOR LA[ 27 ]XOR LA[ 17 ]XOR LA[ 10 ]; Hash[ 8 ]:=LA[ 46 ]XOR LA[ 36 ]XOR LA[ 26 ]XOR LA[ 16 ]XOR LA[ 09 ]; Hash[ 7 ]:=LA[ 45 ]XOR LA[ 35 ]XOR LA[ 25 ]XOR LA[ 15 ]; Hash[ 6 ]:=LA[ 44 ]XOR LA[ 34 ]XOR LA[ 24 ]XOR LA[ 14 ]; Hash[ 5 ]:=LA[ 43 ]XOR LA[ 33 ]XOR LA[ 23 ]XOR LA[ 13 ]; Hash[ 4 ]:=LA[ 42 ]XOR LA[ 32 ]XOR LA[ 22 ]XOR LA[ 12 ]; Hash[ 3 ]:=LA[ 41 ]XOR LA[ 31 ]XOR LA[ 21 ]XOR LA[ 11 ]; Hash[ 2 ]:=LA[ 40 ]XOR LA[ 30 ]XOR LA[ 20 ]XOR LA[ 08 ]; Hash[ 1 ]:=LA[ 39 ]XOR LA[ 29 ]XOR LA[ 19 ]XOR LA[ 07 ]; Hash[ 0 ]:=LA[ 38 ]XOR LA[ 28 ]XOR LA[ 18 ]XOR LA[ 06 ]]; wherein LA corresponds to a linear address, Hash is a resulting bit of the hashing and numbers in the square brackets correspond to respective bits of the LA or the hash.