A programmable memory hierarchy for prefetching linked data structures

Conference Paper

Prefetching is often used to overlap memory latency with computation for array-based applications. However, prefetching for pointer-intensive applications remains a challenge because of the irregular memory access pattern and pointer-chasing problem. In this paper, we use a programmable processor, a prefetch engine (PFE), at each level of the memory hierarchy to cooperatively execute instructions that traverse a linked data structure. Cache blocks accessed by the processors at the L2 and memory levels are proactively pushed up to the CPU. We look at several design issues to support this programmable memory hierarchy. We establish a general interaction scheme among three PFEs and design a mechanism to synchronize the PFE execution with the CPU. Our simulation results show that the proposed prefetching scheme can reduce up to 100% of memory stall time on a suite of pointer-intensive applications, reducing overall execution time by an average 19%. © 2002 Springer Berlin Heidelberg.

Full Text

Duke Authors

Cited Authors

  • Yang, CL; Lebeck, A

Published Date

  • December 1, 2002

Published In

Volume / Issue

  • 2327 LNCS /

Start / End Page

  • 160 - 174

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 10 (ISBN-10)

  • 354043674X

International Standard Book Number 13 (ISBN-13)

  • 9783540436744

Digital Object Identifier (DOI)

  • 10.1007/3-540-47847-7_15

Citation Source

  • Scopus