Optimal segmentation points for programs

Research output: Contribution to conferencePaper

1 Scopus citations

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 optimal break points. The algorithm requires an execution time which grows linearly with the number of nodes in almost all cases.

Original languageEnglish (US)
Pages47-53
Number of pages7
DOIs
StatePublished - Oct 20 1969
Externally publishedYes
Event2nd ACM Symposium on Operating Systems Principles, SOSP 1969 - Princeton, United States
Duration: Oct 20 1969Oct 22 1969

Other

Other2nd ACM Symposium on Operating Systems Principles, SOSP 1969
CountryUnited States
CityPrinceton
Period10/20/6910/22/69

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Software

Fingerprint Dive into the research topics of 'Optimal segmentation points for programs'. Together they form a unique fingerprint.

  • Cite this

    Kernighan, B. W. (1969). Optimal segmentation points for programs. 47-53. Paper presented at 2nd ACM Symposium on Operating Systems Principles, SOSP 1969, Princeton, United States. https://doi.org/10.1145/961053.961072