Clustering For Processing Of Circuit Design Data

Abstract

Nodes in microdevice design data are selected to form initial clusters. Typically the nodes are selected based upon the type of process to be performed on the design data. The initial clusters are then be grown, merged with other nodes, or come combination of both until the processing costs of the final clusters are compatible with the amount of resources that will be used to process the design data.

What is claimed is: 
     
         1 . A method of partitioning portions of a circuit design for an electronic design automation process, comprising:
 generating initial clusters of nodes from a circuit design by
 employing a computer to select a node in the circuit design, and 
 employing a computer to grow a cluster of nodes from the selected node; 
   employing a computer to create final clusters of nodes from the initial clusters of nodes based upon processing weight values for processing the final clusters of nodes according to the electronic design automation process; and   employing a computer to partition the circuit design according to the final clusters of nodes groups.   
     
     
         2 . The method recited in  claim 1 , wherein employing the computer to generate the initial clusters of nodes in the circuit design includes
 identifying a critical path in the circuit design that does not meet specified timing requirements;   selecting a node in the circuit path with a largest timing violation and designating the selected node as an initial cluster of nodes; and   growing the initial cluster of nodes by
 (1) analyzing nodes logically connected to the initial cluster to determine if the analyzed nodes have a timing violation exceeding a threshold value, 
 (2) if an analyzed node has a timing violation exceeding the threshold value, adding the analyzed node to the initial cluster of nodes. 
   
     
     
         3 . The method recited in  claim 2 , further comprising growing the initial cluster of nodes by repeating operations (1) and (2) until no analyzed nodes have a timing violation exceeding the threshold value. 
     
     
         4 . The method recited in  claim 2 , further comprising growing the initial cluster of nodes by repeating operations (1) and (2) until
 no analyzed nodes have a timing violation exceeding the threshold value, or   an initial cluster limitation criteria is satisfied.   
     
     
         5 . The method recited in  claim 4 , wherein the initial cluster limitation criteria is selected from the group consisting of: a maximum node depth from the selected node, a maximum processing time for processing the initial cluster of nodes according to the electronic design automation process, a maximum number of nodes in the initial cluster of nodes, a number of net endpoints that end in the initial cluster of nodes, a maximum size of nets in the initial cluster of nodes, and a maximum number of relatively complex cells in the initial cluster of nodes. 
     
     
         6 . The method recited in  claim 1 , wherein
 employing the computer to generate initial clusters of nodes includes a first stage in which critical nodes in the circuit design are identified, and   employing the computer to generate final clusters of nodes includdes a second stage in which existing initial clusters of nodes are expanded.   
     
     
         7 . The method recited in  claim 6 , wherein the first stage of employing the computer to generate initial clusters of nodes includes
 selecting a critical path in the circuit design that does not meet specified timing requirements;   identifying a node in the circuit path with a largest timing violation as a critical node forming an initial cluster of nodes; and   growing the initial cluster of nodes by
 (1) analyzing nodes logically connected to the initial cluster of nodes to determine if the analyzed nodes have a timing violation exceeding a threshold value, 
 (2) if an analyzed node has a timing violation exceeding the threshold value, adding the analyzed node to the initial cluster of nodes. 
   
     
     
         8 . The method recited in  claim 7 , wherein the second stage of employing the computer to generate one or more final clusters of nodes in the circuit design includes
 selecting an initial cluster of nodes; and   growing the selected initial cluster of nodes by
 (1) analyzing nodes logically connected to the selected initial cluster of nodes to determine if the analyzed nodes have a timing violation exceeding a second threshold value, 
 (2) if an analyzed node has a timing violation exceeding the second threshold value, adding the analyzed node to the selected initial cluster of nodes. 
   
     
     
         9 . The method recited in  claim 8 , wherein the second stage of employing the computer to generate one or more final clusters of nodes further includes growing the selected initial cluster of nodes by repeating operations (1) and (2) until no analyzed nodes have a timing violation exceeding the second threshold value. 
     
     
         10 . The method recited in  claim 8 , wherein the second stage of employing the computer to generate one or more final clusters of nodes further includes growing the selected initial cluster of nodes by repeating operations (1) and (2) until no analyzed nodes have a timing violation exceeding the second threshold value, or a cluster limitation criteria is satisfied. 
     
     
         11 . The method recited in  claim 10 , wherein the cluster limitation criteria is selected from the group consisting of: a maximum node depth from the critical node, a maximum processing time for processing the selected initial cluster of nodes according to the place and route process, a maximum number of nodes in the selected initial cluster of nodes, a number of endpoints that end in the selected initial cluster of nodes, a maximum size of nets in the selected initial cluster of nodes, and a maximum number of relatively complex cells in the selected initial cluster of nodes. 
     
     
         12 . The method recited in  claim 1 , wherein the second stage of employing the computer to generate the final clusters of nodes further includes employing the computer to combine two or more initial clusters of nodes into a final cluster of nodes such that processing weight of final cluster of nodes does not substantially exceed a maximum processing weight value. 
     
     
         13 . The method recited in  claim 12 , further comprising combining the clusters of nodes by
 identifying border nodes between the initial clusters of nodes; and   merging the initial clusters of nodes into a final cluster of nodes along the border nodes with the largest timing violations.   
     
     
         14 . The method recited in  claim 1 , wherein employing a computer to partition the circuit design according to the final clusters of nodes comprises:
 providing the nodes in a first final cluster of nodes to a first iteration of the electronic design automation process for execution; and   providing the nodes in a second final cluster of nodes to a second iteration of the electronic design automation process for execution.   
     
     
         15 . The method recited in  claim 14 , wherein the execution of the first iteration of the electronic design automation process is independent of the execution of the second iteration of the electronic design automation process. 
     
     
         16 . The method recited in  claim 1 , wherein employing a computer to partition the circuit design according to the final clusters of nodes comprises:
 storing design data for the nodes in a first final cluster of nodes at a first storage location; and   storing design data for the nodes in a second final cluster of nodes at a second storage location separate from the first storage location.   
     
     
         17 . The method recited in  claim 1 , wherein employing a computer to partition the circuit design according to the final clusters of nodes comprises modifying the circuit design to distinguish nodes in a first final cluster from nodes in a second final cluster. 
     
     
         18 . The method recited in  claim 1 , further comprising:
 executing a first iteration of the electronic design automation using design data associate with a first final cluster of nodes; and   executing a second iteration of the electronic design automation process using design data associated with a final cluster of nodes.   
     
     
         19 . The method recited in  claim 1 , wherein a processing weight value for a final cluster of nodes is the time required to process the design data associated with the final cluster of nodes using the electronic design automation process.