Method for apparatus for prefetching linked data structures

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 pointer-based data structure are stored and thus remembered, which allows the size of the CAM to remain relatively small and access to the CAM by the CPU, relatively fast.