Skip to Content
Find More Like This
Return to Search

Method for prefetching non-contiguous data structures

United States Patent

May 5, 2009
View the Complete Patent at the US Patent & Trademark Office
Lawrence Livermore National Laboratory - Visit the Industrial Partnerships Office Website
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.
Blumrich; Matthias A. (Ridgefield, CT), Chen; Dong (Croton On Hudson, NY), Coteus; Paul W. (Yorktown Heights, NY), Gara; Alan G. (Mount Kisco, NY), Giampapa; Mark E. (Irvington, NY), Heidelberger; Philip (Cortlandt Manor, NY), Hoenicke; Dirk (Ossining, NY), Ohmacht; Martin (Brewster, NY), Steinmacher-Burow; Burkhard D. (Mount Kisco, NY), Takken; Todd E. (Mount Kisco, NY), Vranas; Pavlos M. (Bedford Hills, NY)
International Business Machines Corporation (Armonk, NY)
11/ 617,276
December 28, 2006
This invention was made with Government support under subcontract number B517552 under prime contract number W-7405-ENG-48 awarded by the Department of Energy. The Government has certain rights in this invention.