Abstract:
Boolean circuits are designed with minimal depth by calculating the depth of an existing circuit. Those subtrees having a non-regular root cell (i.e., cells having other than one child or having a child of a type different from the cell) are balanced by constructing a new subtree. The cells are then iteratively transformed with parent and/or grandparent cells to reduce the depth of the circuit. The transformation may include balancing the subtree to make the parent cell the same type as the selected cell, or by creating a new cell as parent to the selected cell.

Description:
FIELD OF THE INVENTION 
   This invention relates to integrated circuits, and particularly to minimizing depth of Boolean integrated circuits. 
   BACKGROUND OF THE INVENTION 
   One important problem in integrated circuit (IC) design is the minimization of the delay in the circuits. In ICs, Boolean circuits comprise trees to carry out certain Boolean functions. Typically, the Boolean circuits are created from a library of Boolean elements such as two-input AND and OR elements (cells) and NOT (inverter) elements or cells. The delay of Boolean circuits can ordinarily be minimized by minimizing the depth of the Boolean circuit. 
   The maximal number of cells that lie on any path from any input of a Boolean circuit to the output of the Boolean circuit is called a depth of a Boolean circuit. Each cell along the path adds one to the depth of the circuit. Thus, a tree or subtree having a path containing eight cells has a depth of 8. The delay of a Boolean circuit increases with its depth. 
   Considerable attention has been given to minimizing depth of Boolean circuits. Much of the attention has been directed at certain classes of Boolean functions (such as comparators, adders, subtractors, multipliers, etc), and to the development of techniques that allow fabricating Boolean circuits with small depth and small number of cells. In the present case, consideration is given to the special classes of Boolean circuits that perform the following functions:
 
f 0 (x 1 , x 2 , . . . , x n )=x 1             (x 2           (x 3           (x 4           ( . . . ))))
 
f 1 (x 1 , x 2 , . . . , x n )=x 1           (x 2           (x 3           (x 4           ( . . . )))).

   The above functions are important because they are included in many arithmetic operations, such as addition, subtraction, and comparison. A fast hardware evaluation of these functions has been developed based on the presumption that all inputs x 1 , x 2 , . . . , x n  of functions f 0  and f 1  have the same arrival depth when functions f 0  and f 1  are a part of adders and comparators. 
   Functions f 0  and f 1  are used in several methods of synthesis Boolean circuits other than special arithmetical operations, for example a Boolean function y determined by the RTL-Verilog code:
         y=0;   if (A 1 ) y=1;   if (A 2 ) y=0;   if (A 3 ) y=1;   if (A 4 ) y=0;   if (A 5 ) y=1;   . . .   if (An) y=0.
 
It is clear that y=ƒ 1 ({tilde under (A)} 1 , A n-1 , . . . , A 1 ). Consequently, functions f 0  and f 1  can be used during the synthesis of Boolean circuits to evaluate Boolean functions determined by some programming languages.
       

   Variables A 1 , A 2 , . . . , A n  can be either single variables or comprehensive expressions that are evaluated by different Boolean circuits. These variables often have the different arrival depths. Because the values of variables A 1 , A 2 , . . . , A n  are evaluated by the different Boolean circuits whose depths are optimized separate from each other, a need exists for a more universal method of rapid reduction of the depth of functions f 0  and f 1  for various sets of arrival depths of inputs A 1 , A 2 , . . . , A n . 
   SUMMARY OF THE INVENTION 
   The present invention is directed to a process of fabricating Boolean circuits of minimal depth functions having different input arrival depths. 
   In one embodiment, Boolean circuits are designed with minimal depth. The depth of an existing circuit is calculated, the Boolean circuit being composed of cells arranged in a tree to perform a Boolean function. Those subtrees having a non-regular root cell is balanced, wherein a non-regular cell is one having a number of children other than one or having one child of a type different from the root cell. The cells are iteratively transformed parent and/or grandparent cells until the depth of the circuit not reduced between two successive iterations. The resulting circuit design is then output. 
   The subtrees are balanced by constructing a new subtree connected to the nets that are leaves to the tree, or by creating a new cell connected to two leaves that are nets with minimal depth and thereupon constructing a new subtree connected to the leaves. 
   If a parent cell to a selected cell has two or more children or is a type different from that of the selected cell, the subtree may be adjusted so that the parent cell is the same type as its child and has more than one child. Adjustment of the subtree can be accomplished by balancing the subtree to make the parent cell the same type as the selected cell (if the parent and selected cells were of different types), or by creating a new cell as parent to the selected cell (if the parent cell had more than one child cell). 
   The adjustment of the subtree by creating a new parent cell can be accomplished by creating a new cell as a duplicate of the parent cell, and connecting the selected cell to the new parent cell. The adjustment of the subtree by balancing the subtree can be accomplished by creating new parent cells of the same type as the selected cell, and a selected new cell of the same type as the original parent cell. Each new parent cell is connected to the other parent cell and to a respective grandparent cell of the original parent cell. The selected new cell is connected to new parent cells. The subtrees containing the new parent cells are then balanced. 
   In another embodiment of the present invention, a computer readable code is provided to cause a computer to perform the processes of the invention. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIGS. 1 and 2  are diagrams of Boolean circuits useful in explaining certain of the expressions used herein. 
       FIG. 3  is a flowchart of the steps of the process of optimizing depth of Boolean circuits in accordance with a preferred embodiment of the present invention. 
       FIGS. 4–7  are flowcharts of certain subprocesses used in the process illustrated in  FIG. 3 . 
   

   DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
   In the present invention, inputs x 1 , x 2 , . . . , x n  have respective arrival depths expressed as non-negative integer numbers d 1 , d 2 , . . . , d n . This is different from the case where d 1 −d 2 = . . . =d n =0. 
     FIG. 1  illustrates a Boolean circuit with inputs x 1 , x 2 , . . . , x 6  and output y. There are 3 two-input cells of the type OR 2 : A, B, D, and 4 two-input cells of type AND 2 : C, E, F, G. For ease of explanation, the names of the nets are the same as the names of their respective driver cells, so net A is connected to the output of cell A; net B is connected to the output of cell B, etc. 
   A cell U is connected to a cell V (or input x i ) if one of inputs of cell U is connected to the net that is driven by the cell V (or input x i ). In such case, cell U is a child of cell V (or input x i ), and cell V (or input x i ) is a parent of cell U. In the example of  FIG. 1 , cell A is connected to inputs X 1  and X 2  and cell F is connected to cells D and E. Thus, cell F is a child of cells D and E and cells D are E are parents to cell F. 
   P 0 (U) and P 1 (U) are the parents of the cell U. The depth d is recursively defined for each cell and each net of the Boolean circuit. For each input x i  assume d(x i )=d i . The depth d(U) for each cell U and the net U connected to the output of cell U is defined as 1 plus the maximum depth of the parent with the largest depth. Hence, depth d(U) can be written as d(U)=max(d(P 0 (U)),d(P 1 (U)))+1. In the example,
 
 d ( A )=max( d ( x   0 ), d ( x   i ))+1, and
 
 d ( F )=max( d ( D ), d ( E ))+1.
 
Using this recursive definition, the depth of all the cells can be calculated. If d 1 =d 2 =. . . d 6 =0,
 
 d ( A )= d ( B )= d ( C )=1
 
 d ( D )= d ( E )=2
 
 d ( F )=3
 
 d ( G )=4
 
   Hence, the depth of the Boolean circuit is the depth of the net to which its output connected. Thus, the depth of the Boolean circuit shown in  FIG. 1  is d(G)=4. 
   Cells are ordered in “topological order” if they are ordered by depth in ascending order; cells are ordered in “back topological order” if they are ordered by depth in descending order. In the example the order A, B, C, D, E, F, G is a topological order. 
   A cell U is called “dis-balanced” if d(P 0 (U))≠d(P 1 )(U)). In the example there are two dis-balanced cells: E and G. 
   A cell U is a called a “regular” cell if it has only one child and this child is of the same type (AND 2  or OR 2 ) as the type of the cell U. In the example there are four regular cells: B, C, E and F. A “non-regular cell” is one having a number of children other than one, or a single child of a different type. Thus, cell A is a non-regular cell because it has two children, cell D is a non-regular cell because its child is a different type from cell D, and cell G is a non-regular cell because it has no children. 
   For each non-regular cell U a uniform subtree D(U) fragment of the Boolean circuit is determined recursively:
         1) UεD(U);   2) if the cell VεD(U) and cell P i (V), i=0, 1, is a regular cell, it implies that P i (V)εD(U);   3) the uniform subtree D(U) also contains all nets connected to any input of any cell VεD(U).       

     FIG. 2  illustrates the uniform subtrees D(A), D(D) and D(G) of the three non-regular cells shown in  FIG. 1 . The non-regular cell U is the root of the uniform subtree D(U). Each Boolean circuit consisting of OH 2  and AND 2  cells can be presented as the union of uniform subtrees created for all non-regular cells. Thus each cell V of the Boolean circuit belongs to one of its uniform subtrees, and the root of the uniform subtree that contains cell V is cell R(V). 
   Finally, two cells U and V are considered duplicates if they are connected to the same cells and they are of the same type. 
     FIG. 3  is a flowchart of the process of the present invention. The process begins at step  100  with the Boolean circuit determined by the expression x 1             (x 2           (x 3           (x 4           ( . . . )))) for function f 0 (x 1 , x 2 , . . . , x n ) and by the expression x 1           (x 2           (x 3           (x 4           ( . . . )))) for function F 1 (x 1 , x 2 , . . . , x n ). The Boolean circuit description, such as in Verilog code, is input to the process at step  100 . In accordance with the invention equivalent transformations will be applied to the starting Boolean circuit to reduce the depth of the resulting circuit. Because only equivalent transformations are employed, the evaluation of the Boolean function F k (x 1 , x 2 , . . . , x n ), where k=0, 1, by the resulting Boolean circuit is the same as the evaluation of the function by the starting Boolean circuit.
   At step  102 , the CALCULATE DEPTH procedure is run. The CALCULATE DEPTH procedure examines all the cells in the topological order. The depth of each regular cell is calculated as the maximum of the depth of parents plus one. A BALANCE SUBTREE transformation is applied to non-regular cells U at step  104 . The BALANCE SUBTREE transformation is described in detail in connection with  FIG. 4 . 
   At step  106 , the cells are examined in back topological order. The PROCESS TRANSFORMATION procedure is applied to each cell U. The PROCESS TRANSFORMATION procedure is described in greater detail in connection with  FIG. 5 . 
   At step  108 , the REMOVE DUMMY procedure is applied. Dummy cells may have existed in the starting Boolean circuit, or created as part of one or both of steps  104  or  106 . To remove dummy cells, all cells are examined in the topological order. If both parents of the cell are the same the cell is removed, and all the children of this cell are reconnected to the parent cells. 
   At step  110 , the CALCULATE DEPTH procedure, described in step  102 , is re-run. If the depth of the circuit was reduced during steps  106 – 110 , the process loops back to step  106  at step  112 . Otherwise, the process continues to step  114  where a REMOVE DUPLICATES AND DUMMY procedure is run. In this procedure, all cells are examined in the topological order. If the cell has a duplicate cell, the cell is removed and all the children of the cell are reconnected to the duplicate. If both parents of the cell are the same, the cell is removed and all children of the cell are reconnected to the parent cells. 
   Finally, the process ends at step  116  with the output of the resulting Boolean circuit. 
     FIG. 4  is a flowchart of the BALANCE SUBTREE transformation used at steps  104  ( FIG. 3 ),  408  ( FIG. 6) and 504  ( FIG. 7 ). If at step  200  the cell U of the Boolean circuit is a regular cell, no action is necessary and the transformation ends. If, at step  200 , cell U is a non-regular cell the uniform subtree D=D(U) is used to construct a new uniform subtree D_NEW and replace the uniform subtree D with the new subtree D_NEW so that the children of the cell U become connected to the root cell of the subtree D_NEW. Both subtrees D and D_NEW have the same number of cells but the depth of the root cell of the subtree D_NEW can be less than the depth of the cell U. 
   The process of constructing the subtree D_NEW starts as step  202 . Let A=(a 1 , a 2 , . . . , a 6 ), where m≧2, be a set of nets that are the leaves of the subtree D and let s 1 , s 2 , . . . , s m  be the depths of these nets. For example, the uniform subtree D(D) shown in  FIG. 2  has 3 leaves: A, X 3 , X 4  with depths 1, 0, 0 respectively. Subtree D_NEW is defined recursively. 
   At step  202 , a determination is made as to whether m=2 or m&gt;2 (recall, m is the number of nets that are leaves to the subtree). If at step  202  m=2, subtree D_NEW is established at step  204  and consists of one cell connected to nets a 1  and a 2 . The type of this cell is the same as cell U. 
   If at step  202  m&gt;2, the process continues to step  206  to chose leaves a 1 εA and a j εA with minimal possible depths s 1  and s j . At step  208 , cell V is created connected to nets a 1  and a 2  with the same type as cell U. Net V is connected to the output of the cell V and s=max(s 1 ,s j )+1 is the depth of the cell V. Subtree D_NEW is constructed at step  210  for the set of leaves {V, a 1 , a 2 , . . . , a m }\{a 1 , a j }. This set has one less net than the set A={a 1 , a 2 , . . . , a m }. 
     FIG. 5  is a flowchart of the PROCESS TRANSFORMATION procedure used at step  106  ( FIG. 3 ). The process begins at step  300  with the examination of the parents of cell U. If, at step  300 , both parents of cell U have already been examined, the process ends at step  326 . Otherwise, the process advances to step  302  to consider parent V of cell U. At step  302 , if d(V)&lt;d(U)−1 then the process returns to step  300  to consider the other parent W. At step  304 , if parent V is an input to the Boolean circuit, the process returns to step  300  to consider the other parent W. If at step  306 , cell U and parent cell V are not the same type, the process loops to step  318 . Otherwise, if at step  308  cell U is the only child of parent cell V, the process returns to step  300  to consider the other parent W. If cell U is not the only child of cell V (i.e., parent cell V is a non-regular cell), the process advances to step  310  where the uniform subtree D(R(U)) is searched to find dis-balanced cells Z. If subtree D(R(U)) contains no dis-balanced cells Z, the process returns to step  300  to consider the other parent W. Otherwise the dis-balanced cell Z with maximal possible depth d(Z) is selected at step  312 . If at step  314  the depth of cell Z is not greater than the minimum depth of either parent plus 2, namely that d(Z)≦min(d(P 0 (V)), d(P 1 (V)))+2, then the process returns to step  300 , otherwise the MOVE transformation, more fully described in connection with  FIG. 7 , is applied to cells U and V at step  316  and the process advances to step  326 . 
   If, at step  306 , cells U and V are of different types, the process continues to step  318 . At step  318 , the other parent cell W of cell U is considered (as opposed to parent cell V). Cells W 1  and W 2  are the parents of cell V and grandparents to cell U. At step  318 , if both cells W 1  and W 2  are of the same type as the type of the cell V then the process returns to step  300 . Otherwise, at step  320  parameter k is defined. More particularly, k is 0 if cells W, U, W 1 , W 2  are of the same type. Otherwise, k=1. At step  322 , if d(W)&gt;d(U)−2−k, then the process returns to step  300 . Otherwise at step  324  the DISTRIBUTE transformation, more fully described in connection with  FIG. 6 , is applied to cells U and V and the process ends at step  326 . 
   Steps  306  and  308  effectively identify if parent cell V is a non-regular cell. Recall, one form of non-regular cell is one with more than one child or is of a different type than its child. Step  306  identifies if cell V is a non-regular cell because it is a different type from cell U, and the transformation of  FIG. 6  is performed (if cell V&#39;s parent cell W 1  and W 2  are not the same type as cell V) to distribute and balance the subtree to make cell V a regular cell. Step  308  identifies if cell V is a non-regular cell because it has more than one child, and the MOVE transformation of  FIG. 7  is performed to change cell V to a regular cells by creating a new cell V 1  to be parent to cell U. 
   In  FIG. 6 , cell V is a parent of cell U and cells U and V are of different types, i.e., cell u is an AND 2  cell and cell V is an OR 2  cell, or vice versa. W is the second parent of cell U, and W 1  and W 2  are the parents of cell V. At step  400 , new cell NEW_V 1  is created and connected to cells W 1  and W and new cell NEW_V 2  is created and connected to cells W 2  and W. Both new cells NEW_V 1  and NEW_V 2  are of the same type as cell U. At step  402 , a new cell NEW_U is created connected to cells NEW_V 1  and NEW_V 2 . Cell NEW_U is of the same type as cell V. At step  404 , new cell NEW_U replaces cell U so that the children of the cell U become connected to the cell NEW_U instead of to cell U. At step  406 , cell V is removed if the cell V had only one child U. At step  408  BALANCE SUBTREE transformation is applied to cells NEW_V 1  and NEW_V 2 . 
   The DISTRIBUTE transformation increases the number of cells of the Boolean circuit by 2, except where a cell is removed at step  406  in which case the transformation increases the number of cell by 1. The transformation is an equivalent transformation because cell U is replaced with an equivalent cell NEW_U. 
     FIG. 7  is a flow chart of the MOVE transformation used at step  316  ( FIG. 5 ). Cell V is a parent of cell U and the cells U and V are of the same types. Cell V is a non-regular cell and thus has more than one child. At step  500 , a new cell V 1  is created as a duplicate of the cell V. At step  502 , cell U is connected to the cell V 1  instead of to cell V. At step  504 , the transformation BALANCE SUBTREE transformation is performed on the subtree D(R(U)). Note that the MOVE transformation increases the number of cells, but the depth of the circuit may actually be reduced b the BALANCE SUBTREE transformation, as previously described. 
   As previously stated, inputs x 1 , x 2 , . . . , x n  have respective arrival depths expressed as non-negative integer numbers d 1 , d 2 , . . . , d n . In the present case, the arrival depths do not need to be equal (it is not necessary that d 1 =d 2 =. . . =d n =0). Thus, the present invention provides for the more general case of providing an optimally minimal depth Boolean circuit for performing the functions
 
 f   0 ( x   1   , x   2   , . . . , x   n )= x   1             ( x   2           ( x   3           ( x   4           ( . . . )))) and
 
 f   1 ( x   1   , x   2   , . . . , x   n )= x   1           ( x   2           ( x   3           ( x   4           ( . . . )))),
 
where the arrival depths of each input x 1 , x 2 , . . . , x n  are not the same. It also applies to the special case where d 1 =d 2 =. . . =d n =0. Experiments demonstrate that where the input arrival depths are equal and n≦64, a Boolean circuit obtained by the present invention has a depth no greater than one more, and in some cases the same, as one obtained by prior techniques specifically directed to equal input arrival depths.

   In preferred embodiments, the invention is carried out in a computer, with a memory medium, such as a recording disk of a disk drive, having a computer readable program therein containing computer readable program code that carries out the computer processes of the invention. The stating Boolean circuit may be represented in RTL-Verilog code and input as data to the computer. The computer, operating under control of the computer readable program, and particularly the computer readable program code on the disk, executes the code and performs the process steps of the invention, thus supplying an output in the form of an RTL-Verilog code describing the resulting Boolean circuit with minimal depth. 
   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.