Prefetching with Respect to Indirect Memory Accesses: Potential New Demands on Memory Translation
Max Malmros · Uppsala University Publications (Uppsala University) · 2024
Indirect memory accesses (IMAs, such as A[f(B[i])]), are common memory access patterns in applications like graph analysis, machine learning, and databases. An early attempt at an IMA prefetcher came in the form of IMP, which showed a promising ability to capture and thus predict such access patterns. A recent attempt by the name of Tyche showed matching, and for certain IMA benchmarks significantly improved, performance relative to IMP and other state-of-the-art IMA prefetchers. However, neither of the corresponding papers for IMP or Tyche address a potential new performance bottleneck: Provided significant prefetching with respect to IMAs, what is the resulting behaviour of the virtual to physical translation process? This thesis first summarises the general ideas of IMP and in more detail touches on the preliminary work and resulting architecture presented in Tyche's associated paper. The latter prefetcher being less of an extension of IMP and other addressed IMA prefetchers, and more a distinct approach that entails recording instruction dependencies in hardware. We then proceed to explore performance and translation behaviour while utilising the second-mentioned prefetcher, by simulating execution using a modified version of ChampSim employing traces that – in addition to standard ones – contain information regarding memory and register states. IMA workloads were obtained using the GAPS benchmark suite. While the chosen simulation method did not properly represent virtual to physical translation during prefetching, in addition to a non-ideal approach that compared Tyche to no L1D prefetching, there were still some arguably valuable insights to glean from overall behaviour. Some kernels – PageRank in particular – had the potential to be far more bottlenecked by the TLB than others when Tyche was utilised, indicating that a more thorough study of the matter should be conducted