Patent ID: 6839895

Claim:
A method of restructuring a program comprising a basic blocks for execution by a processor having a memory hierarchy comprised of a plurality of levels, the method comprising the steps of: a) constructing a Program Execution Graph (PEG) corresponding to a first level of the memory hierarchy from control flow and frequency information from a profile of the program, the PEG comprising a weighted undirected graph comprising nodes and edges, each node representing a basic block, each edge representing a transfer of control between a pair of the basic blocks, each of the nodes having a weight equal to the size of the basic block represented by the node, and each of the edges having a weight equal to a frequency of transition between a pair of basic blocks represented by a pair of nodes connected by the edge, b) for the first level of the memory hierarchy, partitioning the nodes of the PEG into clusters, such that a sum of weights of the edges whose endpoints are in different clusters is minimized, and such that, for any cluster, a sum of weights of the nodes in the cluster is no greater than an upper bound corresponding to a size of the first level of the memory hierarchy; and c) restructuring the basic blocks into contiguous code corresponding to the cluster, such that the basic blocks that communicate extensively with each other are on a same level of the memory hierarchy, in order to reduce communications between the basic blocks across the levels of the memory hierarchy.