Evaluation of a Data Preload Mechanism for a Linked List Structure

ABSTRACT

The authors have been developing a data preload/prefetch scheme for a linked list structure. In this paper, results of evaluating this preload scheme with benchmark programs requiring frequent pointer operations are reported. This scheme is characterized by the fact that the pointer value of a linked list is preloaded and stored, and a mechanism of providing the pointer value without delay for subsequent instructions is installed inside the processor. While dramatic performance improvement is expected by preloading / prefetching of a pointer value in this scheme, it is feared that a speculative execution using a preloaded pointer value before an update may fail if the linked list structure is modified, which may influence the performance negatively. However, it has been confirmed that in actual programs, such a failure of speculative execution does not occur, so that no performance problem arises. The evaluation results have confirmed a maximum performance improvement of 24.3% and the efficacy of the scheme.

KEYWORDS

Data Preload, Data Prefetch, Speculative Memory Access, Super Scalar Processor

RETURN!! to Mr. K. SHIBAYAMA's HOME PAGE