Practical Temporal Prefetching With Compressed On-Chip Metadata

Temporal prefetchers are powerful because they can prefetch irregular sequences of memory accesses, but temporal prefetchers are commercially infeasible because they store large amounts of metadata in DRAM. This article presents Triage, the first temporal data prefetcher that does not require off-chip metadata. Triage builds on two insights: (1) Metadata are not equally useful, so the less useful metadata need not be saved, and (2) for irregular workloads, it is more profitable to use portions of the LLC to store metadata than data. We also introduce novel schemes to identify useful metadata, to compress metadata, and to determine the fraction of the LLC to dedicate for metadata. Using an industrial-strength simulator running irregular workloads on a single-core system, we show that at a prefetch degree of 4, Triage improves performance by 41.1 percent compared to a baseline with no prefetching, whereas BO, a state-of-the-art prefetcher that uses only on-chip metadata, sees only 10.9 percent improvement. Compared with MISB, a temporal prefetcher that uses off-chip metadata, Triage provides a design alternative that reduces memory traffic by an order of magnitude (260.8 percent extra traffic for MISB at degree 1 versus 56.9 percent for Triage), while reducing coverage by 20 percent.