Granted Patent B2

US 6,868,536 · App. 10/299,564 · Granted Mar 15, 2005

Abstract

Claims (119)

1. A method to construct a symmetry tree of a Boolean function, comprising:

(a) setting an initial set of the trees T={D 1 , . . . , D n } and function ƒ, wherein D i is a tree which includes a node marked by variable x 1 (i=1, . . . , n), and proceeding to step (b);

(b) applying a procedure to construct a 1-symmetric part for the set T and the function ƒ, wherein T′={D′ 1 , . . . , D′ k } is the result of the applied procedure, and proceeding to step (c);

(c) determining whether |T′|=1, wherein |T′| is the cardinality of the set T′, and if |T′|=1, then the tree D′ 1 is returned, otherwise, proceeding to step (d);

(d) determining whether |T′|>1, if |T′|>1, then m is set equal to 2, where m corresponds to m-symmetric part of the set T′, and proceeding to step (e);

(e) determining whether m>|T′|/2, and if so, constructing tree N(T′) utilizing an N-union operation and returning the tree as the result of the operation, otherwise proceeding to step (f);

(f) determining whether m≦|T|′/2, and if so, applying a procedure to construct an m-symmetric part to the set T′ and the function ƒ, wherein T″ is the result of the procedure, and proceeding to step (g); and

(g) determining whether T′=T″, and if so, m is set equal to m+1 and the method returns to step (f), if T′≠T″, then T is set equal to T″ and the method returns to step (b).

wherein the method is utilized to minimize path delays and eliminate ramptime violations in internal synthesis tools for intergrated circuits.

2. The method as described in claim 1 , wherein the procedure to construct a 1-symmetric part to the set T and the function ƒ of step (b), in which the input of the procedure is a Boolean function ƒ(x 1 , . . . , x n ) and a set of marked trees and the output of the procedure is a set of marked trees, is as follows:

(b)(1) receiving an input including an initial set of trees T={D i , . . . D k } and function ƒ, and continuing to step (b)(2);

(b)(2) setting i equal to one, and continuing to step (b)(3);

(b)(3) determining if i is less than k, if i is less than k, setting j equal to i+1, initializing an auxiliary set of trees L={D i } and continuing to step (b)(4), otherwise returning set T as a result of the procedure;

(b)(4) determining if trees D i and D j are symmetric for function ƒ, and if so proceeding to step (b)(7), and if not, proceeding to step (b)(5);

(b)(5) determining if j is less than k, and if so, setting j equal to j+1 and proceeding to step (b)(4), otherwise proceeding to step (b)(6);

(b)(6) determining if j is equal to k, and if so, proceeding to step (b)(9);

(b)(7) removing the tree D j from the set T and adding the tree D j to the set L, when D j is removed from the set T, the trees of the set T are renumbered, k is set equal to k−1, and proceeding to step (b)(8);

(b)(8) determining if j is less than or equal to k, if so, proceeding to step (b)(4), otherwise proceeding to step (b)(9);

(b)(9) determining if |L|=1, wherein |L| is the cardinality of the set L, and if so, proceeding to step (b)(10), otherwise proceeding to step (b)(11);

(b)(10) setting i equal to i+1 and proceeding to step (b)(3); and

(b)(11) determining if |L|>1, and if so, then the trees from L are symmetric for function ƒ, let L={D t , D j 1 , . . . , D j q }, and a new tree D′=S(D i , D j 1 , . . . , D j q ) is constructed utilizing a S-union operation, the tree D i is removed from the set T and the trees of the set T are renumbered, the new tree D′ is added to the set T, then the process proceeds to step (b) (3).

3. The method as described in claim 1 , wherein applying a procedure to construct an m-symmetric part to the set T′ and the function ƒ, wherein T″ is the result of the procedure is performed as follows:

(f)(1) R is set equal to Ø, wherein R is an auxiliary set of marked trees and may include new trees obtained utilizing an SN m operation, and continuing to step (f)(2);

(f)(2) determining if |T|<2m, and if so, the procedure returns the set T∪R as a result, otherwise T is greater than or equal to 2m and proceeding to step (f)(3);

(f)(3) obtaining a first subset G of the set T such that |G|=m, and continuing to step (f)(4);

(f)(4) constructing a new tree D′=N(G), setting L equal to {D′} and setting A equal to T\G, where L and A are an auxiliary sets of marked trees, the set T\G contains all elements of the set T which do not belong to the set G, and proceeding to step (f)(5);

(f)(5) obtaining a first subset Q that |Q|=m, and continuing to step (f) (6);

(f)(6) obtaining a first permutation of the set Q, and proceeding to step (f)(7);

(f)(7) constructing a new tree D″=N(Q) and proceeding to step (f)(8);

(f)(8) determining whether trees D′ and D ″ are symmetric for function ƒ, if not, the procedure proceeds to step (f)(9), if so, the procedure proceeds to step (f)(13);

(f)(9) determining if the subset is the last permutation of Q, if Q is not the last permutation, a next permutation of Q is obtained and the procedure proceeds to step (f)(7), otherwise proceeding to step (f)(10);

(f)(10) determining if Q is the last subset of A, if Q is not the last subset of set A with cardinality m, then a next subset Q is obtained such that |Q|=m and the process proceeds to step (f)(7), if Q is the last subset of the set A then the procedure proceeds to step (f)(11);

(f)(11) determining if |L| is greater than 1, if so, proceeding to step (f)(12), otherwise proceeding to step (f)(15);

(f)(12) determining if G is the last subset of T, if G is not the last subset of the set T, a next subset G is obtained such that |G|=m and the procedure proceeds to step (f)(4), if G is the last subset of the set T, the procedure returns the set T∪R as the result of the procedure;

(f)(13) setting L equal to L∪{D″}, such that the tree D″ is added to the set L, T is set equal to T\(Q∪G) and A is set equal to A\Q, and proceeding to step (f)(14);

(f)(14) determining if |A|≧m, and if |A|≧m, then proceeding to step (f)(6), otherwise if |A|<m, then the procedure proceeds to step (f)(15); and

(f)(15) constructing a new tree D′=S(L), set R equal to R∪{D′}, so that the tree D′ is added to the set R, and proceed to step (f)(2).

4. The method as described in claim 1 , wherein a data structure which describes groups of commutative variables of a Boolean function is a symmetry tree of the Boolean function.

5. The method as described in claim 1 , wherein ƒ(x 1 , . . . , x n ) is a Boolean function, a tree D is a symmetry tree for the function ƒ(x 1 , . . . , x n ) if the following conditions hold: (1) the tree D has n leaves and each leaf of the tree D is marked by some variable from X={x 1 , . . . , x n }; (2) each internal node of the tree D is marked by symbol N or S; (3) if a node of the tree D is marked by symbol S and β 1 , . . . , β m are sons of the node β then {A β 1 , . . ., A β m } is maximal symmetric relatively ƒ and {A β 1 , . . . , A β m } is maximal S-partition of the set A β ; and (4) if a node β of the tree D is marked by symbol N and β 1 , . . . , β m are sons of the node β then the set A β is not S-set of the function ƒ and for each iε{1, . . . , m}, i β i is not marked by symbol N.

6. A system for constructing a symmetry tree of a Boolean function, comprising:

a memory suitable for storing a program of instructions; and

a processor suitable for performing the program of instructions, wherein the program of instructions configures the processor to perform a method comprising steps of

(a) setting an initial set of the trees T={D 1 , . . . , D n } and function ƒ, wherein D i is a tree which includes a node marked by variable x i (i=1, . . . , n), and proceeding to step (b);

(b) applying a procedure to construct a 1-symmetric part for the set T and the function ƒ, wherein T′={D′ 1 , . . . , D′ k } is the result of the applied procedure, and proceeding to step (c);

(c) determining whether |T′|=1, if |T′|=1, then the tree D′ 1 is returned, otherwise, proceeding to step (d);

(d) determining whether |T′|>1, if |T′|>1, then m is set equal to 2, where m corresponds to m-symmetric part of the set T′, and proceeding to step (e);

(e) determining whether m>|T′|/2, and if so, constructing tree N(T′) utilizing an N-union operation and returning the tree as the result of the operation, otherwise proceeding to step (f);

(f) determining whether m<|T′|/2, and if so, applying a procedure to construct an m-symmetric part to the set T′ and the function ƒ, wherein T″ is the result of the procedure, and proceeding to step (g); and

(g) determining whether T′=T″, and if so, m is set equal to m+1 and the method returns to step (f), if T′≠T″, then T is set equal to T″ and the method returns to step (b),

wherein the method is utilized to minimize path delays and eliminate ramptime violations in internal synthesis tools for intergrated circuits.

7. The system as described in claim 6 , wherein the procedure to construct a 1symmetric part to the set T and the function ƒ of step (b), in which the input of the procedure is a Boolean function ƒ(x 1 , . . . , x n ) and a set of marked trees and the output of the procedure is a set of marked trees, is as follows:

(b)(1) receiving an input including an initial set of trees T={D 1 , . . . D k } and function ƒ, and continuing to step (b)(2);

(b)(2) setting i equal to one, and continuing to step (b)(3);

(b)(3) determining if i is less than k, if i is less than k, setting j equal to i+1, initializing an auxiliary set of trees L={D 1 } and continuing to step (b)(4), otherwise returning set T as a result of the procedure;

(b)(4) determining if trees D i and D j are symmetric for function ƒ, and if so proceeding to step (b)(7), and if not, proceeding to step (b)(5);

(b)(5) determining if j is less than k, and if so, setting j equal to j+1 and proceeding to step (b)(4), otherwise proceeding to step (b)(6);

(b)(6) determining if j is equal to k, and if so, proceeding to step (b)(9);

(b)(7) removing the tree D j from the set T and adding the tree D j to the set L, when D j is removed from the set T, the trees of the set T are renumbered, k is set equal to k−1, and proceeding to step (b)(8);

(b)(8) determining if j is less than or equal to k, if so, proceeding to step (b)(4), otherwise proceeding to step (b)(9);

(b)(9) determining if |L|=1, wherein |L| is the cardinality of the set L, and if so, proceeding to step (b)(10), otherwise proceeding to step (b)(11);

(b)(10) setting i equal to i+1 and proceeding to step (b)(3); and

(b)(11) determining if |L|>1, and if so, then the trees from L are symmetric for function ƒ, let L={D i , D j l , . . . , D j q }, and a new tree D′=S(D i , D j l , . . . , D j q ) is constructed utilizing a S-union operation, the tree D i is removed from the set T and the trees of the set T are renumbered, the new tree D′ is added to the set T, then the process proceeds to step (b)(3).

8. The system as described in claim 6 , wherein applying a procedure to construct an m-symmetric part to the set T′ and the function ƒ, wherein T″ is the result of the procedure is performed as follows:

(f)(1) R is set equal to Ø, wherein R is an auxiliary set of marked trees and may include new trees obtained utilizing an SN m operation, and continuing to step (f)(2);

(f)(2) determining if |T|<2m, and if so, the procedure returns the set T∪R as a result, otherwise |T| is greater than or equal to 2m and proceeding to step (f)(3);

(f)(3) obtaining a first subset G of the set T such that |G|=m, and continuing to step (f)(4);

(f)(4) constructing a new tree D′=N(G), setting L equal to {D′} and setting A equal to T\G, where L and A are an auxiliary sets of marked trees, the set T\G contains all elements of the set T which do not belong to the set G, and proceeding to step (f)(5);

(f)(5) obtaining a first subset Q that |Q|=m, and continuing to step (f)(6);

(f)(6) obtaining a first permutation of the set Q, and proceeding to step (f)(7);

(f)(7) constructing a new tree D″=N(Q) and proceeding to step (f)(8);

(f)(8) determining whether trees D′ and D″ are symmetric for function ƒ, if not, the procedure proceeds to step (f)(9), if so, the procedure proceeds to step (f)(13);

(f)(9) determining if the subset is the last permutation of Q, if Q is not the last permutation, a next permutation of Q is obtained and the procedure proceeds to step (f)(7), otherwise proceeding to step (f)(10);

(f)(10) determining if Q is the last subset of A, if Q is not the last subset of set A with cardinality m, then a next subset Q is obtained such that |Q|=m and the process proceeds to step (f)(7), if Q is the last subset of the set A then the procedure proceeds to step (f)(11);

(f)(11) determining if |L| is greater than 1, if so, proceeding to step (f)(12), otherwise proceeding to step (f)(15);

(f)(12) determining if G is the last subset of T, if G is not the last subset of the set T, a next subset G is obtained such that |G|=m and the procedure proceeds to step (f)(4), if G is the last subset of the set T, the procedure returns the set T∪R as the result of the procedure;

(f)(13) setting L equal to L∪{D″}, such that the tree D″ is added to the set L, T is set equal to T\(Q∪G) and A is set equal to A\Q, and proceeding to step (f)(14);

(f)(14) determining if |A|≧m, and if |A|≧m, then proceeding to step (f)(6), otherwise if |A|<m, then the procedure proceeds to step (f)(15); and

(f)(15) constructing a new tree D′=S(L), set R equal to R∪{D′}, so that the tree D′ is added to the set R, and proceed to step (f)(2).

9. The system as described in claim 6 , wherein a data structure which describes groups of commutative variables of a Boolean function is a symmetry tree of the Boolean function.

10. The system as described in claim 6 , wherein ƒ(x 1 , . . . , x n ) is a Boolean function, a tree D is a symmetry tree for the function ƒ(x 1 , . . . , x n ) if the following conditions hold: (1) the tree D has n leaves and each leaf of the tree D is marked by some variable from X={x 1 , . . . , x n }; (2) each internal node of the tree D is marked by symbol N or S; (3) if a node β of the tree D is marked by symbol S and β 1 , . . . , β m are sons of the node β then {A β 1 , . . . , A β m } is maximal symmetric relatively ƒ and {A β 1 , . . . , A β m } is maximal S-partition of the set A β ; and (4) if a node β of the tree D is marked by symbol N and β 1 , . . . , β m are sons of the node β then the set A β is not S-set of the function ƒ and for each iε{1, . . . , m}, β i is not marked by symbol N.

11. A computer-readable medium storing computer-executable method steps for constructing a symmetry tree of a Boolean function, the method comprising:

(a) setting an initial set of the trees T={D 1 , . . . , D n } and function ƒ, wherein D i is a tree which includes a node marked by variable x i (i=1, . . . , n), and proceeding to step (b);

(b) applying a procedure to construct a 1-symmetric part for the set T and the function ƒ, wherein T′={D′ 1 , . . . , D′ k } is the result of the applied procedure, and proceeding to step (c);

(c) determining whether |T′|=1, if |T′|=1, then the tree D′ 1 is returned, otherwise, proceeding to step (d);

(d) determining whether |T′|>1, if |T′|>1, then m is set equal to 2, where m corresponds to m-symmetric part of the set T′, and proceeding to step (e);

(e) determining whether m>|T′|/2, and if so, constructing tree N(T′) utilizing an N-union operation and returning the tree as the result of the operation, otherwise proceeding to step (f);

(f) determining whether m≦|T′|/2, and if so, applying a procedure to construct an m-symmetric part to the set T′ and the function ƒ, wherein T″ is the result of the procedure, and proceeding to step (g); and

(g) determining whether T′=T″, and if so, m is set equal to m+1 and the method returns to step (f), if T′≠T″, then T is set equal to T″ and the method returns to step (b),

wherein the method is utilized to minimize path delays and eliminate ramptime violations in internal synthesis tools for intergrated circuits.

12. The computer-readable medium as described in claim 11 , wherein the procedure to construct a 1-symmetric part to the set T and the function ƒ of step (b), in which the input of the procedure is a Boolean function ƒ(x 1 , . . . , x n ) and a set of marked trees and the output of the procedure is a set of marked trees, is as follows:

(b)(1) receiving an input including an initial set of trees T={D 1 , . . . D k } and function ƒ, and continuing to step (b)(2);

(b)(2) setting i equal to one, and continuing to step (b)(3);

(b)(3) determining if i is less than k, if i is less than k, setting j equal to i+1, initializing an auxiliary set of trees L={D i } and continuing to step (b)(4), otherwise returning set T as a result of the procedure;

(b)(4) determining if trees D i and D j are symmetric for function ƒ, and if so proceeding to step (b)(7), and if not, proceeding to step (b)(5);

(b)(5) determining if j is less than k, and if so, setting j equal to j+1 and proceeding to step (b)(4), otherwise proceeding to step (b)(6);

(b)(6) determining if j is equal to k, and if so, proceeding to step (b)(9);

(b)(7) removing the tree D j from the set T and adding the tree D j to the set L, when D j is removed from the set T, the trees of the set T are renumbered, k is set equal to k−1, and proceeding to step (b)(8);

(b)(8) determining if j is less than or equal to k, if so, proceeding to step (b)(4), otherwise proceeding to step (b)(9);

(b)(9) determining if |L|=1, wherein |L| is the cardinality of the set L, and if so, proceeding to step (b)(10), otherwise proceeding to step (b)(11);

(b)(10) setting i equal to i+1 and proceeding to step (b)(3); and

(b)(11) determining if |L|>1, and if so, then the trees from L are symmetric for function ƒ, let L={D i , D j l , . . . , D j q }, and a new tree D′=S(D i , D j l , . . . , D j q ) is constructed utilizing a S-union operation, the tree D i is removed from the set T and the trees of the set T are renumbered, the new tree D′ is added to the set T, then the process proceeds to step (b)(3).

13. The computer-readable medium as described in claim 11 , wherein applying a procedure to construct an m-symmetric part to the set T′ and the function ƒ, wherein T″ is the result of the procedure is performed as follows:

(f)(1) R is set equal to Ø, wherein R is an auxiliary set of marked trees and may include new trees obtained utilizing an SN m operation, and continuing to step (f)(2);

(f)(2) determining if |T|<2m, and if so, the procedure returns the set T∪R as a result, otherwise |T| is greater than or equal to 2m and proceeding to step (f)(3);

(f)(3) obtaining a first subset G of the set T such that |G|=m, and continuing to step (f)(4);

(f)(4) constructing a new tree D′=N(G), setting L equal to {D′} and setting A equal to T\G, where L and A are an auxiliary sets of marked trees, the set T\G contains all elements of the set T which do not belong to the set G, and proceeding to step (f)(5);

(f)(5) obtaining a first subset Q that |Q|=m, and continuing to step (f)(6);

(f)(6) obtaining a first permutation of the set Q, and proceeding to step (f)(7);

(f)(7) constructing a new tree D″=N(Q) and proceeding to step (f)(8);

(f)(8) determining whether trees D′ and D″ are symmetric for function ƒ, if not, the procedure proceeds to step (f)(9), if so, the procedure proceeds to step (f)(13);

(f)(9) determining if the subset is the last permutation of Q, if Q is not the last permutation, a next permutation of Q is obtained and the procedure proceeds to step (f)(7), otherwise proceeding to step (f)(10);

(f)(10) determining if Q is the last subset of A, if Q is not the last subset of set A with cardinality m, then a next subset Q is obtained such that |Q|=m and the process proceeds to step (f)(7), if Q is the last subset of the set A then the procedure proceeds to step (f)(11);

(f)(11) determining if |L| is greater than 1, if so, proceeding to step (f)(12), otherwise proceeding to step (f)(15);

(f)(12) determining if G is the last subset of T, if G is not the last subset of the set T, a next subset G is obtained such that |G|=m and the procedure proceeds to step (f)(4), if G is the last subset of the set T, the procedure returns the set T∪R as the result of the procedure;

(f)(13) setting L equal to L∪{D″}, such that the tree D″ is added to the set L, T is set equal to T\(Q∪G) and A is set equal to A\Q, and proceeding to step (f)(14);

(f)(14) determining if |A|≧m, and if |A|≧m, then proceeding to step (f)(6), otherwise if |A|<m, then the procedure proceeds to step (f)(15); and

(f)(15) constructing a new tree D′=S(L), set R equal to R∪{D′}, so that the tree D′ is added to the set R, and proceed to step (f)(2).

14. The computer-readable medium as described in claim 11 , wherein a data structure which describes groups of commutative variables of a Boolean function is a symmetry tree of the Boolean function.

15. The computer-readable medium as described in claim 11 , wherein ƒ(x 1 , . . . , x n ) is a Boolean function, a tree D is a symmetry tree for the function ƒ(x 1 , . . . , x n ) if the following conditions hold: (1) the tree D has n leaves and each leaf of the tree D is marked by some variable from X={x 1 , . . . , x n }; (2) each internal node of the tree D is marked by symbol N or S, (3) if a node β of the tree D is marked by symbol S and β 1 , . . . , β m are sons of the node β then {A β 1 , . . . , A β m } is maximal symmetric relatively ƒ and {A β 1 , . . . , A β m }is maximal S-partition of the set A β ; and (4) if a node β of the tree D is marked by symbol N and β 1 , . . . , β m are sons of the node β then the set A β is not S-set of the function ƒ and for each i ε{1, . . . , m}, i β i is not marked by symbol N.

Assignments (9)