Symbolic simulation driven netlist simplification

[00002] The present application incorporates by reference in their entirety U.S. Pat. No. 6,553,370, titled “Flexible Search Engine Having Sorted Binary Search Tree for Perfect Match” filed Oct. 4, 2000; and U.S. Pat. No. 6,564,211, titled “Fast Flexible Search Engine for Longest Prefix Match”, filed Oct. 4, 2000.

[00003] The present invention generally relates to the field netlists, and particularly to a symbolic simulation driven netlist simplification.

[00004] As the desire for increased and wide-ranging integrated circuit functionality continue to expand, manufacturers and designers of integrated circuits (IC) are confronted with the associated increase in complexity. Therefore, when designing and testing an integrated circuit, tasks which were relatively efficient when circuit designs contained fewer elements have increased in complexity where a task thought relatively simple before may now take weeks to perform.

[00005] For example, in designing an integrated circuit (IC), a netlist may be employed to describe names of components and connection points which are logically connected in each net of a circuit. Additionally, it may be useful to employ a descriptor language, such as a register transfer language (RTL), to be used in describing registers in an information handling system, such as a desktop computer, server, digital information appliance, convergence device, and the like, and how data is transferred between the registers.

[00006] However, a netlist, after complication from an RTL level to a generic library, may contain redundant elements. For example, a netlist may contain constants, equivalent nets, inverted pairs of nets, and the like redundant fragments. Further, many compilers may not contain optimizations which may be utilized to simplify the structure. However, standard and nonstandard elements may be encountered, so that optimization may be difficult utilizing a predefined library.

[00007] Therefore, it would be desirable to provide a simplification system and method for an arbitrary library.

[00008] Accordingly, the present invention is directed to a simplification method for an arbitrary library. In aspects of the present invention, the method does not rely on specific properties of the library elements and has linear complexity. The present invention may be implemented based on a symbolic simulation in an alphabet which contains 0, 1, symbols of variables, and negations of the variables' symbols.

[00009] In an aspect of the present invention, a method for reducing redundancy in a simulation through use of a symbolic simulation utilizing an arbitrary library includes receiving a set A of values, the set A including input variables which are elements of the set A. Symbols of the input variables are constructed in which like and similar variables share a like symbol and a similar symbol respectively. A table of output values computed from a table of a Boolean operator employing the constructed symbols of the input variable is formed. Output symbols from the table of output values are created according to the following method. 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.

[00010] It is to be understood that both the forgoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the invention as claimed. The accompanying drawings, which are incorporated in and constitute a part of the specification, illustrate an embodiment of the invention and together with the general description, serve to explain the principles of the invention.

[00015] Reference will now be made in detail to the presently preferred embodiments of the invention, examples of which are illustrated in the accompanying drawings.

[00016] Referring generally now to FIGS. 1 through 3, exemplary embodiments of the present invention are shown. The present invention provides a fast simplification procedure of a netlist given in an arbitrary library in order to decrease the area and increase the performance. The present invention has a variety of uses, such as in FFS High Speed Lookup Engines for a perfect and longest prefix matches [1,2], is applicable for any design netlist given in a generic or a technology library, and the like as contemplated by a person of ordinary skill in the art.

[00017] Generally, netlists are redundant after compilation from RTL level to the generic library. For instance, netlists may contain constants, equivalent nets, inverted pairs of nets and other redundant fragments. In the case of a compilation FFS search engine from C++ to generic netlist, a large redundancy may be encountered, mainly because a compiler may not contain some optimizations. For example, the generic library of a FFS compiler may contain standard elements and other more complex elements, such as pieces of comparators, adders and other data-path operators. By utilizing the present invention, simplification methods are provided which are fast and effective in the case of an arbitrary library.

[00018] Simplification methods are provided by the present invention which may be employed for an arbitrary library. The methods need not use specific properties of the library elements, and in aspects of the present invention, the methods have linear complexity. The method may be based on the symbolic simulation in the alphabet which contains 0, 1, the symbols of variables, the negations of variables symbols.

[heading-00019] Local Simulation

[00020] For example, let A be the set {0, 1, v_1, v_2, . . . , v_N,˜v_1,˜v_2, . . . ,˜v_N}. Additionally, let F(y_1, . . . ,y_k,x_1, . . . ,x_m) be a Boolean operator with inputs x_1, . . . ,x_m and outputs y_1, . . . ,y_k. Further, let a_1, . . . ,a_m be values of input variables, which are elements of the set A.

[00021] Described in this section is a method of computation of symbolic values on outputs of the operator F. Let n be the number of different indexes i from {1, . . . ,N}, that v_i or ˜v_i is in the list a_1, . . . ,a_m. Additionally, X_1, . . . ,X_n are Boolean variables. Symbols U_1, . . . ,U_m and W_1, . . . ,W_n are constructed by the method 100 depicted in FIG. 1. Suppose ˜˜v_i=v_i and ˜˜X_i=X_i. In FIG. 1, symbols are constructed from like and similar value of input variables to reduce redundancy.

[00022] Consider Boolean operator G(y_1, . . . ,y_k,X_1, . . . ,X_n)=F(y_1, . . . ,y_k,U_1, . . . , U_m). By using the table of the operator F, G is computed for all possible values of X_1, . . . ,X_n. Let Ty_1, . . . ,Ty_k be the tables of size 2^{n} of values of outputs y_1, . . . ,y_k. Further, let TX_1, . . . , TX_n are the tables of size 2^{n} of the selector functions X_1, . . . , X_n.

[00023] The output symbols b_1, . . . , b_k are computed by below rules:

• • [00024] if all bits of Ty_i are 0, then b_i=0;
  • [00025] if all bits of Ty_i are 1, then b_i=1:
  • [00026] if Ty_i==X_j, then b_i=W_j;
  • [00027] if Ty_i==˜X_j, then b_i=˜W_j;
  • [00028] otherwise b_i=*, i.e. undefined.
    It should be noted that each b_i is a symbol from A or *. In this way, symbols are created for an arbitrary library in an efficient manner to reduce redundancy by utilizing symbols for same and similar values; and determining and storing constants to further reduce processing.

[00030] For instance, referring to the exemplary method 200 shown in FIG. 2, a method for performing a local symbolic simulation in an efficient manner is shown. A set “A” of values is received 202, such as by an information handling system operable to employ the present invention, and the like. Symbols are constructed of input variables, in which, symbols are shared between like and similar variables 204.

[00031] A table of output values is then computed from a table of a Boolean operator 206. Output symbols are then created from the table of output values 208. Creating output symbols may include determining constants, combining like and similar output values into like and similar symbols, combining positive and negative like variables that are denoted as such, and the like as contemplated by a person of ordinary skill in the art without departing from the spirit and scope thereof.

[heading-00032] Global Simulation

[00033] The following is an example of a global simulation. A netlist is split into two instances sets: logical non sequential and all others. The ordered logic instances list may be constructed by a variety of algorithms. For each instance in the list a driver of any input net may be the following:

• • [00034] input port of netlist,
  • [00035] output of non logical cell,
  • [00036] output of logical cell with smaller index in the ordered list.

[00037] A simulation alphabet A may be constructed from the names of all netlist nets. A simulation value S(NT) is computed from A for each net NT. On the first step:

• • [00038] if NT_i is constant 0 then S_i=0;
  • [00039] if NT_i is constant 1 then S_i=1;
  • [00040] if NT_i is input port of netlist or output of non logical cell then S_i=NT_i.

[00041] On the next step, the ordered instances lists are processed. Let i-th instance 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.

[00042] The simulation values S(NI_1), . . . ,S(NI_m) are already known. Values S(NO_1), . . . ,S(NO_k) are computed in accordance with the above section algorithm. If S(NO_i)==* is obtained, then S(NO_i) is set equal to NO_i.

[00043] Next, set of variables V are constructed by progressing through the ordered instances list. On the first step, this may include the input ports of the netlist and the outputs of the non logical cells. Considering the i-th logic instance, which may be represented as follows:
F(.y_1(NO_1), . . . ,y_k(NO_k),.x_1(NI_1), . . . ,.x_m(NI_m)).
If the value S(NO_i) is not variable or variable from set V, the value may be denoted as undefined, i.e. *, otherwise the variable S(NO_i) is added to the set V.

[00046] To further simplify, the netlist nets marked by * are removed. Additionally, and remove all instances which do not have directed connection to the outputs of logical subnetlist may be removed, such as output ports of netlist, inputs of non logical elements, and the like. An exemplary method 300 suitable for providing such global simulation is shown in FIG. 3.

[heading-00047] Local Simplification

[00048] After above procedure, further optimizations may be performed. For example, output pins of a cell are marked by * may be deleted, input pins of a cell are marked by constant may be noted, input pins of a cell are marked by negations of variables may be combined; pins having similar or inverse outputs may be combined, and the like as contemplated by a person of ordinary skill in the art. These situations may be solved inside library rules, for instance, if simpler elements with corresponding functionality are available.

[00049] In exemplary embodiments, the methods disclosed may be implemented as sets of instructions or software readable by a device. Further, it is understood that the specific order or hierarchy of steps in the methods disclosed are examples of exemplary approaches. Based upon design preferences, it is understood that the specific order or hierarchy of steps in the method can be rearranged while remaining within the scope of the present invention. The accompanying method claims present elements of the various steps in a sample order, and are not meant to be limited to the specific order or hierarchy presented.

[00050] Although the invention has been described with a certain degree of particularity, it should be recognized that elements thereof may be altered by persons skilled in the art without departing from the spirit and scope of the invention. One of the embodiments of the invention can be implemented as sets of instructions resident in the memory of one or more information handling systems, which may include memory for storing a program of instructions and a processor for performing the program of instruction, wherein the program of instructions configures the processor and information handling system. Until required by the information handling system, the set of instructions may be stored in another readable memory device, for example in a hard disk drive or in a removable medium such as an optical disc for utilization in a CD-ROM drive and/or digital video disc (DVD) drive, a compact disc such as a compact disc-rewriteable (CD-RW), compact disc-recordable and erasable; a floppy disk for utilization in a floppy disk drive; a floppy/optical disc for utilization in a floppy/optical drive; a memory card such as a memory stick, personal computer memory card for utilization in a personal computer card slot, and the like. Further, the set of instructions can be stored in the memory of an information handling system and transmitted over a local area network or a wide area network, such as the Internet, when desired by the user.

[00051] Additionally, the instructions may be transmitted over a network in the form of an applet that is interpreted or compiled after transmission to the computer system rather than prior to transmission. One skilled in the art would appreciate that the physical storage of the sets of instructions or applets physically changes the medium upon which it is stored electrically, magnetically, chemically, physically, optically or holographically so that the medium carries computer readable information.

[00052] It is believed that the system and method of the present invention and many of its attendant advantages will be understood by the forgoing description. It is also believed that it will be apparent that various changes may be made in the form, construction and arrangement of the components thereof without departing from the scope and spirit of the invention or without sacrificing all of its material advantages. The form herein before described being merely an explanatory embodiment thereof. It is the intention of the following claims to encompass and include such changes.