Method for prefetching non-contiguous data structures

• US 7,529,895 B2
• Filed: 12/28/2006
• Issued: 05/05/2009
• Est. Priority Date: 08/22/2003
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chen, Dong, Gara, Alan G., Ohmacht, Martin, Heidelberger, Philip, Giampapa, Mark E., Blumrich, Matthias A., Coteus, Paul W., Hoenicke, Dirk, Takken, Todd E., Vranas, Pavlos M., Steinmacher-Burow, Burkhard D.
• Primary Examiner(s): NGUYEN, THAN VINH
• Application Number:
  US11/617,276
• Publication Number:
  US 20070204112A1
• Time in Patent Office: 859 Days
• Field of Search: None
• US Class Current: 711/151
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 2212/6028 Prefetching based on hints or prefetch instructions
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A low latency memory system access is provided in association with a weakly-ordered multiprocessor system. Each processor in the multiprocessor shares resources, and each shared resource has an associated lock within a locking device that provides support for synchronization between the multiple processors in the multiprocessor and the orderly sharing of the resources. A processor only has permission to access a resource when it owns the lock associated with that resource, and an attempt by a processor to own a lock requires only a single load operation, rather than a traditional atomic load followed by store, such that the processor only performs a read operation and the hardware locking device performs a subsequent write operation rather than the processor. A simple perfecting for non-contiguous data structures is also disclosed. A memory line is redefined so that in addition to the normal physical memory data, every line includes a pointer that is large enough to point to any other line in the memory, wherein the pointers to determine which memory line to prefect rather than some other predictive algorithm. This enables hardware to effectively prefect memory access patterns that are non-contiguous, but repetitive.

Claims

1. A method of prefetching non-contiguous data structures stored in non-contiguous memory locations but accessed repeatedly in a same order, said method comprising:

embedding pointers in each data structure to point to and indicate the access order of the non-contiguous data structures;

prefetching the target data structures based on the access order indicated by the pointers,

said prefetching being based on memory lines, where a memory line is an aligned section of contiguous physical memory locations, such that the memory is divided into lines, said memory lines being stored in at least one cache memory device at any given time, and wherein each memory line includes;

physical memory data, a pointer sufficient to point to any other memory line in the cache memory, and, additional bits to indicate the status of the pointer; and

,

setting and using the pointers automatically for said pre-fetching, wherein said setting of the pointers comprises;

accessing a memory line, and, if the memory line status indicates a non-valid pointer, promoting the memory line to parent status, and designating the next memory line that is demand fetched as its child, and, modifying the pointer of the parent memory line to point to the child memory line;

recursively accessing and promoting status of said memory lines so that a child memory line is also designated as a parent memory line of another subsequent memory line; and

,

providing a content-addressable prefetch table that keeps track of parent-child pointer relationships, said table having three fields;

a parent, child, and a status field,

wherein when a memory line is fetched and it has an invalid pointer, the next memory line to be fetched is designated as its child, the parent'"'"'s pointer is set to the child memory line, and the pointer status is set to probationary, and when a line is fetched or prefetched with a known pointer, then the child memory line pointed to is immediately prefetched, and

when a memory line with a probationary or known pointer is fetched and it is not found as a parent memory line in the prefetch table, then it is entered into the table along with its child pointer and pointer status, and,

when a memory line is referenced, comparing the memory line address to all the child pointers in said prefetch table, and if a match is found, updating the associated parent'"'"'s status and said probationary pointer is upgraded to known status, and removing the matching entry in the prefetch table, and if more than one child entry is matched, handling each child entry in the same manner.