Granted Patent B2

US 6,842,750 · App. 10/108,286 · Granted Jan 11, 2005

Abstract

Claims (77)

1. A computer executable method for reducing redundancy in a simulation through use of a symbolic simulation utilizing an arbitrary library, comprising:

receiving a set A of values, the set A including input variables which are elements of the set A;

constructing symbols of the input variables in which like and similar variables share a like symbol and a similar symbol respectively;

forming a table of output values computed from a table of a Boolean operator employing the constructed symbols of the input variable; and

creating output symbols from the table of output values, wherein if all bits of a table index i of the table of output values (Ty_i) is constant, the symbol b i for the index is set equal to the constant; if the table output index i of the table of output values (Ty_i) is equal to a Boolean variable (X_j), the symbol b_i is set equal to the input variable symbol constructed from the value of input variable; if the table output index i of the table of output values (Ty_i) is approximately equal to a Boolean variable (X_j), the symbol b_i is set approximately equal to the input variable symbol constructed from the value of input variable; otherwise the symbol b_i is set as undefined.

2. The method as described in claim 1 , wherein

A is denoted as the set {0, 1,v_ 1 ,v_ 2 , . . . ,v_N,˜v_ 1 ,˜v_ 2 , . . . ,˜v_n};

the Boolean operator has inputs x_ 1 , . . . ,x_m and outputs y_ 1 , . . . ,y_k so that the Boolean operator may be denoted as F(y_ 1 , . . . ,y_k, x_ 1 , . . . , x_m);

a_ 1 , . . . ,a_m are values of input variables that are elements of the set A; and

n is a number of different indexes i from { 1 , . . . ,N} so that v_i or ˜v_i is included in the list a_ 1 , . . . , a_m;

symbols U_ 1 , . . . ,U_m and W_ 1 , . . . , W_n are constructed utilizing the values of input variables.

3. The method as described in claim 2 , wherein constructing symbols U_ 1 , . . . ,U_m and W_ 1 , . . . ,W_n is performed as follows:

(a) s=1 and i=1;

(b) if i is not less than m, end method;

(c) if i is less than m, set j=1;

(d) if j is less than i proceed to step (e), otherwise proceed to step (h);

(e) determine if a i ==a j , if yes, set f=1 and U i =U j and proceed to step (h), otherwise proceed to step (f);

(f) determine if a i ==˜a j , if yes, set f=−1 and U i =˜U j and proceed to step (h), otherwise proceed to step (g);

(g) increment j and proceed to step (d);

(h) determine if f==0, if no proceed to step (i), otherwise proceed to step (j)

(i) increment i and proceed to step (b);

(j) set U i =X s ; W s =a i ; increment s and proceed to step (b).

4. The method as described in claim 2 , wherein the table of outputs is formed as follows: the Boolean operator including the constructed symbols, denoted as F(y_ 1 , . . . ,y_k,U_ 1 , . . . , U_m), is set equal to G(y_ 1 , . . . , y_k, X_ 1 , . . . ,X_m); utilizing a table of the operator F, G is computed for values of X_ 1 , . . . X_n, in which Ty_ 1 , . . . ,Ty_k are table of size 2^{n} of values of outputs y_ 1 , . . . ,y_k, and TX_ 1 , . . . ,TX_n are tables of size 2^{n} of selector functions X_ 1 , . . . , X_n.

5. The method as described in claim 1 , further comprising

obtaining a netlist;

splitting the obtained netlist into at least two instance sets, including logical non sequential instance sets and all others;

making an ordered logic instances list;

constructing a simulation alphabet A from names of netlist nets, wherein a simulation value S(NT) is computed from A for each net NT and utilized to optimize the simulation alphabet; and

proceeding through the ordered instances list, let i-th intake is (F.y_ 1 (NO_ 1 ), . . . ,Y_k(NO_k),.x_ 1 (NI_ 1 ), . . . ,.x_m(NI_m)); where x− 1 , . . . ,x_m are inputs and y_ 1 , . . . ,y_k are outputs, values S(NO_ 1 ), . . . ,S(NO_k) are computed in accordance with the method of claim 3 , wherein if S(NO)i is undefined, then S(NO_i) is set equal to NO_i.

6. The method as described in claim 5 , wherein for each instance in the list, a driver of an input net may include at least one of an input port of netlist; output of non logical cell; and output of logical cell with smaller index in ordered list.

7. The method as described in claim 5 , wherein a global simplification method is applied to a netlist.

8. The method as described in claim 7 , wherein global simplification includes constructing a set of variables V from the ordered instances list which includes at least one of input port of the netlist and outputs of non logical cells.

9. The method as described in claim 8 , wherein in a i-th logic instance F(.y_ 1 (NO_ 1 ), . . . ,.y_k(NO_k),.x_ 1 (NI_ 1 ), . . . ,.x_m(NI_m)), if a value S(NO_i) is at least one of not variable and variable from set V, the value S(NO_i) is undefined; otherwise variable S(NO_i) is added to set V.

10. The method as described in claim 9 , wherein netlist nets marked as undefined are removed and instances in which directed connections to output of a logical subnetlist are not available, including at least one of output ports of netlist and inputs of non logical elements.

11. The method as described in claim 7 , wherein a local simplification method is employed including at least one of output pins of a cell marked as undefined are eliminated; input pins of a cell marked by constant are simplified; and input pins of a cell at least one of marked by negations of a variable and pins having at least one of similar and inverse marks are combined.

12. A system for performing a simulation, comprising:

a memory suitable for storing a program of instructions; and

a processor communicatively coupled to the memory, wherein the program of instructions configures the processor to

receive a set A of values of a netlist, the set A including input variables which are elements of the set A;

construct symbols of the input variables in which like and similar variables share a like symbol and a similar symbol respectively;

form a table of output values computed from a table of a Boolean operator; and

create output symbols from the table of output values, wherein if all bits of a table index i of the table of output values (Ty_i) is constant, the symbol b_i for the index is set equal to the constant; if the table output index i of the table of output values (Ty_i) is equal to a Boolean variable (X_j), the symbol b_i is set equal to the input variable symbol constructed from the value of input variable; if the table output index i of the table of output values (Ty_i) is approximately equal to a Boolean variable (X_j), the symbol b_i is set approximately equal to the input variable symbol constructed from the value of input variable; otherwise the symbol b_i is set as undefined.

13. The system as described in claim 12 , wherein

A is denoted as the set {0, 1,v_ 1 ,v_ 2 , . . . ,v_N,˜v_ 1 ,˜v_ 2 , . . . ,˜v_n};

the Boolean operator has inputs x_ 1 , . . . ,x_m and outputs y_ 1 , . . . , y_k so that the Boolean operator may be denoted as F(y_ 1 , . . . ,y_k, x_ 1 , . . . , x_m);

a_ 1 , . . . ,a_m are values of input variables that are elements of the set A; and

n is a number of different indexes i from { 1 , . . . , N} so that v_i or ˜v_i is included in the list a_ 1 , . . . ,a_m;

symbols U_ 1 , . . . ,U_m and W_ 1 , . . . ,W_n are constructed utilizing the values of input variables.

14. The system as described in claim 13 , wherein constructing symbols U_ 1 , . . . ,U_m and W_ 1 , . . . ,W_n is performed as follows:

(a) s=1 and i=1;

(b) if i is not less than m, end method;

(c) if i is less than m, set j=1;

(d) if j is less than i proceed to step (e), otherwise proceed to step (h);

(e) determine if a i ==a j , if yes, set f=1 and U i =U j and proceed to step (h), otherwise proceed to step (f);

(f) determine if a i ==˜a j , if yes, set f=−1 and U i =˜U j and proceed to step (h), otherwise proceed to step (g);

(g) increment j and proceed to step (d);

(h) determine if f==0, if no proceed to step (i), otherwise proceed to step (j)

(i) increment i and proceed to step (b);

(j) set U i =X s ; W s =a i ; increment s and proceed to step (b).

15. The system as described in claim 13 , wherein the table of outputs is formed as follows: the Boolean operator including the constructed symbols, denoted as F(y_ 1 , . . . , y_k, U_ 1 , . . . ,U_m), is set equal to G(y_ 1 , . . . , y_k, X_ 1 , . . . ,X_m); utilizing a table of the operator F, G is computed for values of X_ 1 , . . . X_n, in which Ty_ 1 , . . . , Ty_k are table of size 2^{n} of values of outputs y_ 1 , . . . ,y_k, and TX_ 1 , . . . ,TX_n are tables of size 2^{n} of selector functions X_ 1 , . . . ,X_n.

16. The system as described in claim 12 , further comprising

obtaining a netlist;

splitting the obtained netlist into at least two instance sets, including logical non sequential instance sets and all others;

making an ordered logic instances list;

constructing a simulation alphabet A from names of netlist nets, wherein a simulation value S(NT) is computed from A for each net NT and utilized to optimize the simulation alphabet; and

proceeding through the ordered instances list, let i-th intake is (F.y_ 1 (NO− 1 ), . . . ,Y_k(NO_k),.x_ 1 (NI_ 1 ), . . . ,.x_m(NI_m)); where x− 1 , . . . ,x_m are inputs and y_ 1 , . . . ,y_k are outputs, values S(NO_ 1 ), . . . ,S(NO_k) are computed in accordance with the method of claim 3 , wherein if S(NO)i is undefined, then S(NO_i) is set equal to NO_i.

17. The system as described in claim 16 , wherein for each instance in the list, a driver of an input net may include at least one of an input port of netlist; output of non logical cell; and output of logical cell with smaller index in ordered list.

18. The system as described in claim 16 , wherein a global simplification method is applied to a netlist.

19. The system as described in claim 18 , wherein global simplification includes constructing a set of variables V from the ordered instances list which includes at least one of input port of the netlist and outputs of non logical cells.

20. The system as described in claim 19 , wherein in a i-th logic instance F(.y_ 1 (NO_ 1 ), . . . ,.y_k(NO_k),.x_ 1 (NI_ 1 ), . . . ,.x_m(NI_m)), if a value S(NO_i) is at least one of not variable and variable from set V, the value S(NO_i) is undefined; otherwise variable S(NO_i) is added to set V.

21. The system as described in claim 20 , wherein netlist nets marked as undefined are removed and instances in which directed connections to output of a logical subnetlist are not available, including at least one of output ports of netlist and inputs of non logical elements.

22. The system as described in claim 18 , wherein a local simplification method is employed including at least one of output pins of a cell marked as undefined are eliminated; input pins of a cell marked by constant are simplified; and input pins of a cell at least one of marked by negations of a variable and pins having at least one of similar and inverse marks are combined.

23. A computer executable system for performing simulation comprising:

means for receiving a set A of values, the set A including input variables which are elements of the set A;

means for constructing symbols of the input variables received by the receiving means, in which like and similar variables share a like symbol and a similar symbol respectively;

means for forming a table of output values computed from a table of a Boolean operator, the Boolean operator having the symbols constructed by the constructing means; and

means for creating output symbols from the table of output values obtained from the forming means, wherein if all bits of a table index i of the table of output values (Ty_i) is constant, the symbol b i for the index is set equal to the constant; if the table output index i of the table of output values (Ty_i) is equal to a Boolean variable (X_j), the symbol b_i is set equal to the input variable symbol constructed from the value of input variable; if the table output index i of the table of output values (Ty_i) is approximately equal to a Boolean variable (X_j), the symbol b_i is set approximately equal to the input variable symbol constructed from the value of input variable; otherwise the symbol b_i is set as undefined.

Assignments (9)