  L1 instruction (L1-I) cache misses are a source of performance bottleneck.
Sequential prefetchers are simple solutions to mitigate this problem; however,
prior work has shown that these prefetchers leave considerable potentials
uncovered. This observation has motivated many researchers to come up with more
advanced instruction prefetchers. In 2011, Proactive Instruction Fetch (PIF)
showed that a hardware prefetcher could effectively eliminate all of the
instruction-cache misses. However, its enormous storage cost makes it an
impractical solution. Consequently, reducing the storage cost was the main
research focus in the instruction prefetching in the past decade. Several
instruction prefetchers, including RDIP and Shotgun, were proposed to offer
PIF-level performance with significantly lower storage overhead. However, our
findings show that there is a considerable performance gap between these
proposals and PIF. While these proposals use different mechanisms for
instruction prefetching, the performance gap is largely not because of the
mechanism, and instead, is due to not having sufficient storage. Prior
proposals suffer from one or both of the following shortcomings: (1) a large
number of metadata records to cover the potential, and (2) a high storage cost
of each record. The first problem causes metadata miss, and the second problem
prohibits the prefetcher from storing enough records within reasonably-sized
storage.
