Data prefetcher with complex stride predictor

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

• queuing strides associated with a stream of temporally adjacent load requests from the same memory page into a hardware queue of indexed storage elements, wherein each of the queued strides is a difference between cache line offsets of memory addresses of respective adjacent load requests of the stream;
• calculating a current stride between a current load request and a newest previous load request of the stream, wherein the current stride is a difference between cache line offsets of the memory addresses of the current load request and the newest previous load request;
• comparing the current stride and a stride M in the queue;
• comparing the newest of the queued strides with a queued stride M+1, wherein stride M+1 is older than and adjacent to stride M in the queue;
• when the current stride matches stride M and the newest queued stride matches stride M+1, prefetching into the cache memory a cache line whose offset within the memory page is the sum of the offset of the current load request and a stride M−1, wherein stride M−1 is newer than and adjacent to stride M in the queue.

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

• computer readable program code embodied in said medium, for specifying a hardware data prefetcher, the computer readable program code comprising:
• first program code for specifying a queue of indexed storage elements, into which are queued strides associated with a stream of temporally adjacent load requests from the same memory page into wherein each of the queued strides is a difference between cache line offsets of memory addresses of respective adjacent load requests of the stream;
• and
• second program code for specifying hardware logic, configured to:
• calculate a current stride between a current load request and a newest previous load request of the stream, wherein the current stride is a difference between cache line offsets of the memory addresses of the current load request and the newest previous load request;
• compare the current stride and a stride M in the queue;
• compare the newest of the queued strides with a queued stride M+1, wherein stride M+1 is older than and adjacent to stride M in the queue;
• when the current stride matches stride M and the newest queued stride matches stride M+1, prefetch into the cache memory a cache line whose offset within the memory page is the sum of the offset of the current load request and a stride M−1, wherein stride M−1 is newer than and adjacent to stride M in the queue.