Prefetching Linked Data Structures in Systems with Merged DRAM-Logic

Recent advances in integrating logic and DRAM on the same chip potentially open up new avenues for addressing the long-standing problem of tolerating memory latency. This thesis exploits merged DRAM-logic technology to hide latency incurred by inherently serial accesses to linked data struc-tures (LDS). We propose a programmable prefetch engine that sits close to memory and traverses LDS independently from the processor. The prefetch engine can run ahead of the processor because of its low latency, high bandwidth path to memory. This allows the prefetch engine to initiate data transfers much earlier than the processor and pipeline multiple such transfers over the network. We evaluate the proposed memory-side prefetching scheme for the pointer-intensive Olden bench-mark suite, comparing both to a system without any prefetching and to a system with a state-of-the-art processor-side software prefetching scheme for LDS. For the six benchmarks where LDS memory stall time is signicant, the proposed memory-side scheme reduces execution time by an average of 27 % (range of 0 % to 62%) compared to a system without any prefetching. Compared to processor-side prefetching, the memory-side scheme reduces execution time in the range of 20 % to 50 % for three of the six applications, is about the same for two applications, and is worse by 18