It is well known that compression and prediction are interrelated in that high compression implies good predictability, and vice versa. We use this correlation to find predictable properties of program behavior and apply them to appropriate cache management tasks. In particular, we look at two properties of program references: (1) Inter Reference Gaps: defined as the time interval between successive references to the same address by the processor, and (2) Cache Misses: references which access the next level of the memory hierarchy. Using compression, we show that these two properties are highly predictable and exploit them to improve Cache Replacement and Cache Prefetching, respectively. Using trace-driven simulations on SPEC and Dinero benchmarks, we demonstrate the performance of our predictive schemes, and compare them with other methods for doing the same. We show that, using our predictive replacement scheme, miss ratio in cache memories can be improved up to 43 percent over the well-known Least Recently Used (LRU) algorithm, which covers the gap between the LRU and the off-line optimal (MIN) miss ratios, by more than 84 percent. For cache prefetching, we show that our scheme eliminates up to 62 percent of the total misses in D-caches. An equivalent sequential prefetch scheme only removes up to 42 percent of the misses. For I-caches, our scheme performs almost the same as the sequential scheme and removes up to 78 percent of the misses.

The property of locality in program behavior has been studied and modelled extensively because of its application to memory design, code optimization, multiprogramming etc. We propose a k order Markov chain based scheme to model the sequence of time intervals between successive references to the same address in memory during program execution. Each unique address in a program is modelled separately. To validate our model, which we call the Inter-Reference Gap (IRG) model, we show substantial improvements in three different areas where it is applied. (1) We improve upon the miss ratio for the Least Recently Used (LRU) memory replacement algorithm by up to 37%. (2) We achieve up to 22% space-time product improvement over the Working Set (WS) algorithm for dynamic memory management. (3) A new trace compression technique is proposed which compresses up to 2.5% with zero error in WS simulations and up to 3.7% error in the LRU simulations. All these results are obtained experimentally, via trace driven simulations over a wide range of cache traces, page reference traces, object traces and database traces.