Patent ID: 7539844

Claim:
A method for prefetching data from an array, A, the method comprising: detecting a stride, dB, of a stream of index addresses of an indirect array, B, contents of each index address comprising information for determining an address of an element of the array A wherein the detecting a stride comprises: executing a load instruction to load bi at instruction address, ia, a first time and receiving a first memory access address; executing the load instruction a second time and receiving a second memory access address; and recording a difference between the first memory access address and the second memory access address as the stride, dB; detecting an access pattern from the indirect array, B, to data in the array, A, wherein the detecting an access pattern comprises: using a constant value of an element size, dA; using a domain size k; executing a load instruction to load bi at address, ia, and receiving index data, mbi; multiplying mbi by dA to produce the product mbi*dA; executing another load instruction to load for a column address, j, where 1≦j≦k, and receiving address aj; recording the difference, aj−mbi*dA; iterating the executing a load instruction, the multiplying, the executing another load instruction, and the recording to produce another difference; incrementing a counter by one if the difference and the another difference are the same; and confirming the column address j when the counter reaches a pre-determined threshold; executing a load instruction to load bi+dB and receiving index data nextmbi; and executing a load instruction to load Aj+nextmbi*dA, where Aj=(aj−mbi*dA) when the column address j is confirmed to prefetch the data from the array, A.