Enhancing the instruction fetching mechanism using data compression.

Abstract

The continually increasing speed of microprocessors stresses the need for ever faster instruction fetching rate. To sustain the full speed of microprocessors, the instruction fetching rate must increase proportionally to supply the instructions required. This dissertation applies data compression to improve several critical issues for fast instruction fetching: accurate branch prediction, high instruction cache hit rate, and high transfer bandwidth. First, we show how data compression relates to branch prediction and can be applied to improve prediction accuracy. Then we establish a theoretical basis for current branch predictors by showing that two-level adaptive branch predictors are simplifications of an optimal predictor in data compression, Prediction by Partial Matching (PPM). If the information provided to the predictor remains the same, it is unlikely that significant improvements can be expected (asymptotically) from two-level predictors, since PPM is optimal. We also applied data compression to improve instruction cache hit rates and to increase instruction fetch bandwidth. We introduced a technique to reduce instruction stream by compressing frequently encountered instruction sequences into single byte opcodes. Averaging across SPEC95 benchmarks, the bytes needed from level-1 cache were reduced by 50-70% and the bus cycles needed to fetch instructions from level-1 cache were reduced by 35-65%. In addition, a compression enhanced cache has a lower miss rate than a plain cache twice the size. Finally, to further increase cache hit rates, we proposed a prefetching scheme, which employs a branch predictor to run ahead of the execution unit and to prefetch potentially useful instructions. Branch prediction-based (BP-based) prefetching has a separate small fetching unit, allowing it to compute and predict targets autonomously. Our simulations show that a 4-issue machine with BP-based prefetching achieves higher performance than a plain cache 4 times the size. In addition, BP-based prefetching outperforms other hardware instruction fetching schemes, such as next-n line prefetching and wrong-path prefetching, by a factor of 17-44% in stall overhead and its bus traffic is very close to the best next-n line prefetching.