Uncovering and Exploiting Memory Parellelism in Pointer-Chasing Applications

摘要：C-CR 0000988PI: Donald Yeung， University of maryland，传统的内存延迟容忍技术在指针密集型应用中受到限制，因为指针跟踪内存引用必须顺序执行，并且防止多个缓存丢失重叠。然而，指针追踪计算需要遍历几个独立的指针链。这种独立遍历提供了一种内存并行性来源，而现有的延迟容忍技术尚未利用这种资源。本研究开发了新的指针预取技术来利用“链间”内存并行性。与现有技术相比，新技术更有效地解决了在非数值应用程序中常见的指针跟踪计算的内存瓶颈。这项研究包括三个主要重点。首先，开发了同时跨多个独立指针链遍历调度预取的技术；因此，由于单独的指针跟踪循环或递归函数调用而重叠缓存缺失。本文研究了编译时和运行时调度技术。其次，开发了架构支持，根据所需的预取计划发出预取请求。首先，研究了一种能够遍历指针数据结构的预取引擎。该研究还研究了在多线程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.