Uncovering and Exploiting Memory Parellelism in Pointer-Chasing Applications

Proposal：C-CR 0000988PI：Donald Yeung，马里兰大学的Donald Yeung传统的内存延迟容错技术仅限于指针密集型应用程序，因为指针追逐内存引用必须按顺序执行，并防止多个高速缓存未命中的重叠。然而，指针追逐计算会遍历几个独立的指针链。这种独立的遍历提供了一个内存并行性的来源，这是现有的延迟容忍技术所没有利用的。该研究开发了新的指针预取技术来利用“链间”内存并行。与现有技术相比，新技术更有效地解决了非数值应用程序中常见的指针跟踪计算的内存瓶颈。这项研究包括三个主要推动力。首先，开发了跨多个独立的指针链遍历同时调度预取的技术；从而重叠了来自单独的指针追逐循环或递归函数调用的高速缓存未命中。对编译时和运行时调度技术进行了研究。其次，开发了架构支持以根据所需的预取时间表发出预取请求。首先，研究了一个能够遍历基于指针的数据结构的预取引擎。该研究还研究了在多线程CPU中执行预取的轻量级微线程。最后，开发了编译器支持，以自动提取程序信息，用于计算预取调度和在运行时生成预取请求。

ABSTRACTProposal: C-CR 0000988PI: Donald Yeung, University of MarylandConventional 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.