Optimal segmentation points for programs

Brian W. Kernighan

doi:10.1145/961053.961072

Optimal segmentation points for programs

Brian W. Kernighan

Research output: Contribution to conference › Paper › peer-review

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 language	English (US)
Pages	47-53
Number of pages	7
DOIs	https://doi.org/10.1145/961053.961072
State	Published - Oct 20 1969
Externally published	Yes
Event	2nd ACM Symposium on Operating Systems Principles, SOSP 1969 - Princeton, United States Duration: Oct 20 1969 → Oct 22 1969

Other

Other	2nd ACM Symposium on Operating Systems Principles, SOSP 1969
Country/Territory	United States
City	Princeton
Period	10/20/69 → 10/22/69

All Science Journal Classification (ASJC) codes

Computational Theory and Mathematics
Software

Access to Document

10.1145/961053.961072

Cite this

@conference{a479de2905f540bebe5c42fde7528870,

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

author = "Kernighan, {Brian W.}",

note = "Publisher Copyright: {\textcopyright} 1969 Association for Computing Machinery, Inc. All rights reserved.; 2nd ACM Symposium on Operating Systems Principles, SOSP 1969 ; Conference date: 20-10-1969 Through 22-10-1969",

year = "1969",

month = oct,

day = "20",

doi = "10.1145/961053.961072",

language = "English (US)",

pages = "47--53",

}

TY - CONF

T1 - Optimal segmentation points for programs

AU - Kernighan, Brian W.

PY - 1969/10/20

Y1 - 1969/10/20

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84976654549&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84976654549&partnerID=8YFLogxK

U2 - 10.1145/961053.961072

DO - 10.1145/961053.961072

M3 - Paper

AN - SCOPUS:84976654549

SP - 47

EP - 53

T2 - 2nd ACM Symposium on Operating Systems Principles, SOSP 1969

Y2 - 20 October 1969 through 22 October 1969

ER -

Optimal segmentation points for programs

Abstract

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this