On the fractal dimension of computer programs and its application to the prediction of the cache miss ratio

Author

Thiébaut, Dominique

Author_Institution

Dept. of Comput. Sci., Smith Coll., Northampton, MA, USA

Volume

38

Issue

7

fYear

1989

fDate

7/1/1989 12:00:00 AM

Firstpage

1012

Lastpage

1026

Abstract

Fractal geometry is proposed as a powerful measure of program behavior, and its application to the prediction of the miss ratio of programs in fully associative caches is presented. Programs are modeled as one-dimensional fractal random-walks. The fractal cache model is based on the parameterization of a program trace by a small number of constants, one of which is the fractal dimension of the program. The model is validated by trace-driven simulations of several program traces. With this model, it is possible to read the trace of a program once, and then predict the behavior of the miss ratio curve of that program in fully associative caches of varying sizes

Keywords

buffer storage; computational complexity; programming theory; cache miss ratio prediction; computer programs; fractal dimension; fractal geometry; one-dimensional fractal random-walks; parameterization; trace-driven simulations; Application software; Computational geometry; Computer errors; Computer science; Fractals; Lattices; Microscopy; Performance analysis; Predictive models; Solid modeling;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/12.30852

Filename

30852