Method for apparatus for prefetching linked data structures
US6687807B1 · kind B1 · utility
Assignee
Inventor
Key dates
| Filing date | Apr 18, 2000 |
| Grant date | Feb 3, 2004 |
| Priority date | — |
| Expiry date | Apr 18, 2020 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F2212/6028
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Additional memory hardware in a computer system which is distinct in function from the main memory system architecture permits the storage and retrieval of prefetch addresses and allows the compiler to more efficiently generate prefetch instructions for execution while traversing pointer-based or recursive data structures. The additional memory hardware makes up a content addressable memory (CAM) or a hash table/array memory that is relatively close in cycle time to the CPU and relatively small when compared to the main memory system. The additional CAM hardware permits the compiler to write data access loops which remember the addresses for each node visited while traversing the linked data structure by providing storage space to hold a prefetch address or a set of prefetch addresses. Since the additional CAM is separate from the main memory system and acts as an alternate cache for holding the prefetch addresses, it prevents the overwriting of desired information in the regular cache and thus leaves the regular cache unpolluted. Furthermore, rather than having the addresses for the entire memory system stored in the CAM, only the addresses to those data nodes traversed along the …
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.