Method of, system for, and computer program product for providing efficient utilization of memory hierarchy through code restructuring
US6175957A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Dec 9, 1997 |
| Grant date | Jan 16, 2001 |
| Priority date | — |
| Expiry date | Dec 9, 2017 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F8/4442
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Code restructuring or reordering based on profiling information and memory hierarchy is provided by constructing a Program Execution Graph (PEG) corresponding to a level of the memory hierarchy, partitioning this PEG to reduce estimated memory overhead costs below an upper bound, and constructing a PEG for a next level of the memory hierarchy from the partitioned PEG. The PEG is constructed from control flow and frequency information from a profile of the program to be restructured. The PEG is a weighted undirected graph comprising nodes representing basic blocks and edges representing transfer of control between pairs of basic blocks. The weight of a node is the size of the basic block it represents and the weight of an edge is the frequency of transition between the pair of basic blocks it connects. The nodes of the PEG are partitioned or clustered into clusters such that the sum of the weights of the nodes in any cluster is no greater than an upper bound. A next PEG is then constructed from the clusters of the partitioned PEG such that a node in the next PEG corresponds to a cluster in the partitioned PEG, and such that there is an edge between two nodes in the next PEG if there…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.