Accuracy of correlation prefetching via block correlation and adaptive prefetch degree selection

A system comprising:

• a processing unit;
• a main memory configured to store instructions executable by the processing unit, and further configured to store data used by the processing unit;
• a secondary memory configured to cache instructions and/or data from the main memory;
• and
• a control unit configured to:
• generate control flow information by storing respective information for each retired instruction of one or more retired instructions;
• store a plurality of addresses by storing respective one or more addresses for each retired instruction of one or more retired instructions that incur one or more secondary memory misses;
• wherein storing the respective one or more addresses comprises storing the respective one or more addresses to an entry in a table by using an index for the entry, wherein determining the index for the entry involves using an address for an older retired instruction that incurred one or more secondary memory misses and control flow information for the older retired instruction;
• and
• for each incurred secondary memory miss, perform a prefetch operation from the main memory to the secondary memory according to:
• a respective address corresponding to the incurred secondary memory miss;
• the control flow information;
• and
• the plurality of addresses.

A method for prefetching instructions and/or data from a system memory to a cache memory, the method comprising:

• store a plurality of addresses by storing respective one or more addresses for each retired instruction of one or more retired instructions that incur one or more cache misses;
• wherein storing the respective one or more addresses comprises storing the respective one or more addresses to an entry in a first table by using a tag for the entry, wherein determining the tag for the entry involves using an address for an older retired instruction that incurred one or more cache misses and control flow information for the older retired instruction;
• and
• accessing a specified entry in the first table in response to a given cache miss, wherein the specified entry comprises a specified tag and a specified list of addresses, wherein said accessing the specified entry is performed according to a specified index comprising:
• at least a subset of bits from a specified cache miss address corresponding to the given cache miss;
• and
• additional bits representing program control flow information indicative of a specified program control flow that led to the given cache miss;
• and
• performing a prefetch operation according to the specified tag and at least a first number of respective addresses from the specified list of addresses.

A processing unit comprising:

• a processing core configured to execute instructions stored in a main memory;
• one or more levels of cache memory for caching instructions and/or data from the main memory;
• a control unit configured to manage correlation prefetching for prefetching instructions and/or data from the main memory to respective cache memories of at least one of the one or more levels of cache memory, wherein the control unit comprises:
• a first buffer configured to store program control flow information corresponding to retired branch instructions;
• and
• a second buffer configured to store cache miss addresses corresponding to retired branch instructions that incur a cache miss;
• wherein the control unit is configured to store a plurality of addresses by storing respective one or more addresses for each retired instruction of one or more retired instructions that incur one or more secondary memory misses;
• wherein storing the respective one or more addresses comprises storing the respective one or more addresses to an entry in a table by using an index for the entry, wherein determining the index for the entry involves using an address for an older retired instruction that incurred one or more secondary memory misses and control flow information for the older retired instruction;
• and
• wherein the control unit is configured to perform a memory prefetch operation according to the stored program control flow information and the stored cache miss addresses each time a cache miss is incurred for the respective cache memories of the at least one of the one or more levels of cache memory.