초록 ▼

The present invention provides methods specifically geared to finding natural splits in wide, nearly symmetric dependence graphs and assigning the components of the split to clusters in a VLIW processor. The basic approach of these methods is to assign a node n of the dependence graph to the cluste

The present invention provides methods specifically geared to finding natural splits in wide, nearly symmetric dependence graphs and assigning the components of the split to clusters in a VLIW processor. The basic approach of these methods is to assign a node n of the dependence graph to the cluster to which it has the strongest affinity. A node n has the strongest affinity to the cluster containing its closest common ancestor node. Then, the mirror image node or nodes of the node n are located if they are present in the graph and are assigned to other clusters in the processor to which they have the strongest affinity.

대표청구항 ▼

What is claimed is: 1. 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

What is claimed is: 1. 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. 2. The method of claim 1 further comprising the step of assigning each free node, if any, to either a first cluster or a second cluster of the two clusters. 3. The method of claim 2 in which the step of assigning each free node further comprises making the assignments such that resource usage is balanced. 4. The method of claim 1 in which the step c1 further comprises determining there is a plurality of nodes in the set of candidate nodes having the strongest affinity to a cluster of the two clusters and selecting the preferred node from the plurality of nodes such that the preferred node has the least amount of slack time of any node in the plurality of nodes; and the step c2 further comprises assigning the preferred node to a cluster of the two clusters such that resource usage is balanced if the preferred node has an equal affinity to each cluster of the two clusters. 5. The method of claim 1 wherein step c further comprises assigning the preferred node to a cluster of the two clusters such that resource usage is balanced if the preferred node has an equal affinity to each cluster of the two clusters. 6. The method of claim 1 in which the plurality of instructions is an unrolled loop. 7. A method for assigning instructions to a plurality of 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 plurality of clusters of any node in the set of candidate nodes; c2. assigning the preferred node to a cluster of the plurality of clusters to which the preferred node has a strongest affinity; c3. removing the preferred node from the set of candidate nodes; and c4. performing the following steps for each additional cluster of the plurality of clusters: c4.1 selecting a mirror image node, if present, from the set of candidate nodes or from the window of nodes; c4.2 assigning the mirror image node to the additional cluster; and c4.3 removing the mirror image node from the set of candidate nodes or from the window of nodes. 8. The method of claim 7 further comprising the step of assigning each free node, if any, to a cluster of the plurality of clusters. 9. The method of claim 8 in which the step of assigning each free node further comprises making the assignments such that resource usage is balanced. 10. The method of claim 7 in which the step c1 further comprises determining there is a plurality of nodes in the set of candidate nodes having the strongest affinity to a cluster of the plurality of clusters and selecting the preferred node from the plurality of nodes such that the preferred node has the least amount of slack time of any node in the plurality of candidate nodes; and the step c2 further comprises determining that the preferred node has an equal affinity to two or more clusters of the plurality of clusters and assigning the preferred node to one of the clusters to which the preferred node has equal affinity such that resource usage is balanced. 11. The method of claim 7 wherein the step c further comprises the step of determining that the preferred node has an equal affinity to two or more clusters of the plurality of clusters and assigning the preferred node to one of the clusters to which the preferred node has equal affinity such that resource usage is balanced. 12. The method of claim 7 in which the plurality of instructions is an unrolled loop. 13. A development system comprising: a general purpose computer; and a software development system installed on the general purpose computer wherein the software development system comprises a compiler incorporating 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. 14. A development system comprising: a general purpose computer; and a software development system installed on the general purpose computer wherein the software development system comprises a compiler incorporating a method for assigning instructions to a plurality of 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 plurality of clusters of any node in the set of candidate nodes; c2. assigning the preferred node to a cluster of the plurality of clusters to which the preferred node has a strongest affinity; c3. removing the preferred node from the set of candidate nodes; and c4. performing the following steps for each additional cluster of the plurality of clusters: c4.1 selecting a mirror image node, if present, from the set of candidate nodes or from the window of nodes; c4.2 assigning the mirror image node to the additional cluster; and c4.3 removing the mirror image node from the set of candidate nodes or from the window of nodes. 15. A digital system comprising: a processor comprising two clusters and operable to execute an application program; and wherein the application program was compiled with a compiler using 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. 16. A digital system comprising: a processor comprising a plurality of clusters and operable to execute an application program; and wherein the application program was compiled with a compiler using a method for assigning instructions to a plurality of 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 plurality of clusters of any node in the set of candidate nodes; c2. assigning the preferred node to a cluster of the plurality of clusters to which the preferred node has a strongest affinity; c3. removing the preferred node from the set of candidate nodes; and c4. performing the following steps for each additional cluster of the plurality of clusters: c4.1 selecting a mirror image node, if present, from the set of candidate nodes or from the window of nodes; c4.2 assigning the mirror image node to the additional cluster; and c4.3 removing the mirror image node from the set of candidate nodes or from the window of nodes.