Partial sampling with reverse state reconstruction: A new technique for branch predictor performance estimation

Exploring the design space of branch predictors can consume tremendous computational resources. In order to mitigate this problem we present a new non-clustered sampling technique for rapidly evaluating the performance of a large number of branch predictors in a single rapid pass through a trace. The predictors studied in this single pass need not closely resemble one another. Each may use a radically different method of indexing into one or more arrays of two bit counters. In experiments with SPEC95 benchmarks we have found that while sampling on the order of one branch per every ten thousand we can typically produce correct results for all but a few hundredths of a percent of the branches in the sample. The only instances we have found where this is not the case are degenerate cases in which we show that full-trace modeling also fails to give accurate results. Our technique is based on a general approach we call partial sampling. Partial sampling maintains a generic data structure as it scans a trace. At selected sample points in the trace, this structure is queried to determine the behavior of particular operations. The sampled operations need not be clustered