Method and system for incrementally improving a program layout
US6381740B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Sep 16, 1997 |
| Grant date | Apr 30, 2002 |
| Priority date | — |
| Expiry date | Sep 16, 2017 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F8/445
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method and system for incrementally improving the layout of a program image of a computer program to reduce the working set. The system iteratively selects pairs of basic blocks and reorders the basic blocks in the range delimited by the selected pair of basic blocks. The system selects the pairs of basic blocks so that the working set of the computer program is improved by reordering the basic block in the range. Thus, during each iteration, the working set is improved. The system continues with these iterations until a termination condition (e.g., number of iterations) is satisfied. In one embodiment, during each iteration the system designates one of the basic blocks as an initial anchor basic block. The system then repeats the following until the same range of basic blocks is identified twice in a row. The system first finds a basic block such that when the basic blocks in the range from the anchor basic block to the found basic block are reordered, the working set is more favorable than reordering any other range that ends with the anchor basic block. The system then designates the found basic block as the new anchor basic block. When the same range is found twice in a row, …
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.