Bounding box prefetcher

A method for prefetching data into a cache memory of a microprocessor, the method comprising:

• receiving a plurality of memory accesses each to an address within a memory block, wherein the plurality of memory access addresses are non-monotonically increasing or decreasing as a function of time;
• maintaining, as the plurality of memory accesses are received, largest and smallest addresses within the memory block and counts of changes to the largest and smallest addresses;
• maintaining, as the plurality of memory accesses are received, a history of recently accessed cache lines implicated by the access addresses within the memory block;
• determining a predominant access direction based on the counts;
• determining a predominant access pattern based on the history;
• and
• prefetching into the cache memory, in the predominant access direction according to the predominant access pattern, cache lines of the memory block which the history indicates have not been recently accessed.

A computer program product encoded in at least one computer readable medium for use with a computing device, the computer program product comprising:

• computer readable program code embodied in said medium, for specifying a data prefetcher in a microprocessor having a cache memory, the computer readable program code comprising:
• wherein the data prefetcher is configured to receive a plurality of memory accesses each to an address within a memory block, wherein the plurality of memory access addresses are non-monotonically increasing or decreasing as a function of time;
• first program code for specifying a storage element;
• and
• second program code for specifying control logic, coupled to the storage element, wherein as the plurality of memory accesses are received, the control logic is configured to:
• maintain within the storage element a largest address and a smallest address of the plurality of accesses and counts of changes to the largest and smallest addresses;
• maintain a history of recently accessed cache lines implicated by the access addresses within the memory block;
• determine a predominant access direction based on the counts;
• determine a predominant access pattern based on the history;
• and
• prefetch into the cache memory, in the predominant access direction according to the predominant access pattern, cache lines of the memory block which the history indicates have not been recently accessed.

A method for prefetching data into a cache memory of a microprocessor, the method comprising:

• receiving a memory access to an address within a memory block;
• setting a bit in a bitmask associated with a cache line implicated by the address within the memory block;
• incrementing an access total counter, in response to said receiving;
• if the address is greater than a maximum pointer, updating the maximum pointer with the address and incrementing a maximum change counter;
• if the address is less than a minimum pointer, updating the minimum pointer with the address and incrementing a minimum change counter;
• computing a middle pointer as the average of the maximum and minimum pointers;
• for each of a plurality of distinct bit periods, incrementing a match counter associated with the bit period if the N bits of the bitmask to the right of the middle pointer match the N bits to the left of the middle pointer, wherein N is the number of bits in the bit period;
• determining whether a condition exists, wherein the condition comprises:
• a) the access total count is greater than a first predetermined value;
• b) the absolute value of the difference between the maximum change counter and the minimum change counter is greater than a second predetermined value;
• and
• c) the absolute value of the difference between one of the plurality of distinct match counters and all other ones of the plurality of distinct match counters is greater than a third predetermined value;
• and
• if the condition exists:
• determining an access direction as upward if the maximum change counter is greater than the minimum change counter, and determining the access direction as downward if the maximum change counter is less than the minimum change counter;
• determining an access pattern specified by the N bits to one side of the middle pointer of the bitmask, wherein N is the number of bits in the bit period associated with the largest match counter;
• and
• prefetching cache lines of the memory block into the cache memory based on the determined access direction and access pattern.

A microprocessor, comprising:

• a plurality of processing cores;
• a cache memory, shared by the plurality of processing cores, configured to receive a plurality of memory access requests each to an address within a memory block, wherein the plurality of memory access request addresses are non-monotonically increasing or decreasing as a function of time;
• and
• a data prefetcher, configured to:
• observe the plurality of memory access requests and maintain largest and smallest addresses within the memory block of the plurality of requests and counts of changes to the largest and smallest addresses;
• determine a predominant access direction based on the counts;
• and
• prefetch into the cache memory, in the predominant access direction, cache lines of the memory block which are missing in the cache memory.