Zhang, Haga, and Barua propose a new hardware-based I-cache correlated prefetch algorithm called “execution guided history method.” Their main idea is to correlate cache misses to instructions executed in a delta-time prior to the miss. This delta-time is calculated based on the latency of the target hardware, such that the prefetched instruction will arrive just in time to be useful. The miss history information is kept in a table, and the authors’ main contribution is that their method does not require an extra port to I-cache (there is no probing).

The authors also propose a variant to the method, aimed at return-from-procedure situations, which targets instruction cache misses happening when a return-from-procedure occurs between the trigger and the instruction being prefetched. The rationale is that a procedure can potentially be called from many others, and the missed instruction addresses will be different for each one. In that scenario, the original method will trigger prefetches among all the procedures, resulting in many useless ones, while the modified algorithm will associate the miss history table with the return stack.

Using simulations, and four benchmarks from the CPU2000 suite, the authors demonstrate that their method is more efficient than the best equivalent hardware-based correlated algorithm: branch-history-guided instruction prefetch (BHGP).