Improving locality by critical working sets

ABSTRACT

A new approach to program locality improvement via restructuring is described. The method is particularly suited to those systems where primary memory is managed according to a working set strategy. It is based on the concept of critical working set, a working set which does not contain the next memory reference. The data the method operates upon are extracted from a trace of the program to be restructured. It is shown that, except in some special cases, the method is not optimum. However, the experimental results obtained by using the method to restructure an interactive text editor and the file system module of an operating system have shown its substantial superiority over the other methods proposed in the literature.

REFERENCES

• 1: Belady, L.A. A study of replacement algorithms for a virtualstorage computer. IBM Systems J. 5, 2 (1966), 78-101.
• 2: Peter J. Denning, Virtual Memory, ACM Computing Surveys (CSUR), v.2 n.3, p.153-189, Sept. 1970 [doi>10.1145/356571.356573]
• 3: A. C. McKellar , E. G. Coffman, Jr., Organizing matrices and matrix operations for paged memory systems, Communications of the ACM, v.12 n.3, p.153-165, March 1969 [doi>10.1145/362875.362879]
• 4: Barbara S. Brawn , Frances G. Gustavson , Efrem S. Mankin, Sorting in a paging environment, Communications of the ACM, v.13 n.8, p.483-494, Aug. 1970 [doi>10.1145/362705.362710]
• 5: Per Brinch Hansen, Operating System Principles, Prentice Hall PTR, Upper Saddle River, NJ, 1973
• 6: Lesin W. Comeau, A study of the effect of user program optimization in a paging system, Proceedings of the first ACM symposium on Operating System Principles, p.4.1-4.7, January 1967 [doi>10.1145/800001.811667]
• 7: Tsao, R.F., Comeau, L.W., and Margolin, B.H. A multifactor paging experiment: I. The experiment and the conclusions. In Statistical Computer Performance Evaluation, Freiberger, W. (Ed.), Academic Press, New York, 1972, pp. 103-134.
• 8: Hatfield, D.J, and Gerald, J. Program restructuring for virtual memory. IBM Systems J. 10, 3 (1971), 168-192.
• 9: C. V. Ramamoorthy, The analytic design of a dynamic look ahead and program segmenting system for multiprogrammed computers, Proceedings of the 1966 21st national conference, p.229-239, January 1966 [doi>10.1145/800256.810702]
• 10: Thomas C. Lowe, Automatic segmentation of cyclic program structures based on connectivity and processor timing, Communications of the ACM, v.13 n.1, p.3-6, Jan. 1970 [doi>10.1145/361953.361957]
• 11: Vet Hoef, E.W. Automatic program segmentation based on Boolean connectivity. Proc. AFIPS 1971 SJCC, AFIPS Press, Montvale, N.J., pp. 491-495.
• 12: Baer, J.L., and Caughey, R. Segmentation and optimization of programs from cyclic structure analysis. Proc. AFIPS 1972 SJCC, AFIPS Press, Montvale, N.J., pp. 23-36.
• 13: Peter J. Denning, The working set model for program behavior, Communications of the ACM, v.11 n.5, p.323-333, May 1968 [doi>10.1145/363095.363141]
• 14: Domenico Ferrari, A tool for automatic program restructuring, Proceedings of the annual conference, p.228-231, August 27-29, 1973, Atlanta, Georgia, United States [doi>10.1145/800192.805709]
• 15: Gotthoffer, D.J. KQED user's manual, Doc. No. W-66.0/ CSRP, Computer Systems Res. Proj., U. of California, Berkeley, Aug. 1972.
• 16: Thompson, H. Functional specification of the local file system, Doc. No. R-5.0/CSRP, Computer Systems Res. Proj., U. of California, Berkeley, Apr. 1973.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Multiprocessing/multiprogramming/multitasking

General Terms:
Experimentation, Performance

Keywords:
critcal work set, dynamic restructuring, locality improvement, memory hierarchies, multiprogramming, program restructuring, program segmentation, restructuring techniques, static restructuring, virtual memory, working set strategy