Harnessing Pairwise-Correlating Data Prefetching with Runahead Metadata

Recent research revisits pairwise-correlating data prefetching due to its extremely low overhead. Pairwise-correlating data prefetching, however, cannot accurately detect where data streams end. As a result, pairwise-correlating data prefetchers either expose low accuracy or they lose timeliness when they are performing multi-degree prefetching. In this letter, we propose a novel technique to detect where data streams end and hence, control the multi-degree prefetching in the context of pairwise-correlated prefetchers. The key idea is to have a separate metadata table that operates one step ahead of the main metadata table. This way, the runahead metadata table harnesses the degree of prefetching by allowing/disallowing the main metadata table to issue prefetch requests. We evaluate our proposal in the context of a four-core chip multiprocessor and show that it significantly reduces erroneous prefetches, providing up to 16.1 percent performance improvement on top of a state-of-the-art pairwise-correlating prefetcher.