  We present Pangloss, an efficient high-performance data prefetcher that
approximates a Markov chain on delta transitions. With a limited information
scope and space/logic complexity, it is able to reconstruct a variety of both
simple and complex access patterns. This is achieved by a highly-efficient
representation of the Markov chain to provide accurate values for transition
probabilities. In addition, we have added a mechanism to reconstruct delta
transitions originally obfuscated by the out-of-order execution or page
transitions, such as when streaming data from multiple sources. Our
single-level (L2) prefetcher achieves a geometric speedup of 1.7% and 3.2% over
selected state-of-the-art baselines (KPCP and BOP). When combined with an
equivalent for the L1 cache (L1 & L2), the speedups rise to 6.8% and 8.4%, and
40.4% over non-prefetch. In the multi-core evaluation, there seems to be a
considerable performance improvement as well.
