Classifying Memory Access Patterns for Prefetching

This work proposes a novel methodology to classify the memory access patterns of applications, enabling well-informed reasoning about the applicability of a certain prefetcher.

Classification of Memory Access Patterns

The workloads become increasingly diverse and complicated. As a result, the design of a prefetcher is challenging. Although it is not possible to cover all memory access patterns, we do find some patterns appear more frequently.

Classification of Memory Access Patterns

The prefetching problem is then choosing between the above pattens. It is a classification problem!

The classification scheme of Table 1 maps memory accesses to design patterns and data structures and is useful for the human observer. However, these patterns are challenging to leverage for automated processing.

To address this issue, we formalize our approach to express prefetch patterns as follows: For a given load instruction and its function to compute the next address,f(x)can be expressed as a prefetch kernel which consists of a number of data sources and operations on those sources which generate the delinquent load address.

Machine Operations and Patterns

How to find the patterns?

There are two ways to make the observation:

  • Indirect observation: use address, history and/or program counter (PC)
  • Direct observation: extract patterns directly from programs

This paper choose direct observation. The procedure is this:

  1. identify critical cache misses
  2. rebuild the dataflow graphs for each miss-causing instruction in the application.
  3. reduce and classify