Abstract:
An iterative process assigns nodes of a new logical tree to positions in a space that was previously assigned to an old logical tree equivalent to the new logical tree. A path in the new tree is identified for an essential node of the new tree. Coordinates of a position in the space are identified for an old tree node that is equivalent to a son of the essential node. Coordinates are iteratively identified for each node in the new tree path using a free space algorithm and based on the nodes of the new tree path and the coordinates identified for the old tree node that is equivalent to the son of the essential node. If all sons of the essential node are leaves of the new tree, the old tree node is a leaf node equivalent to the son. Otherwise, the old tree node is identified in a prior iteration.

Description:
FIELD OF THE INVENTION  
       [0001]     This invention relates generally to the field of integrated circuit layout, and particularly to placement of nodes of trees without overcrowding or increasing wire lengths.  
       BACKGROUND OF THE INVENTION  
       [0002]     U.S. Pat. No. 6,564,361 granted May 13, 2003 to Andrej A. Zolotykh et al. for “Method and Apparatus for Timing Driven Resysthesis” and assigned to the same assignee as the present invention, describes techniques for optimizing integrated circuit (IC) designs employing local optimization. Local logic restructuring is a basic step of the resynthesis procedure. One such logic restructuring procedure is described in U.S. Pat. No. 6,543,032 granted Apr. 1, 2003 to Andrej A. Zolotykh et al. for “Method and Apparatus for Local Resynthesis of Logic Trees with Multiple Cost Functions” and assigned to the same assignee as the present invention. The input of the local logic restructuring procedure described in the U.S. Pat. No. 6,543,032 is a logical tree. The result of the local logic restructuring procedure is a new logical tree that is equivalent to the initial tree.  
         [0003]     U.S. Pat. No. 6,513,148 granted Jan. 28, 2003 to Elyar E. Gasanov et al. for “Density Driven Assignment of Coordinates” and assigned to the same assignee as the present invention describes a procedure to assign coordinates to nodes of a new logical tree. But the procedure described in the U.S. Pat. No. 6,513,148 leads to increased summary wire length if the resynthesis stage is the area optimization.  
         [0004]     IC chips generally comprise a plurality of cells. Each cell may include one or more circuit elements, such as transistors, capacitors and other basic circuit elements, which are interconnected in a standardized manner to perform a specific function.  
         [0005]     The timing driven resynthesis described in the U.S. Pat. No. 6,564,361 patent has been used to change the chip design step by step, making the improvements of the chip locally. The main concept of the local resynthesis is to consecutively examine the cell trees of a chip for the necessity of the optimization, and then organize the chosen trees as local tasks for the resynthesis that follows. All necessary information about the tree neighborhood (neighboring cells, capacities, delays, etc.) is first collected. Next, local optimization procedures work with this information only. No additional information about the chip structure is required.  
         [0006]     Within the logical resynthesis, ordinary logical cells are considered, i.e. those cells with one output pin constructed using standard logical gates NOT, AND, OR. A logical tree is a tree formed from ordinary logical cells. Inside a logical tree, the output pin of each cell, other than the root (or root cell), is connected to exactly one other input pin, and this one other input pin is a pin of a cell of the logical tree. In contrast, the output pin of the root may be connected to any number of cell input pins. All cells connected with the output pin of the root of a tree may not belong to the tree, and the cells are not necessarily logical. An input pin of a cell of the tree may be connected to the power or the ground, or to a cell outside the tree. The cell input pin may be called the entrances of the tree.  
         [0007]      FIG. 1  illustrates an exemplary logical tree that includes six cells inside rectangle  50 . All entrances of the tree are enumerated by assigning variables x n  to the entrances. In addition, identical variables may be assigned to entrances connected through a wire because the input values of these entrances are always the same. As shown, for example, the variable x 1  is assigned to the first input pin of the cell ND 3 C and to the first input pin of the cell ENB, the variable x 2  is assigned to the second input pin of the cell ENB and to the first input pin of the cell NR 2 A, the variable x 3  is assigned to the input pin of the cell N 1 C.  
         [0008]     One goal of the logical resynthesis is to change a logical tree into a logically equivalent one, which is better with respect to a given estimator. The nodes of the initial logical tree have the coordinates, but it is necessary to assign coordinates to nodes of new logical tree.  
         [0009]     The present invention is directed the assignment of coordinates to nodes of a new logical tree without increasing summary wire length or wire congestion.  
       SUMMARY OF THE INVENTION  
       [0010]     In one embodiment of the invention, an iterative process assigns nodes of a new logical tree to positions in a space, wherein the space was previously assigned to an old logical tree that is equivalent to the new logical tree. A path in the new tree is identified for an essential node of the new tree. Coordinates of a position in the space are identified for an old tree node that is equivalent to a son of the essential node. Coordinates are iteratively identified for each node in the new tree path based on the nodes of the new tree path and the coordinates identified for the old tree node that is equivalent to the son of the essential node.  
         [0011]     In some forms, if all sons of the essential node are leaves of the new tree, the old tree node is a leaf node equivalent to the son. Otherwise, (if all sons of the essential node are not leaves of the tree) the old tree node is identified in a prior iteration.  
         [0012]     In some forms, the process is performed using a free space concept without increasing wire length of the tree.  
         [0013]     In other embodiments, a computer useable medium contains a computer readable program comprising computer readable program code for addressing data to cause a computer to carry out the process of the invention. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0014]      FIG. 1  is a block diagram of an integrated circuit containing a typical tree of logic cells.  
         [0015]      FIG. 2  is an illustration of a logic tree useful to explain certain principles of the present invention.  
         [0016]      FIGS. 3-5  are illustrations of logic trees that that are equivalent to the circuit of the tree illustrated in  FIG. 1 .  
         [0017]      FIGS. 6-8  are flow diagrams of a process of placement of nodes of a tree in accordance with an embodiment of the present invention. 
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0018]     The present invention finds corresponding essential nodes of old and new trees and uses coordinates of the old node as coordinates of the new node. The degree of a node of a tree is the number of edges incident to the node; an essential node is one having a degree of 2 (two edges). The coordinates of a cell are chosen using the concept of free space, which is the maximal size of a cell that can be placed in that position.  
         [0019]     A tree is a graph without loops with one pole called root.  FIG. 2  is an example of a tree D, where node α is the root of the tree, nodes β, γ, δ are sons of node α (node α is the father of the nodes β, γ, δ), nodes ε, ζ are sons of node δ, nodes η, θ, are sons of node ε, and nodes          , ι are sons of node ζ. Nodes β, γ, η, θ,          , ι are leaves of tree D.  
         [0020]      FIG. 3  illustrates tree D 1  which corresponds to the logical tree shown in rectangle  50  in  FIG. 1 .  
         [0021]      FIGS. 4 and 5  illustrate trees D 2  and D 3 , respectively, both of which are logically equivalent to tree D 1  illustrated in  FIG. 3 .  
         [0022]     A node of a tree D is “essential” if the node meets at least one of two conditions. If the node has more than one son, it is essential. If the node has but one son and that son is a variable, the node is essential. If a node is not essential then it is called “simple”. For tree D 1  shown in  FIG. 3 , nodes OR 2 B, ND 3 C, ENB, NR 2 A and N 1 C are essential, and node N 1 A is simple.  
         [0023]     Consider a tree D having a set of nodes {α, α 1 , α 2 , . . . , α m } where node α is an essential node and nodes α 1 , α 2 , . . . , α m  are simple nodes. Node α 1  is the father of the node α, the node α 2  is the father of the node α 1 , the node α m  is the father of the node α m-1 , and either the father of node α m  is essential or node α m  is the root of tree D. The set {α, α 1 , α 2 , . . . , α m } is called the simple path associated with the essential node α. For example, for the tree D 1  shown in  FIG. 3 , the simple path associated with the essential node N 1 C is {N 1 C}, the simple path associated with the essential node NR 2 A is {NR 2 A, N 1 A}.  
         [0024]     Consider that tree D 1  shown in  FIG. 3  is a logical tree of a chip. Assume it is desired to replace tree D 1  with tree D 2  shown in  FIG. 4 . It is easy to find correspondence between variables of these trees. For example, variable x 1 , which is the son of node ENB of tree D 1 , corresponds to variable x 1 , which is the son of node AND 2 C of tree D 2 ; variable x 1 , which is the son of node ENB of tree D 1 , corresponds to variable x 1 , which is the son of node ENB of tree D 2 .  
         [0025]     For purposes of the following description, it is presumed that a correspondence between variables of the old and new logical trees is found.  
         [0026]      FIG. 6  is a flowchart that shows the basic steps of the procedure to assign coordinates to nodes of the new logical tree. At step  100 , the input of the procedure is received, namely an old tree D 0  and a new tree D n . It is presumed that a correspondence exists between the leaves of the old and new trees.  
         [0027]     All simple paths of new tree D n  are examined. This is accomplished by examining all essential nodes of D n  using a depth-first tree pass algorithm and for each essential nodes, constructing the simple path associated with the essential node. For example, for tree D 1  shown in  FIG. 3 , the simple paths are considered in the following order: {ENB}, {ND 3 C}, {N 1 C}, {NR 2 A, N 1 A}, {OR 2 B}.  
         [0028]     If at step  102  all simple paths of D n  are considered, then the process exits at step  104 . Otherwise the next simple path {N 1 , . . . , N k } of new tree D n  is considered at step  106  where N 1  is essential node.  
         [0029]     If at step  108  all sons of node N 1  are leaves, then at step  110  the node of the old tree D 0  which corresponds to some son of node N 1  is denoted O in  (i.e. , O in  is a leaf node of the old tree that is equivalent to a son of node N 1 ). If at step  108  at least one son of node N 1  is not a leaf, O in  is set equal to O out , where O out  had been obtained at the step  114  for the previous simple path.  
         [0030]     At step  114 , coordinates are assigned to nodes N 1 , . . . , N k  using the procedure described in conjunction with  FIG. 7 . O out  is the result of the procedure shown in  FIG. 6  and is a node of the old tree D 0 .  
         [0031]      FIG. 7  is a flowchart that shows the basic steps of the process to assign coordinates of nodes of a simple path of the new logical tree. At step  200 , the input of the procedure is received, namely a node O in  of the old tree, and a simple path {N 1 , . . . , N k } of the new tree. The node O in  corresponds to some son of essential node N 1 .  
         [0032]     At step  202 , no is calculated as the number of essential parents of node O in , and n n  is calculated as the number of essential parents of node N 1  plus 1.  
         [0033]     At step  204 , a process to get a path of the old tree, shown and described below in conjuction with  FIG. 8 , is used to get some path of the old tree which begins with node O in . {O 1 , . . . , O m  is the result of this procedure. The coordinates of nodes O 1 , . . . , O m  will be used when assigning coordinates to nodes N 1 , . . . , N k .  
         [0034]     At step  206 , i is set equal to 1 and j is set equal to 1. At step  208 , the value of i is saved by setting e equal to i.  
         [0035]     At step  210 , the (x,y) coordinates of node O i  are identified, and the free space s of the (x,y) position is calculated, such as by the procedure described in U.S. Pat. No. 6,637,016 granted Oct. 21, 2003 to Elyar E. Gasanov et al. for “Assignment of Cell Coordinates” and assigned to the same assignee as the present invention. The coordinates of a cell are chosen using the concept of free space, which is the maximal size of a cell that can be placed in that position.  
         [0036]     If at step  212  the value of the free space s less than the size of the node N j , then the process proceeds to step  218 . Otherwise the process proceeds to step  214 .  
         [0037]     If at step  214  the number of remained nodes in the set {O 1 , . . . , O m } is more than the number of remained nodes in the set {N 1 . . . , N k } (i.e. (m-i)&gt;(k-j)) then the process proceeds to step  216 . Otherwise the process proceeds to step  220 .  
         [0038]     At step  216 , i is incremented (i=i+1) and the process loops back to step  210 .  
         [0039]     If at step  214  (m-i)≦(k-j), then at step  220 , the number i is restored to its previous value (i.e. i=e) and the (x,y) coordinates of the node O 1  are determined as the closest position to the (x,y) position, where the free space s is more than the size of the node N j . To find such closest position, the procedure described in the U.S. Pat. No. 6,637,016 may be used. The result of this procedure is again denoted by (x/y).  
         [0040]     The use of the procedure described in the U.S. Pat. No. 6,637,016 would seemingly increase wire length, but if the procedure is performed in the area optimization mode the summary size of nodes of the old tree is greater than the summary size of nodes of the new tree. Therefore, the procedure of the U.S. Pat. No. 6,637,016 can usually be applied without increasing wire lengths.  
         [0041]     At step  118 , the coordinates (x,y) are assigned to the node N j  and j is incremented (j=j+1).  
         [0042]     If at step  222  all nodes of the set {N 1 , . . . , N k } have been considered (i.e, j&gt;k) then the process proceeds to step  228 . Otherwise (if j≦k), the process proceeds to step  224 .  
         [0043]     If at step  224  the number of remaining nodes in the set {O 1 , . . . , O m } is more than the number of remaining nodes in the set {N j , . . . , N k } (i.e. (m-i)&gt;(k-j)), then at step  226  i is incremented (i=i+1) and the process loops back to step  208 . Otherwise, (if (m-i)≦(k-j)) i is not incremented and the process loops back to step  208 .  
         [0044]     If at step  228  n n &gt;n o  (meaning that the number of essential parents of the node O j  is more than the number of essential parents of the node N 1 ), then the process proceeds to step  232 . Otherwise the process proceeds to step  230 .  
         [0045]     At step  230  the closest essential parent O of node O i  is identified and the output node O out  is identified as a son of node O.  
         [0046]     At step  232  the output node is identified as node O i  (O out =O i )  
         [0047]     In either case, O out  is returned at step  234  as result of the procedure.  
         [0048]      FIG. 8  is a flowchart illustrating the basic steps of the procedure to get some path of the old tree which begins with node O in .  
         [0049]     At step  300 , the input of the procedure is received, namely a node O in  of the old tree, a node N 1  of the new tree, a number n o  which is equal to the number of essential parents of the node O in , and a number n n  which is equal to the number of essential parents of the node N 1  plus one.  
         [0050]     At step  302 , O is set equal to O in  and node O in  is added to the output set by setting m=1 and 0 1 =O in . If at step  304  n n &gt;n o  then the process proceeds to step  318 . Otherwise the process proceeds to step  306 .  
         [0051]     At step  306 , the value of n is calculated as n=n o −n n +1, and j is set to 0 (j=0) . At step  308 , the father of the node O is considered, i.e. node O is set to the father of node O.  
         [0052]     If at step  310 , node O is essential then the process proceeds to step  312 . Otherwise the process proceeds to step  316  where node O is added to the output set, i.e. set m=m+1 and O m =O. Then the process loops back to step  308  and iterates until a node O is found that is essential.  
         [0053]     At step  312 , j is incremented (j=j+1) If at step  314  j≦n then the process loops back to step  316  and iterates until j&gt;n, whereupon the process proceeds to step  326 .  
         [0054]     If at step  304  n n &gt;n 0 , then at step  318  n o is calculated as the number of parents of node O in , and n n  is calculated as the number of parents of node N 1  plus 1. At step  320 , n=n o −n n +1, and j is set equal to 1.  
         [0055]     If at step  322  j≦n, the process proceeds to step  324  where O is set equal to Father (O), j is incremented (j=j+1), and node O is added to the output set, i.e. set m=m+1 and O m =O. Then the process loops back to step  322 . If at step  322  j&gt;n, the process proceeds to step  326 .  
         [0056]     At step  326 , the set {O 1 , . . . , O m } is returned as a result of the procedure.  
         [0057]     The present invention thus provides a technique to assign nodes of a new tree to a space, such as an integrated circuit design, to replace an old tree. Coordinates for the nodes are found using a free space technique without increasing wire size within the tree or chip. In preferred embodiments, the process is carried out by a computer employing a computer program comprising computer readable program code recorded or embedded on a computer-readable medium, such as a recording disk or other readable device.  
         [0058]     Although the present invention has been described with reference to preferred embodiments, workers skilled in the art will recognize that changes may be made in form and detail without departing from the spirit and scope of the invention.