The Fractal Structure of Data Reference: Applications to the Memory Hierarchy

For purposes of understanding its performance, a computer system is traditionally viewed as a processor coupled to one or more disk storage devices, and driven by externally generated requests (typically called transactions). Over the past several decades, very powerful techniques have become available to the performance analyst attempting to understand, at a high level, the operational behavior of such systems. Nevertheless, the ability of computers to rapidly deliver requested information, at the time it is needed, depends critically on an underlying structure whose operational behavior is not nearly as well understood: the memory hierarchy through which data stored on disk is made available to the processor. The memory hierarchy tends to consist of many levels, including one or more processor buffer memories (also called L1 and L2 cache), main processormemory, disk storage cache memory? disk storage, and often tape. A given level is usually configured to have both a much smaller storage capacity and a much faster access time than the level below it. The data stored in each memory level is managed dynamically, with new data being brought in as needed from the level below.