Paper included in the “25 years of International Conference on Supercomputing”

Dr. Jih-Kwon Peir’s paper entitled “Bloom Filtering Cache Misses for Accurate Data Speculation and Prefetching” co-authored with S. Lai, S. Lu, J. Stark, and K. Lai has been included in the “25 years of International Conference on Supercomputing”. The selection committee reviewed the top 100 most-cited papers out of 1800 papers published in ICS proceedings between 1987 and 2011 and selected 35 papers to be included.

A processor must know a load instruction’s latency to schedule the load’s dependents at the correct time. Unfortunately, modern processors do not know this latency until well after the load’s dependent instructions should have been scheduled to avoid pipeline bubbles. One solution is to predict the load latency based on whether the load will hit or miss the cache. Existing cache hit/miss predictors, however, can only correctly predict about 50% of the cache misses.

This paper introduces a new cache hit/miss predictor that uses a cache-address Bloom Filter to identify cache misses early in processor pipeline. This early identification of cache misses allows the processor to more accurately schedule instructions that are dependent on load and to more precisely prefetch data into cache. Our simulation results show that the proposed Bloom Filter can accurately identify 99 percent of the cache misses and achieve over 99 percent of the IPC comparing with a processor with perfect instruction scheduling.

Computer & Information Science & Engineering
Herbert Wertheim College of Engineering