Multi-tier cache placement mechanism

1. A method for guiding placement of data blocks in a cache system, comprising:

executing a memory instruction to access data associated with a first data address in a memory, the memory instruction having a first instruction identifier, where the data associated with the first data address is not stored in a cache of the cache system;

accessing a prediction table dependent upon the first instruction identifier to retrieve reuse data associated with the memory instruction and the cache;

retrieving a data block containing the data associated with the first data address from a lower order cache of the multi-tier cache or the memory; and

inserting the data block into one or more caches of the cache system or bypassing the cache system dependent upon the reuse data.

2. The method of claim 1 , where an entry in the prediction table comprises an instruction identifier and, for each cache of the cache system, a reuse counter, the method further comprising:

executing the memory instruction to access data associated with a second data address, where the data associated with the second data address is stored in the cache of the cache system;

responsive to executing the memory instruction to access the data associated with the second data address, incrementing the reuse counter in an entry of the prediction table associated with the first instruction identifier and the cache; and

responsive to executing the memory instruction to access the data associated with the first data address, decrementing the reuse counter in the entry of the prediction table associated with the first instruction identifier and the cache.

3. The method of claim 1 , where an entry in the prediction table comprises an instruction identifier, a probabilistic data structure and, for each cache of the cache system, a reuse counter, the method further comprising:

adding an identifier of the first data address to the probabilistic data structure of a first entry in the prediction table associated with the first instruction identifier;

evicting data associated with a second data address from the cache of the cache system;

identifying a second entry of the prediction table for which an identifier of the second data address is stored in the probabilistic data structure;

incrementing the reuse counter associated with the cache in the second entry of the prediction table when data at the second data address has been reused in the cache; and

decrementing the reuse counter associated with the cache in the second entry of the prediction table when data at the second data address has not been reused in the cache.

4. The method of claim 3 , further comprising:

inserting the data block into a cache line in a cache of the cache system, the cache line comprising an address tag, a data block, and a reuse bit;

setting the reuse bit to zero when the cache line is inserted into a cache of the cache system;

setting the reuse bit to one when the cache line is reused; and

determining data at the second data address to have been reused or not dependent upon the reuse bit in an evicted cache line containing the data at the second data address.

5. The method of claim 3 , further comprising:

deleting the second data address from the probabilistic data structure of the second entry; and

removing the second entry from the prediction table when the probabilistic data structure is empty.

6. The method of claim 1 , where an entry in the prediction table comprises an instruction identifier and, for each cache of the cache system, a reuse counter and a prediction result.

7. The method of claim 6 , further comprising:

updating a prediction result in an entry of the prediction table when a corresponding reuse counter crosses a threshold value.

8. The method of claim 6 , further comprising:

periodically updating a prediction result in an entry of the prediction table dependent upon a corresponding reuse counter.

9. The method of claim 6 , further comprising storing a prediction result in backing memory.

10. The method of claim 6 , further comprising storing a prediction result in a metadata region of an instruction stored in a backing memory.

11. The method of claim 9 , further comprising storing a prediction result in backing memory when an associated instruction is evicted from an instruction cache.

12. The method of claim 1 , further comprising:

adding a new entry to the prediction table for the first instruction identifier;

setting an instruction identifier of the entry to the first instruction identifier; and

resetting reuse data of the entry.

13. The method of claim 12 , further comprising:

evicting a least recently used entry from the prediction table; and

replacing the evicted entry with the new entry.

14. The method of claim 13 , further comprising:

saving a result of the evicted entry in a metadata region of a backing memory.

15. A method for placing data in a cache system comprising one or more caches, the method comprising:

monitoring cache behavior responsive to execution of a plurality of memory instructions issued by a cache client;

storing one or more indicators of the cache behavior in entries of a prediction table, where a first entry in the prediction table is associated with an instruction identifier of a first memory instruction of the plurality of memory instructions;

detecting a cache miss of a first memory instruction:

accessing the first entry of the prediction table to retrieve an indicator of prior cache behavior in response to the first memory instruction; and

placing a data block, retrieved in response to the first memory instruction, in a cache of the one or more caches or bypassing the cache based upon the indicator of prior cache behavior.

16. The method of claim 15 , where the cache behavior is monitored when a cache line is evicted from a cache of the cache system.

17. The method of claim 15 , where the cache behavior is monitored when a memory instruction is executed.

18. The method of claim 15 , where

the cache behavior is monitored during one or more learning phases, and

placing the data block in the cache of the one or more caches or bypassing the cache based upon the indicator of prior cache behavior is performed during an inference phase and is dependent upon cache behavior monitored in a prior learning phase.

19. The method of claim 15 , where determining when a retrieved data block should be placed in a cache of the one or more caches and when the retrieved data block should bypass the cache is occasionally performed at random.