## 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 | |

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