Optimal segmentation points for programs

ABSTRACT

A program may be modeled as a directed graph on n " nodes, " where the nodes are instructions, or data items, or contiguous groups of these. This paper discusses the problem of partitioning such sets of nodes into pages to minimize the number of transitions between pages during execution of the program.The node's are assumed to have a given ordering which may not be changed. We require that nodes on any page must be contiguous, so the only degree of freedom is in selecting "break points" between the pages.We show that if the expected number of transitions between each node of the program graph and its successors is known, then there is an algorithm for selecting the optima break points. The algorithm requires an execution time which grows linearly with the number of nodes in almost all cases.

REFERENCES

• 1: Richard Ernest Bellman, Dynamic Programming, Dover Publications, Incorporated, 2003
• 2: Berztiss, A. T., A note on segmentation of computer programs, <u>Information & Control<</u>, vol. 12 (1968), pp. 21--22.
• 3: Dearnley, F. H., Newell, G. B., Automatic segmentation of programs for a two-level store computer, <u>Computer J.</u>, vol. 7, #3, October 1964, pp. 185--187.
• 4: Feller, W., <u>An Introduction to Probability Theory and Its Applications</u>, vol. 1, Wiley, New York, 1957.
• 5: Kernighan, B. W., Some Graph Partitioning Problems related to Program Segmentation. Ph. D. Thesis, Department of Electrical Engineering, Princeton University, January 1969.
• 6: Kral, J., To the problem of segmentation of a program, Information Processing Machines, <u>Research Institute for Mathematical Machines</u>, Prague, 1965, pp. 140--149.
• 7: Jaroslav Král, One way of estimating frequencies of jumps in a program, Communications of the ACM, v.11 n.7, p.475-480, July 1968 [doi>10.1145/363397.363400]
• 8: Pinkerton, T. B., Program behavior and control in virtual storage computer systems, University of Michigan Technical Report 4, April 1968.
• 9: Schurmann, A., The application of graphs to the analysis of distribution of loops in a program, <u>Information and Control</u>, vol. 7 (1964), pp. 275--282.