Analysis of boolean program models for time-shared, paged environments

ABSTRACT

Directed graphs or their associated matrices are frequently used to represent the logical structure of sequences of computer instructions. Such techniques are used and, in addition, data references are represented in a nondirected model. The complete structural specification of a program is represented by a combined model. A transformation of the combined model yields a new model in which additional timing information is also contained. Analysis of these models prior to execution yields information valuable in determining segmentation of instructions and data for a time-shared environment, as well as for initial page loading; during execution, the analysis may be used for “look ahead” control of page turning.

REFERENCES

• 1: ARCHIBALD, RUSSELL D., AND VILLORIA, RICHARD L. Network Based Management Systems. Wiley, New York, 1967.
• 2: James D. Foley, A Markovian model of the university of Michigan executive system, Communications of the ACM, v.10 n.9, p.584-588, Sept. 1967 [doi>10.1145/363566.363701]
• 3: HOHN, F. E., SESHU, S., AND AUFENKAMF, D.D. The theory of nets. IRE Trans. EC-6 (Sept. 1957), 154-161.
• 4: INFORMATICS INC. Automatic program segmentation technical documentary report. TR 67-681-1, Rome Air Development Center, Contract no. AF 30 (602)-4297, Nov. 1967.
• 5: KASE, ROBERT HOWARD. Topological ordering for computer solution of PERT networks and other acyclic digraphs. M.S. Th., U. of Pennsylvania, Philadelphia, Pa., 1964.
• 6: KASE, ROBERT HOWARD. Algorithm 219, topological ordering for PERT networks. Comm. ACM 6, 12 (Dec. 1963), 738-739.
• 7: LOWE, THOMAS C. A scheduling problem. In Readings in simulation, Giuseppe M. Ferrero (Ed.), di Roccaferrera. (In press)
• 8: LOWE, THOMAS C. An algorithm for rapid calculation of products Boolean matrices. Software Age 2 (Mar. 1968), 36-37.
• 9: MARTIN, D.F. The automatic assignment and sequencing of computations on parallel processors. AD-628-220, UCLA Dept. of Eng., Rep. Jan. 1966.
• 10: David Martin , Gerald Estrin, Models of Computations and Systems—Evaluation of Vertex Probabilities in Graph Models of Computations, Journal of the ACM (JACM), v.14 n.2, p.281-299, April 1967 [doi>10.1145/321386.321391]
• 11: C. V. Ramamoorthy, Analysis of Graphs by Connectivity Considerations, Journal of the ACM (JACM), v.13 n.2, p.211-222, April 1966 [doi>10.1145/321328.321332]
• 12: 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]
• 13: ROSENBLATT, DAVID. Aggregation in matrix models of resource flows II.-Boolean remation matrix methods. The American Statistician (June 1967), 32-37.
• 14: ROSENBLATT, DAVID. On the graphs and asymptotic forms of finite Boolean relation matrices and stochastic matrices. Naval Res. Logistics Quart. 4 (June 1957), 244-256.
• 15: WHITEHOUSE, G. E. Mathematical background of G.E.R.T.: graphical evaluation and review technique. Res. rep., Dep. Industr. Eng., Lehigh U., Bethlehem, Pa., Apr., 1968.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Design, Theory

Keywords:
compiler, executive, monitor, paging, program model, segmentation, time-sharing