Uncovering and Exploiting Memory Parellelism in Pointer-Chasing Applications

University Of Maryland, College Park, College Park MD

Investigators

Abstract

ABSTRACT Proposal: C-CR 0000988 PI: Donald Yeung, University of Maryland Conventional memory latency tolerance techniques are limited on pointer-intensive applications because pointer-chasing memory references must perform sequentially and prevent the overlap of multiple cache misses. Pointer-chasing computations, however, traverse several independent pointer chains. Such independent traversals provide a source of memory parallelism that has remained untapped by the existing latency tolerance techniques. This research develops novel pointer prefetching techniques to exploit "inter-chain" memory parallelism. Compared to existing techniques, the new techniques address more effectively the memory bottleneck for pointer-chasing computations commonly found in non-numeric applications. The research consists of three major thrusts. First, techniques are developed to schedule prefetches across multiple independent pointer-chain traversals simultaneously; thus overlapping cache misses from separate pointer-chasing loops or recursive function calls. Both compile-time and run-time scheduling techniques are investigated. Second, architectural support is developed to issue prefetch requests according to the required prefetch schedules. Initially, a prefetch engine capable of traversing pointer-based data structures is studied. The research also investigates into lightweight microthreads to perform prefetching inside a multithreaded CPU. Finally, compiler support is developed to automatically extract program information for computing the prefetch schedules and for generating the prefetch requests at runtime.