Optimal segmentation points for programs

Research output: Contribution to conferencePaperpeer-review

1 Scopus citations


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)
Number of pages7
StatePublished - Oct 20 1969
Externally publishedYes
Event2nd ACM Symposium on Operating Systems Principles, SOSP 1969 - Princeton, United States
Duration: Oct 20 1969Oct 22 1969


Other2nd ACM Symposium on Operating Systems Principles, SOSP 1969
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Software


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

Cite this