Influence of program transients in computer cache-memories
Dominique Thiébaut · 1988
In this dissertation two approaches are taken to analyze the effects of extrinsic and intrinsic transients experienced by programs on their performance in cache memories. In the first approach an analytical model is developed to predict the amount of cache lines that a program needs to reload when it resumes execution after having been interrupted by another program. This quantity is coined the reload transient and is a cause of performance degradation in multitasking environments, as well as in real-time systems. The analytical model predicts the amount of reload transient as a function of the number of cache congruence classes, of the degree of associativity of the cache, and of the size of the programs. The size of a program is defined as the number of unique lines brought in the cache over that program's execution. In the second approach, computer programs are modeled as fractal, lattice random-walks. As such, the dynamic characteristics of a program can be determined in a one-pass analysis of the trace of the program by only four parameters, one of which is the fractal dimension of the program. A cache model based on the fractal approach is presented. The model predicts the miss-ratio of programs in fully associative caches managed by a Least Recently Used (LRU) replacement-algorithm. Both models are validated by trace-driven simulations.