Method for apparatus for prefetching linked data structures

A method for prefetching data from a linked data structure in a computer system, said method comprising:

• traversing the linked data structure and visiting a first data node therein in search of requested data during execution of a process;
• locating, in a content addressable memory, a storage location associated with a second data node in the linked data structure which was visited prior to the first data node;
• and
• storing at the storage location associated with the second data node a data node address of the first data node as a prefetch address for the first data node.

A method for prefetching data from a linked data structure within a memory subsystem of a computer system while searching for requested data in the linked data structure, said method comprising:

• retrieving a prefetch address from a content addressable memory, the prefetch address pointing to a latter data node in the linked data structure, the latter data node being a specified number of data nodes beyond a current data node in the linked data structure;
• prefetching data from the latter data node onto a cache memory of the memory subsystem;
• storing an address of the current data node into the content addressable memory at a storage location associated with a data node which is the specified number of data nodes prior to the current data node within the linked data structure;
• incrementing the latter data node to a next latter data node and incrementing the current data node to a next current data node;
• fetching data from a data node being currently visited;
• determining if the fetched data matches the requested data;
• and
• iterating said retrieving, said prefetching, said storing, said incrementing, said fetching, and said determining until the fetched data matches the requested data.

A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform a method for prefetching data from a linked data structure in a computer system, the computer system including a processor, at least one cache memory, and a main memory, the method comprising:

• traversing the linked data structure and visiting a first data node therein in search of requested data during execution of a process;
• locating a storage location in a content addressable memory using a data node address of a second data node in the linked data structure which was visited prior to the first data node;
• and
• storing a data node address of the first data node into the content addressable memory at the storage location associated with the second data node as a prefetch address for the first data node.

A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform a method for prefetching data from a linked data structure within a memory subsystem of a computer system while searching for requested data in the linked data structure, the method comprising:

• retrieving a prefetch address from a content addressable memory, the prefetch address pointing to a latter data node in the linked data structure, the latter data node being a specified number of data nodes beyond a current data node in the linked data structure;
• prefetching data from the latter data node onto a cache memory of the memory subsystem;
• storing an address of the current data node into the content addressable memory at a storage location associated with a data node which is the specified number of data nodes prior to the current data node within the linked data structure;
• incrementing the latter data node to a next latter data node and incrementing the current data node to a next current data node;
• fetching data from a data node being currently visited;
• determining if the fetched data matches the requested data;
• and
• iterating said retrieving, said prefetching, said storing, said incrementing, said fetching, and said determining until the fetched data matches the requested.