A method for prefetching data from an array, A, the method including:
detecting a stride, dB, of a stream of index addresses of an indirect
array, B, contents of each index address having information for
determining an address of an element of the array A; detecting an access
pattern from the indirect array, B, to data in the array, A, wherein the
detecting an access pattern includes: 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.ltoreq.j.ltoreq.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 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.