Patent ID: 7062762

Claim:
A method for assigning instructions to two clusters comprising the steps of: generating a plurality of instructions; creating a data dependence graph comprised of a plurality of nodes wherein each node of the plurality of nodes represents an instruction from the plurality of instructions; calculating an earliest cycle and a latest cycle for each node of the plurality of nodes; performing the following steps a–c for each cycle between and inclusive of a maximum value of the latest cycle calculated for any connected node of the plurality of nodes and a minimum value of the earliest cycle calculated for any connected node of the plurality of nodes: a. selecting a window of connected nodes to be considered for assignment to a cluster wherein the cycle falls within a slack range of each selected node; b. selecting a set of candidate nodes from the window of nodes such that each node in the candidate set has an earliest cycle value equal to the value of the cycle; and c. performing the following steps while the set of candidate nodes is not empty: c1. selecting a preferred node from the set of candidate nodes such that the preferred node has a strongest affinity to a cluster of the two clusters of any node in the set of candidate nodes; c2. assigning the preferred node to the cluster of the two clusters to which the preferred node has a strongest affinity; c3. removing the preferred node from the set of candidate nodes; c4. selecting a mirror image node, if present, from the set of candidate nodes or from the window of nodes; c5. assigning the mirror image node to a cluster of the two clusters to which the preferred node is not assigned; and c6. removing the mirror image node from the set of candidate nodes or from the window of nodes.