Prefetch mechanisms by application memory access pattern
Abstract
Modern computer systems spend a substantial fraction of their running time waiting for data from memory. While prefetching has been a promising avenue of research for reducing and tolerating latencies to memory, it has also been a
challenge to implement. This
challenge exists largely because of the growing
complexity of memory hierarchies and the wide variety of application behaviors.
In this dissertation we propose a new methodology that emphasizes decomposing
complex behavior at the application level into regular components
that are intelligible at a high level to the architect.
This dissertation is divided into three stages. In the first, we build tools to help decompose application behavior by data structure and phase,
and use these tools to create a richer picture of application behavior than with
conventional simulation tools, yielding
compressed summaries of dominant
access patterns. The variety of a
access patterns drives the next stage: design
of a prefetch system that improves on the state of the art.
Every prefetching system must make low-overhead decisions on what
to prefetch, when to prefetch it, and where to store prefetched data. Visualizing
application a
access patterns allows us to articulate the subtleties in making
these decisions and the many ways that a mechanism that improves one decision for one set of applications may degrade the quality of another decision
for a different set. Our insights lead us to a new system
called TwoStep with
a small set of independent but synergistic
mechanisms.
In the third stage we perform a detailed evaluation of TwoStep. We
find that while it outperforms past approaches for the most irregular applications
in our benchmark suite, it is unable to improve on the speedups for more
regular applications. Understanding why leads to an improved understanding
of two general
categories of prefetch techniques. Prefetching
an either look
back at past history or look forward by precomputing an application's future
requirements. Applications with a low
compute-a
ccess ratio
an benefit from
history-based prefetching if their access pattern is not too irregular. Applications
with irregular access patterns may benefit from precomputation-based
prefetching, as long as their
compute-access ratio is not too low.
Department
Description
text