Method and system for improving the layout of a program image using clustering
US6269477A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Sep 16, 1997 |
| Grant date | Jul 31, 2001 |
| Priority date | — |
| Expiry date | Sep 16, 2017 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F8/4442
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A computer system for establishing a program image layout of a computer program. The computer program has basic blocks that each have temporal usage vector indicating time intervals during which the basic block was accessed during an execution of the computer program. For each of the basic blocks, the layout system initializes a cluster to contain that basic block and the layout system repeats the following until one cluster remains that contains all of the basic blocks. For each possible ordered pair of clusters, the layout system determines a metric value for the ordered pair of clusters, the metric value being derived from the temporal usage vectors of the basic blocks of the cluster and estimating an effect on the performance of the computer program when that ordered pair of clusters are position in the program image in that order and contiguously. The layout system then selects the ordered pair whose metric value estimates the smallest effect on the performance of the computer program. The layout system then replaces the clusters of the selected ordered pair of clusters with a new cluster that includes the basic blocks of the selected order pair.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.