Prefetching indirect array accesses
US7539844B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Jun 24, 2008 |
| Grant date | May 26, 2009 |
| Priority date | — |
| Expiry date | Jun 24, 2028 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F2212/6024
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
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≦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 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, w…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.