Measurements of major locality phases in symbolic reference strings

Previous studies have shown that a program's behavior can be characterized as a sequence of transitions between phases of execution during which some subset of the program's segments is referenced. The nature of the phases (sometimes called localities or regimes), and the characteristics of the transitions between neighboring phases, will determine the performance of the program on a virtual memory system. We here investigate methods for identifying those “major” phases in programs which correspond to intervals of distinctive referencing behavior. Experimental measurements on symbolic reference strings generated by production Algol-60 programs are used to determine the properties of these phases and the transitions between them. The experimental results are discussed in terms of current models for program behavior and also with regard to their implications for memory management systems.