Skip to main content
Journal cover image

A programmable memory hierarchy for prefetching linked data structures

Publication ,  Conference
Yang, CL; Lebeck, A
Published in: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
December 1, 2002

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.

Duke Scholars

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

ISBN

9783540436744

Publication Date

December 1, 2002

Volume

2327 LNCS

Start / End Page

160 / 174

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Yang, C. L., & Lebeck, A. (2002). A programmable memory hierarchy for prefetching linked data structures. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 2327 LNCS, pp. 160–174). https://doi.org/10.1007/3-540-47847-7_15
Yang, C. L., and A. Lebeck. “A programmable memory hierarchy for prefetching linked data structures.” In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2327 LNCS:160–74, 2002. https://doi.org/10.1007/3-540-47847-7_15.
Yang CL, Lebeck A. A programmable memory hierarchy for prefetching linked data structures. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2002. p. 160–74.
Yang, C. L., and A. Lebeck. “A programmable memory hierarchy for prefetching linked data structures.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2327 LNCS, 2002, pp. 160–74. Scopus, doi:10.1007/3-540-47847-7_15.
Yang CL, Lebeck A. A programmable memory hierarchy for prefetching linked data structures. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2002. p. 160–174.
Journal cover image

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

ISBN

9783540436744

Publication Date

December 1, 2002

Volume

2327 LNCS

Start / End Page

160 / 174

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences