Uncovering and Exploiting Memory Parellelism in Pointer-Chasing Applications

摘要建议：C-CR 0000988 PI：Donald Yeung，马里兰大学传统的内存延迟容忍技术在指针密集型应用程序上受到限制，因为指针追踪内存引用必须顺序执行，并防止多个缓存未命中的重叠。 然而，指针追踪计算会遍历几个独立的指针链。 这种独立的遍历提供了一个来源的内存并行性，一直未被现有的延迟tolerance.This研究开发新的指针预取技术，利用“链间”的内存并行性。 与现有技术相比，新技术更有效地解决了非数值应用程序中常见的指针追逐计算的内存瓶颈。 这项研究包括三个主要方面。 首先，开发了同时跨多个独立指针链遍历调度预取的技术;从而重叠来自单独指针追逐循环或递归函数调用的缓存未命中。 编译时和运行时调度技术进行了研究。 第二，开发架构支持，以根据所需的预取时间表发出预取请求。 首先，研究了一种能够遍历基于指针的数据结构的预取引擎。该研究还调查了轻量级微线程在多线程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.