Browse Prior Art Database

Method for the dynamic prediction of nonsequential memory accesses

IP.com Disclosure Number: IPCOM000009888D
Publication Date: 2002-Sep-25
Document File: 3 page(s) / 100K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method for a software mechanism for the dynamic prediction of nonsequential memory accesses. Benefits include improved performance.

This text was extracted from a Microsoft Word document.
This is the abbreviated version, containing approximately 41% of the total text.

Method for the dynamic prediction of nonsequential memory accesses

Disclosed is a method for a software mechanism for the dynamic prediction of nonsequential memory accesses. Benefits include improved performance.

Background

              Multiple linked lists are conventionally implemented. Each node can contain pointers linking several nodes ahead and behind in the traversal order. Prefetch or speculative load operations may be used to improve performance during traversal. However, the implementation would bear the overhead of maintaining correct pointers whenever nodes are manipulated within the data structure. The conventional solution does not use past traversal history to predict future memory accesses. The time spent waiting for nodes to be loaded from memory is often the limiting factor in how fast the software can be executed.

              Recursive data structures are typically dynamic. Nodes are inserted in, removed from, or reordered within the data structure. The order of traversal may not be constant, and static prefetch pointers are of limited use.

General description

              The disclosed method is the use of dynamic prefetch pointers to predict and load memory access locations during the processing of recursive data structures, such as linked lists, trees, and graphs. The method improves the performance of the traversal of recursive data structures by loading the memory addresses several iterations ahead, even as the aggregate data structure changes over time, reducing the time spent waiting for memory accesses to complete.

              A key performance limiter in dynamic operations is the time the computer takes to load from memory the address of the next node to be traversed in the data structure, particularly if that node is not already in cache. The disclosed method enables the software to predict probable future memory access locations and request that these locations be loaded for likely future use. The method detects when prefetch pointers differ from the actual sequence of memory accesses and uses that information to predict the memory accesses of future traversals of the data structure.

              An incorrect prefetch pointer must not inhibit the correct functioning of the application. Several modern microprocessor architectures support prefetch or speculative load operations that can be used to efficiently meet this requirement. If speculative load operations are not supported, the prefetch pointer may still be used but with additional processing to verify the pointer returns a valid memory location.

              The key components of the method include:

•             Each node in the data structure contains one or more prefetch pointers that predict a probable future memory access of the application.

•             Prefetch pointers are maintained, based on the sequence of nodes visited during execution of the software.

Advantages

              The disclosed method provides advantages, including:

•             Improved performance due...