Measurements of major locality phases in symbolic reference strings

ABSTRACT

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.

REFERENCES

• 1: Belady, L. A., A Study of Replacement Algorithms for a Virtual Storage Computer. IBM Systems J. 5 (1966) pp. 78-101.
• 2: Denning, P. J., On Modeling Program Behavior. Proc. AFIPS SJCC (1972) pp. 937-945.
• 3: Spirn, J. R. and P. J. Denning, Experiments with Program Locality. Proc. AFIPS FJCC (1972) pp. 611-621.
• 4: Freiberger, W. F., U. Grenander, and P. D. Sampson, Patterns in Program References. IBM J. of R. and D. 19, 3 (1975) pp. 230-243.
• 5: Hatfield, D. J. and J. Gerald, Program Restructuring for Virtual Memory. IBM Systems J. 10 (1971) pp. 168-192.
• 6: A. Wayne Madison , Alan P. Batson, Characteristics of program localities, Communications of the ACM, v.19 n.5, p.285-294, May 1976 [doi>10.1145/360051.360227]
• 7: Peter J. Denning , Kevin C. Kahn, A study of program locality and lifetime functions, Proceedings of the fifth ACM symposium on Operating systems principles, p.207-216, November 19-21, 1975, Austin, Texas, United States
• 8: A. P. Batson , R. E. Brundage, Measurements of the virtual memory demands of Algol-60 programs (Extended Abstract), Proceedings of the 1974 ACM SIGMETRICS conference on Measurement and evaluation, p.121-126, January 1974
• 9: Brundage, R. E., Ph.D. thesis, University of Virginia, 1974.
• 10: Prieve, B. G. and R. S. Fabry, VMIN - an Optimal Variable Space Replacement Policy. Presented at Proc. 5th ACM Symposium on Operating Systems Principles, Austin, Texas, November 1975. To appear in CACM.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance

General Terms:
Management, Performance

Keywords:
Locality, Memory management, Program behavior, Reference strings