Sandbox prefetching: Safe run-time evaluation of aggressive prefetchers

Memory latency is a major factor in limiting CPU per-formance, and prefetching is a well-known method for hid-ing memory latency. Overly aggressive prefetching can waste scarce resources such as memory bandwidth and cache capacity, limiting or even hurting performance. It is therefore important to employ prefetching mechanisms that use these resources prudently, while still prefetching required data in a timely manner. In this work, we propose a new mechanism to deter-mine at run-time the appropriate prefetching mechanism for the currently executing program, called Sandbox Prefetch-ing. Sandbox Prefetching evaluates simple, aggressive offset prefetchers at run-time by adding the prefetch ad-dress to a Bloom filter, rather than actually fetching the data into the cache. Subsequent cache accesses are tested against the contents of the Bloom filter to see if the ag-gressive prefetcher under evaluation could have accurately prefetched the data, while simultaneously testing for the ex-istence of prefetchable streams. Real prefetches are per-formed when the accuracy of evaluated prefetchers exceeds a threshold. This method combines the ideas of global pattern confirmation and immediate prefetching action to achieve high performance. Sandbox Prefetching improves performance across the tested workloads by 47.6 % com-pared to not using any prefetching, and by 18.7 % compared to the Feedback Directed Prefetching technique. Perfor-mance is also improved by 1.4 % compared to the Access Map Pattern Matching Prefetcher, while incurring consid-erably less logic and storage overheads.