Method and apparatus for distinguishing combinational designs

[0001] The present invention relates generally to the comparison of combinational designs with the purpose of determining whether they are functionally different.

[0002] Techniques for determining whether two combinational designs are functionally different (which can be referred to as “combinational design discriminators” or CDDs) have a wide range of applications.

[0003] An example application of CDDs, within the area of ASIC design, is for EDA software that needs to determine whether two sequential designs are equivalent (which can be referred to as the “sequential equivalence problem”). In the sequential equivalence problem, the two designs to be compared can be referred to as the “reference” and “implementation” designs. More generally, the two designs to be compared can be referred to as a first compare design and a second compare design. An overview of known ASIC design flow is presented below. Next a known approach to solving the sequential equivalence problem is presented.

[0004] An Overview of Known ASIC Design Flow

[0005] Before proceeding further with the description, it may be helpful to place this process in context. FIG. 21 shows a simplified representation of an exemplary digital ASIC design flow. At a high level, the process starts with the product idea (step 2100) and is realized in an EDA software design process (step 2110). When the design is finalized, it can be taped-out (event 2140). After tape out, the fabrication process (step 2150) and packaging and assembly processes (step 2160) occur resulting, ultimately, in finished chips (result 2170).

[0006] The EDA software design process (step 2110) is actually composed of a number of steps 2112-2130, shown in linear fashion for simplicity. In an actual ASIC design process, the particular design might have to go back through steps until certain tests are passed. Similarly, in any actual design process, these steps may occur in different orders and combinations. This description is therefore provided by way of context and general explanation rather than as a specific, or recommended, design flow for a particular ASIC.

[0007] A brief description of the components steps of the EDA software design process (step 2110) will now be provided. The sequential equivalence problem can occur in step 2118 (“Netlist verification”), since this is when a designer can have a reference design (resulting from step 2114 “Logic design and functional verification”) and an implementation design (resulting from step 2116 “Synthesis and design for test”):

• [0008] a) System design (step 2112): The designers describe the functionality that they want to implement; they can perform what-if planning to refine functionality, check costs, etc. Hardware-software architecture partitioning can occur at this stage. Exemplary EDA software products from Synopsys, Inc. that can be used at this step include Model Architect, Saber, System Studio, and DesignWare® products.
• [0009] b) Logic design and functional verification (step 2114): At this stage, the VHDL or Verilog code for modules in the system is written and the design is checked for functional accuracy. More specifically, the design is checked to ensure production of functionally correct outputs. Exemplary EDA software products from Synopsys, Inc. that can be used at this step include VCS, VERA, DesignWare®, Magellan, Formality, ESP and LEDA products.
• [0010] c) Synthesis and design for test (step 2116): Here, the VHDL/Verilog is translated to a netlist. The netlist can be optimized for the target technology. Additionally, the design and implementation of tests to permit checking of the finished chip occurs. Exemplary EDA software products from Synopsys, Inc. that can be used at this step include Design Compiler®, Physical Compiler, Test Compiler, Power Compiler, FPGA Compiler, Tetramax, and DesignWare® products.
• [0011] d) Netlist verification (step 2118): At this step, the netlist is checked for compliance with timing constraints and for correspondence with the VHDL/Verilog source code. Exemplary EDA software products from Synopsys, Inc. that can be used at this step include Formality, PrimeTime, and VCS products.
• [0012] e) Design planning (step 2120): Here, an overall floorplan for the chip is constructed and analyzed for timing and top-level routing. Exemplary EDA software products from Synopsys, Inc. that can be used at this step include Astro and IC Compiler products.
• [0013] f) Physical implementation (step 2122): The placement (positioning of circuit elements) and routing (connection of the same) occurs at this step. Exemplary EDA software products from Synopsys, Inc. that can be used at this step include the Astro and IC Compiler products.
• [0014] g) Analysis and extraction (step 2124): At this step, the circuit function is verified at a transistor level, this in turn permits what-if refinement. Exemplary EDA software products from Synopsys, Inc. that can be used at this step include AstroRail, PrimeRail, Primetime, and Star RC/XT products.
• [0015] h) Physical verification (step 2126): At this step various checking functions are performed to ensure correctness for: manufacturing, electrical issues, lithographic issues, and circuitry. Exemplary EDA software products from Synopsys, Inc. that can be used at this step include the Hercules product.
• [0016] i) Resolution enhancement (step 2128): This step involves geometric manipulations of the layout to improve manufacturability of the design. Exemplary EDA software products from Synopsys, Inc. that can be used at this step include Proteus, ProteusAF, and PSMGen products.
• [0017] j) Mask data preparation (step 2130): This step provides the “tape-out” data for production of masks for lithographic use to produce finished chips. Exemplary EDA software products from Synopsys, Inc. that can be used at this step include the CATS(R) family of products.

[0018] An Example Approach To Solving The Sequential Equivalence Problem

[0019] For each of the first and second compare designs, a set of representative combinational sub-designs can be determined. The set of representative combinational sub-designs for the first compare design can be referred to as the “first combinational sub-designs” and the set of representative combinational designs for the second compare design can be referred to as the “second combinational sub-designs.”

[0020] As an example, a combinational sub-design can represent the next-state function for one bit of state, in either the first or second compare design.

[0021] A goal, in the solution of the sequential equivalence problem, can be for each member of the first combinational sub-designs to be paired with a corresponding member of the second combinational sub-designs. Each such pair of designs can be referred to as a “combinational design pair.” A process, by which combinational design pairs can be identified, with a CDD, can include the following steps. A subset of the first combinational sub-designs and a subset of the second combinational sub-designs can be combined to create an equivalence class (or “EC”). This EC, that can be referred to as “EC_—for_CDD,” can be divided into smaller ECs by determining, with a CDD, that pairs of combinational designs, within EC_for_CDD, are functionally distinct. A goal of such subdivision can be to convert EC_for_CDD into a set of smaller ECs, where each of the smaller ECs is a combinational design pair.

[0022] Once all combinational design pairs have been identified, the potential equivalence, between the members of each such pair, can be addressed. If the members of a combinational design pair are equivalent, the pair can be referred to as an “equivalent combinational design pair.”

[0023] If all combinational design pairs are equivalent combinational design pairs, the first compare design and the second compare design are equivalent.

[0024] It is important to note that even if a particular CDD has placed two combinational designs in the same combinational design pair, it does not mean the combinational design pair, if processed for equivalence determination, will be found to represent equivalent functions. Unless one has gone to the computational effort of determining, positively, whether the members of a combinational design pair are in-fact equivalent, it can be the case that a better CDD can rule-out the same combinational design pair as a candidate for application to an equivalence determination process.

[0025] Therefore, while there are known methods of combinational design discrimination, there is a need for better methods of discriminating between combinational designs such that a more computationally expensive step (e.g., that of positive equivalence determination) can be avoided as often as possible.

[0026] Please refer to the Glossary of Selected Terms, included at the end of the Detailed Description, for the definition of selected terms used in the below Summary. Section numbers in the below Summary correspond to section numbers in the Detailed Description.

[0027] Processes are described for application of minterm counting, both ordinary minterm counting (OMC) and weighted minterm counting (WMC), as combinational design discriminators (CDDs). The processes operate by applying minterm counting to a pair of combinational sub-designs D1 and D2. Each such sub-design can be regarded as comprised of n input variables and one output variable.

[0028] Regardless of whether the minterm counting is OMC or WMC, when don't cares are not utilized, a general process for application of minterm counting is as follows.

[0029] D1 and D2 can each be converted into a data representation (e.g., the BDD data representation) suitable for application of minterm counting. Suitable data representations for D1 and D2 can be referred to as, respectively, D1_DREP and D2_DREP. Regardless of the type of data structure used, it can be viewed as being representative of a set of minterms, where the set of minterms defines a functionality of the sub-design.

[0030] Prior to conversion of D1 and D2 into D1_DREP and D2_DREP the input variables of D1 and D2 can be reduced by assigning binary values to some of them.

[0031] D1_DREP and D2_DREP can each be assigned a minterm count, respectively MC_D1_DREP and MC_D2_DREP, that is equivalent to assigning an appropriate weighting to the set of minterms each such data structure represents.

[0032] If MC_D1_DREP and MC_D2_DREP are within a certain tolerance of each other, then D1 and D2 cannot be distinguished by the particular type of minterm counting applied.

[0033] If MC_D1_DREP and MC_D2_DREP are not within a certain tolerance of each other, then it is known that D1 and D2 represent different functionalities.

[0034] Even if D1 and D2, in a strict sense, represent different functionalities, their functionalities may still be sufficiently related such that classification of D1 and D2 as differing functionalities is inappropriate. Each such test of relatedness, between a pair of sub-designs D1, and D2, is referred to herein as an “exception.”

[0035] A general process for application of minterm counting, when don't cares are part of a design specification, is as follows.

[0036] A D1 can have an input combination for which the designer has specified a “don't care” as to what output is produced. Such an input combination can match any corresponding value produced by D2. A D1 can contain one or more “don't care” combinations.

[0037] In order to express one or more “don't care” combinations, a design D1 can be expressed by any two of the following types of design specifications: D1_dc, D1_min and D1_max. D1_dc is defined to produce a true value for each set of input combinations, inputs_x, for which a designer has specified a “don't care.” For each set of input combinations to D1, D1_min and D1_max are defined to produce the same value, except for any set of inputs inputs_x for which D1_dc produces a true value. For each inputs_x where D1_dc produces a true value, D1_min is defined to produce a zero and D1_max is defined to produce a one.

[0038] Suitable minterm counting data representations of D1_dc, D1_min and D1_max, referred to respectively as D1_dc,DREP, D1_min,DREP and D1_max,DREP, are determined. D1_dc,DREP, D1_min,DREP and D1_max,DREP can be determined provided the user has input at least two of D1_dc, D1_min and D1_max. An example suitable data representation, for minterm counting, is a BDD. Regardless of the type of data structure used, it can be viewed as being representative of a set of minterms that can determine a functionality of D1_dc, D1_min or D1_max.

[0039] A suitable minterm counting data representation for D2, referred to as D2_DREP, can be determined.

[0040] Prior to the production of D1_dc,DREP, D1_min,DREP, D1_max,DREP and D2_DREP, the support of the sub-designs from each is determined. Each of these supports can be reduced by assigning binary values to some of the variables that would be included in the support.

[0041] D1_min,DREP, D1_max,DREP and D2_DREP can each be assigned a minterm count, respectively MC_D1_min,DREP, MC_D1_max,DREP and MC_D2_DREP. Determining a minterm count, for a data representation suitable for minterm counting, is equivalent to assigning an appropriate weighting to the set of minterms each such data structure represents.

[0042] A minterm count MC_D2_min,DREP can also be determined from D1_dc,DREP and D2_DREP.

[0043] If the following relations are satisfied, then D1 and D2 cannot be distinguished by the particular type of minterm counting applied: $\mathrm{if}\left(\begin{array}{c}\left[\mathrm{mc}\left(D{1}_{\min }\right)=\mathrm{mc}\left(D2\bigwedge -D{1}_{\mathrm{dc}}\right)\right]\\ \mathrm{AND}\\ \left[\mathrm{mc}\left(D{1}_{\min }\right)\le \mathrm{mc}\left(D2\right)\le \mathrm{mc}\left(D{1}_{\max }\right)\right]\end{array}\right)$

• • [0044] then keep D1 and D2 in same EC

[0045] The above relation depicts two expressions, one on either side of an AND operator. If the expressions before and after the AND are determined to be true, then the relationship between D2 and D1 is consistent with D2 being within the range of functions encompassed by D1.

[0046] Even if D1 and D2, in a strict sense, represent different functionalities, it may still be the case that their functionalities are sufficiently related such that classification of D1 and D2 as differing functionalities is inappropriate. Each such test of relatedness, between a D1 and D2, is referred to herein as an “exception.”

[0047] A known form of minterm counting is referred to herein as “ordinary” minterm counting or OMC. Application of OMC, to a suitable data representation of a sub-design, is as follows. OMC determines an integer that represents the sub-design. Regardless of how the integer is determined, it can be viewed as being equivalent to assigning a value of one to each minterm of the sub-design and computing the sum of all such assigned values.

[0048] Rather than assigning the same weight (e.g., a weight of one) to each minterm, weighted minterm counting (WMC) assigns a weight that can vary. Such weight can vary, for example, by being a function of the particular literals of which a minterm is comprised.

[0049] For example, a weight can be assigned to each variable, comprising a minterm, that is a function of the particular variable and whether the variable is required to be in true or complemented form. The function, that assigns a weight to each variable of a minterm, can be referred to as a variable-level weighting function (VLWF). Example VLWFs are presented.

[0050] The weights assigned to each variable of a minterm can be combined, according to an appropriate function (referred to as a minterm-level weighting function or MLWF), to arrive at a total weight for each minterm. An example MLWF is finding the product of the weights assigned to each variable of a minterm.

[0051] The minterm weights for a particular combinational sub-design can be combined, according to an appropriate function (referred to as a design-level weighting function or DLWF), to arrive at a total weight for the sub-design. An example DLWF is to take the sum of the weights assigned to each minterm.

[0052] Where a sub-design is expressed as a BDD, and where the VLWF, MLWF and DLWF to be applied are known, a suitable set of expressions, for the efficient determination of the BDD's WMC, can be determined.

[0053] A set of expressions is presented for the case where the DLWF is summation, the MLWF is multiplication and the VLWF satisfies certain constraints.

[0054] Even if OMC indicates D1 and D2 are different, there can be exceptions to classifying the designs into different equivalence classes. The two basic types of exceptions are: output inversion and input inversion. These two basic types of exceptions can be combined to produce a total of three exception types. Each of these exception types is addressed below.

[0055] The output inversion exception can be expressed as follows: D1 is consistent with being the same as D2, except that the output of D2 is inverted with respect to the output of D1. Example expressions, for testing for the output inversion exception, are presented.

[0056] Using known techniques, one can determine the following: whether, as a necessary-but-insufficient condition for equivalency between D1 and D2, a pair of corresponding inputs, one input applied to D1 and the other input applied to D2, must be inverted with respect to each other.

[0057] Each pair of inputs identified as needing to be inverted, as a necessary-but-insufficient condition, can then be further tested to determine whether the pair is consistent with being inverted when tested according to OMC.

[0058] If all such pairs are consistent with being inverted according to OMC, then D1 and D2 can be kept in the same equivalence class. In addition, the outputs of the two combinational sub-designs can be compared, using OMC, to determine whether they are consistent with being output inversions of each other.

[0059] Example expressions, for application of OMC-based exceptions, are presented.

[0060] Even if WMC indicates that D1 and D2 are different, there can be exceptions to classifying the sub-designs into different equivalence classes. As with OMC, these exceptions can be of three types: output inversion, input inversion or a combination of output and input inversion. Each of these three exception types is addressed below.

[0061] The output inversion exception can be expressed as follows: D1 cannot be distinguished from the inverse functionality of D2 (i.e., −D2). Example expressions, for testing for the output inversion exception, are presented.

[0062] As discussed above, using known techniques one can determine which pairs of inputs between two sub-designs, as a necessary-but-insufficient condition for equivalency between the two sub-designs, must be inverted with respect to each other.

[0063] Each pair of inputs identified as needing to be inverted, as a necessary-but-insufficient condition, can then be further tested to determine whether the pair is consistent with being inverted when tested according to WMC. If all such pairs are consistent with being inverted according to WMC, then D1 and D2 can be kept in the same equivalence class. In addition, the outputs of the two combinational sub-designs can be compared, using WMC, to determine whether they are consistent with being output inversions of each other.

[0064] Example expressions, for application of WMC-based exceptions, are shown.

[0065] When an MC is applied with D1 having a don't care specification, even if the MC indicates that D1 and D2 are different, there can be exceptions to classifying the sub-designs into different equivalence classes. The two basic types of exceptions are: output inversion and input inversion. The two basic types of exceptions can be combined to produce a total of three exception types. Each of these three exception types is addressed below.

[0066] OMC and WMC expressions to test for output inversion are essentially identical to the expression, presented above, for the general application MC with don't cares.

[0067] A set of k input variables can be determined, as a necessary-but-insufficient condition for equivalency between two sub-designs, as needing to be inverted with respect to each other.

[0068] Given the set of k input variables, an expression to test, with OMC, whether those variables are consistent with being input inverted, is presented. A further expression is presented that combines testing for input inversion with OMC with testing for output inversion with OMC.

[0069] Given the set of k input variables, an expression to test, with WMC, whether those variables are consistent with being input inverted, is presented. A further expression is presented that combines testing for input inversion with WMC with testing for output inversion with WMC.

[0070] Functions, useful for compactly presenting exception expressions, are presented.

[0071] A D1 and D2 may be too large for complete conversion into a BDD representation. However, since the goal of analyzing the BDDs, that represent D1 and D2, is to determine whether D1 and D2 are different, it is not necessary for the entirety of D1 and D2 to be converted into the BDD form. Heuristic approaches can be used to select the appropriate portions of D1 and D2, for conversion into BDDs, such that the ability to distinguish D1 and D2 will be preserved.

[0072] Without loss of generality, it will be assumed that D1 and D2 both accept n inputs. Some of those n inputs are m state bits. One of the sub-designs (for purposes of example D1 is selected) is used for guiding the partial BDD construction. A first compare design, from which D1 can be drawn, can be represented by m such sub-designs, each of which determines the value of a state bit. For those sub-designs in a same EC, their outputs, when present among the n inputs, can be treated as a single input.

[0073] Of the n inputs to D1, k inputs (where k≦n) can be selected to remain as symbolic variables, with the remaining n−k inputs assigned a literal binary value. Selection of the k inputs can be accomplished by any suitable method, including heuristically-guided methods. An example heuristically-guided method for symbolic variable selection is presented.

[0074] Selection of binary values for the remaining n−k inputs can be accomplished by any suitable method, including heuristically-guided methods. An example method is presented. An example pseudo-coded procedure, for performing binary value assignment, is presented.

[0075] A pseudo-coded procedure, called “distinguish_designs,” is presented that accepts a first and second compare designs, each of which is comprised of m sub-designs.

[0076] If distinguish_designs is successful in its application of WMC, each EC, of an EC_all returned value, should contain two sub-designs that constitute a combinational design pair.

[0077] As discussed above, a potential application of distinguish_designs is the sequential equivalence problem. If all combinational design pairs are equivalent, it can be concluded that the first and second compare designs are equivalent.

[0078] Each sub-design passed to distinguish_designs accepts n input variables. Each sub-design represents the next-state function for one-bit of state storage. The first and second compare designs are each assumed to have m state bits.

[0079] The accompanying drawings, that are incorporated in and constitute a part of this specification, illustrate several embodiments of the invention and, together with the description, serve to explain the principles of the invention:

[0080] FIG. 1A depicts a general process for application of minterm counting.

[0081] FIG. 1B depicts a general process for application of minterm counting when don't cares are part of a design specification.

[0082] FIG. 2A depicts an example function, in a form suitable for OMC, as a Karnaugh map.

[0083] FIG. 2B depicts the example function of FIG. 2A, in a form suitable for WMC, also as a Karnaugh map.

[0084] FIGS. 3A-3E depict a suitable set of expressions for the determination of a BDD's WMC.

[0085] FIGS. 4A-4E present example pseudo-code for implementing the expressions of FIGS. 3A-3E.

[0086] FIG. 5A depicts an example BDD to which the expressions of FIGS. 3A-3E have been applied.

[0087] FIG. 5B depicts another example BDD to which the expressions of FIGS. 3A-3E have been applied.

[0088] FIGS. 6A-6D present example expressions of exceptions when using OMC without don't cares.

[0089] FIGS. 7A-7D present example expressions of exceptions when using WMC without don't cares.

[0090] FIGS. 8A, 9A and 10A present example expressions of exceptions when using OMC with don't cares.

[0091] FIGS. 8B, 9B and 10B present example expressions of exceptions when using WMC with don't cares.

[0092] FIGS. 11A-11B present an example pseudo-coded procedure, “ComputeWithCareSet,” for performing a conjunction in a more efficient way.

[0093] FIGS. 12A-12C depict an example of symbolic variable selection.

[0094] FIG. 13 presents a pseudo-code procedure “distinguish_designs.”

[0095] FIG. 14 presents a pseudo-code procedure “BreakEqClassWithOmc.”

[0096] FIG. 15 presents a pseudo-code procedure “FindMatchWithOmc.”

[0097] FIG. 16 presents a pseudo-code procedure “BreakEqClassWithWmc.”

[0098] FIG. 17 presents a pseudo-code procedure “FindMatchWithWmc.”

[0099] FIG. 18 presents a pseudo-code procedure “FindInputInversions.”

[0100] FIGS. 19A-19B present a pseudo-code procedure “BuildBddInEqClass.”

[0101] FIG. 20 presents a computing environment (or data processing system) within which the combinational design distinguishing architecture of the present invention can be executed.

[0102] FIG. 21 shows a simplified representation of an exemplary digital ASIC design flow.

[0103] Reference will now be made in detail to preferred embodiments of the invention, examples of which are illustrated in the accompanying drawings. Wherever possible, the same reference numbers will be used throughout the drawings to refer to the same or like parts.

[0104] Please refer to the Glossary of Selected Terms, included at the end of the Detailed Description, for the definition of selected terms used below.

• [0105] 1. Application of Minterm Counting
  • [0106] 1.1. Without Don't Cares
  • [0107] 1.2. With Don't Cares
    • [0108] 1.2.1. Conjoining BDDs
• [0109] 2. Ordinary Minterm Counting (OMC)
  • [0110] 2.1. For BDDs
• [0111] 3. Weighted Minterm Counting (WMC)
  • [0112] 3.1. Example VLWFs
  • [0113] 3.2. Example Sub−Design
  • [0114] 3.3. Application To BDDs
    • [0115] 3.3.1. Example Expressions
    • [0116] 3.3.2. Example Pseudo-Code
    • [0117] 3.3.3. Example BDDs
• [0118] 4. Exceptions to OMC, Without Don't Cares
  • [0119] 4.1. Output Inversion
  • [0120] 4.2. Input Inversion
  • [0121] 4.3. Output Inversion and Input Inversion
• [0122] 5. Exceptions to WMC, Without Don't Cares
  • [0123] 5.1. Output Inversion
  • [0124] 5.2. Input Inversion
  • [0125] 5.3. Output Inversion and Input Inversion
• [0126] 6. Exceptions to MC, With Don't Cares
  • [0127] 6.1. Output Inversion
  • [0128] 6.2. Input Inversion
  • [0129] 6.3. Output Inversion and Input Inversion
• [0130] 7. Functions for Defining Exceptions
• [0131] 8. Partial BDD Production
  • [0132] 8.1. Symbolic Variable Selection
    • [0133] 8.1.1. Example
  • [0134] 8.2. Binary Value Selection
    • [0135] 8.2.1. Example Pseudo-Code
• [0136] 9. Example Application of WMC
  • [0137] 9.1. Distinguish_Designs
  • [0138] 9.2. BreakEqClassWithOmc
  • [0139] 9.3. FindMatchWithOmc
  • [0140] 9.4. BuildBddInEqClass
  • [0141] 9.5. BreakEqClassWithWmc
  • [0142] 9.6. FindMatchWithWmc
  • [0143] 9.7. FindInputInversions
• [0144] 10. Hardware Environment
• [0145] 11. Glossary of Selected Terms

[0146] Below described are processes for application of minterm counting, both ordinary minterm counting (OMC) and weighted minterm counting (WMC), as combinational design discriminators (CDDs). Regardless of whether the minterm counting is OMC or WMC, a general process for application of minterm counting, when don't cares are not utilized, is depicted in FIG. 1A. FIG. 1B depicts a general process for application of minterm counting when don't cares are part of a design specification.

[0147] The processes of FIGS. 1A and 1B each operate by applying minterm counting to a pair of combinational sub-designs D1 and D2. Without loss of generality, each such sub-design can be regarded as comprised of n input variables and one output variable.

1.1. Without Don't Cares

[0148] Please refer to FIG. 1A in conjunction with this section. D1 and D2 can each be converted into a data representation (e.g., the BDD data representation) suitable for application of minterm counting. Step 102. Suitable data representations for D1 and D2 can be referred to as, respectively, D1_DREP and D2_DREP. Regardless of the type of data structure used, it can be viewed as being representative of a set of minterms, where the set of minterms defines a functionality of the sub-design.

[0149] Prior to conversion of D1 and D2 into D1_DREP and D2_DREP, the input variables of D1 and D2 can be reduced by assigning binary values to some of them. Step 101. Such selective conversion of input variables to fixed binary values involves two main steps, that can be performed separately or in an interdepedent fashion: selection of the variables to remain symbolic and selection of the binary value to assign to each non-symbolic variable.

[0150] D1_DREP and D2_DREP can each be assigned a minterm count, respectively MC_D1_DREP and MC_D2_DREP, that is equivalent to assigning an appropriate weighting to the set of minterms each such data structure represents. Step 103.

[0151] If MC_D1_DREP and MC_D²_DREP are within a certain tolerance of each other, then D1 and D2 cannot be distinguished by the particular type of minterm counting applied (the “yes” branch of decision point 104 is followed).

[0152] If MC_D1_DREP and MC_D2_DREP are not within a certain tolerance of each other, then it is known that D1 and D2 represent different functionalities.

[0153] Even if D1 and D2, in a strict sense, represent different functionalities, their functionalities may still be sufficiently related such that classification of D1 and D2 as differing functionalities is inappropriate. Each such test of relatedness, between a pair of sub-designs D1 and D2, is referred to herein as an “exception” since it can be an exception to the classification of D1 and D2 as differing functionalities. The evaluation of exceptions is represented in FIG. 1A by step 105. Detailed discussion, of the types of exceptions that can be evaluated in step 105, are presented below in the following sections: 4 (“Exceptions to OMC, Without Don't Cares”) and 5 (“Exceptions to WMC, Without Don't Cares”).

1.2. With Don't Cares

[0154] Please refer to FIG. 1B in conjunction with this section.

[0155] A D1 can have an input combination for which the designer has specified a “don't care” as to what output is produced. Such an input combination can match any corresponding value produced by D2. A D1 can contain one or more “don't care” combinations. As an example of where a “don't care” specification can be useful, D1 can be a higher level design specification that can include don't cares, while D2 can be a more hardware-specific implementation.

[0156] In order to express one or more “don't care” combinations, a design D1 can be expressed by any two of the following types of design specifications: D1_dc, D1_min and D1_max. D1_dc is defined to produce a true value for each set of input combinations, inputs_x, for which a designer has specified a “don't care.” For each set of input combinations to D1, D1_min and D1_max are defined to produce the same value, except for any set of inputs inputS_x for which D1_dc produces a true value. For each inputs_x where D1_dc produces a true value, D1_min is defined to produce a zero and D1_max is defined to produce a one.

[0157] In FIG. 1B, suitable minterm counting data representations of D1_dc, D1_min and D1_max, referred to respectively as D1_dc,DREP, D1_min,DREP and D1_max,DREP, are determined. Step 111. D1_dc,DREP, D1_min,DREP and D1_max,DREP can be determined provided the user has input at least two of D1_dc, D1_min and D1_max. An example suitable data representation, for minterm counting, is a BDD. Regardless of the type of data structure used, it can be viewed as being representative of a set of minterms that can determine a functionality of D1_dc, D1_min or D1_max.

[0158] FIG. 1B also depicts a step for determination of suitable minterm counting data representation for D2, referred to as D2_DREP. Step 112.

[0159] Prior to the production of D1_dc,DREP, D1_min,DREP, D1_max,DREP and D2_DREP, the support of the sub-designs from each is determined (see Glossary for definition of support of sub-design). Each of these supports can be reduced by assigning binary values to some of the variables that would be included in the support. Step 110. Such selective conversion of input variables to fixed binary values involves two main steps, that can be performed separately or in an interdepedent fashion: selection of the variables to remain symbolic and selection of the binary value to assign to each non-symbolic variable.

[0160] D1_min,DREP, D1_max,DREP and D2_DREP can each be assigned a minterm count, respectively MC_D1_min,DREP. MC_D1_max,DREP and MC_D2_DREP. Step 114. Determining a minterm count, for a data representation suitable for minterm counting, is equivalent to assigning an appropriate weighting to the set of minterms each such data structure represents.

[0161] A minterm count MC_D2_min,DREP can also be determined from D1_dc,DREP and D2_DREP. Step 113.

[0162] If the following relations are satisfied, then D1 and D2 cannot be distinguished by the particular type of minterm counting applied: $\mathrm{if}\left(\begin{array}{c}\left[\mathrm{mc}\left(D{1}_{\min }\right)=\mathrm{mc}\left(D2\bigwedge -D{1}_{\mathrm{dc}}\right)\right]\\ \mathrm{AND}\\ \left[\mathrm{mc}\left(D{1}_{\min }\right)\le \mathrm{mc}\left(D2\right)\le \mathrm{mc}\left(D{1}_{\max }\right)\right]\end{array}\right)$

• • [0163] then keep D1 and D2 in same EC

[0164] The above relation (which corresponds, in FIG. 1B, to decision point 115) depicts two expressions, one on either side of an AND operator. The expression before the AND compares the MC of D1_min to an expression (i.e., D2−D1_dc) that determines the equivalent of D2_min. Alternatively, the expression before the AND can compare the MC of D1_max to an expression (i.e., D2D1_dc) that determines the equivalent of D2_max.

[0165] If the expressions before and after the AND are determined to be true, then the relationship between D2 and D1 is consistent with D2 being within the range of functions encompassed by D1.

[0166] Even if D1 and D2, in a strict sense, represent different functionalities, it may still be the case that their functionalities are sufficiently related such that classification of D1 and D2 as differing functionalities is inappropriate. Each such test of relatedness, between a D1 and D2, is referred to herein as an “exception” since it can be an exception to the classification of D1 and D2 as differing functionalities. The evaluation of exceptions is represented in FIG. 1B by step 116. Detailed discussion, of the types of exceptions that can be evaluated in step 116, are presented below the following section: 6 (“Exceptions to MC, With Don't Cares”).

[0167] 1.2.1. Conjoining BDDs

[0168] If D2 and −D1_dc are expressed as BDDs, taking their conjunction, to determine D2_min (as called-for above), can be computationally expensive.

[0169] FIG. 11A-11B present an example pseudo-coded procedure, “ComputeWithCareSet,” for performing the conjunction in a more efficient way. FIG. 11A is a version of ComputeWithCareSet for BDDs with potentially redundant nodes, while FIG. 11B is designed to operate on “reduced” BDDs (i.e., BDDs where redundant nodes are removed).

[0170] ComputeWithCareSet of FIG. 11A operates as follows (ComputeWithCareSet of FIG. 11B operates in a similar fashion). ComputeWithCareSet is initially invoked (line 4) with the “L” parameter set to zero, such that the variable closest to the root node, in BDDs F and C, is the starting node.

[0171] ComputeWithCareSet begins by addressing the following simple cases first. If the BDD for F or C represents a constant zero (line 7), the WMC of F and C is simply zero (line 8). If F represents a constant “1” (line 9) then the WMC of F and C is simply the WMC of C (line 10). Conversely, if C represents a constant “1” (line 11), then the WMC of F and C is simply the WMC of F (line 12).

[0172] If F and C do not fit one of the above simple cases, then ComputeWithCareSet is recursively invoked on the “then” (line 14) and “else” (lines 16-20) branches of the current variable as indicated by “L.” The results of the recursive invocations are combined according to the WMC formula of FIG. 3A (line 22).

[0173] A known form of minterm counting is referred to herein as “ordinary” minterm counting or OMC. Application of OMC, to a suitable data representation of a sub-design, is as follows. OMC determines an integer that represents the sub-design. Regardless of how the integer is determined, it can be viewed as being equivalent to assigning a value of one to each minterm of the sub-design and computing the sum of all such assigned values.

[0174] While OMC is useful as a CDD, and can be determined rapidly, it can readily be appreciated there are many instances in which two sub-designs are functionally different but are still assigned the same integer value by OMC.

2.1. For BDDs

[0175] When the data representation is a BDD, and when the size of the support, of the sub-design represented by the BDD, is n, OMC can be accomplished as follows. Each constant “1” leaf node of the BDD can be assigned a weight of 2ⁿ. Each constant “1” leaf node, after passing through an inverted “else” edge, can be assigned a weight of zero. The weight of a parent BDD node (omc_parent) can be determined from the weight of its “then” and “else” edges (represented by wt_then and wt_else) by the following expression: $\mathrm{omc\_parent}=\frac{\left(\mathrm{wt\_then}+\mathrm{wt\_else}\right)}{2}$

[0176] Rather than assigning the same weight (e.g., a weight of one) to each minterm, weighted minterm counting (WMC) assigns a weight that can vary. Such weight can vary, for example, by being a function of the particular literals of which a minterm is comprised.

[0177] For example, a weight can be assigned to each variable, comprising a minterm, that is a function of the particular variable and whether the variable is required to be in true or complemented form. The function, that assigns a weight to each variable of a minterm, can be referred to as a variable-level weighting function (VLWF). Example VLWFs are discussed below.

[0178] The weights assigned to each variable of a minterm can be combined, according to an appropriate function (referred to as a minterm-level weighting function or MLWF), to arrive at a total weight for each minterm. An example MLWF is finding the product of the weights assigned to each variable of a minterm.

[0179] The minterm weights for a particular combinational sub-design can be combined, according to an appropriate function (referred to as a design-level weighting function or DLWF), to arrive at a total weight for the sub-design. An example DLWF is to take the sum of the weights assigned to each minterm.

3.1. Example VLWFs

[0180] For a combinational design that is a function of n variables, for each minterm m, each of its variables v can be identified by a value i, where 0≦i≦(n−1). The type of literal l_i representing each variable v_i (i.e., whether the literal that represents the variable in its true or complemented form) can be represented by the following binary vector:
b_n−1, b_n−2, . . . b₁, b₀

[0181] Where b_i=0 means the corresponding variable v_i is represented in its complemented form by −l_i, and b_i=1 means the corresponding variable v_i is represented in its true form by l_i.

[0182] A VLWF for assigning a variable weight v_wt_i to a variable v_i of a minterm m, can be represented as follows:
v_wt_i=VLWF(i, b₁), for 0≦i≦(n−1)

[0183] The class of functions for VLWF can be further constrained to those that satisfy any combination of the following three constraints:
v_wt_i=1 when b_i=0  (1)
v_wt_i≠0 and v_wt_i≠−1  (2)
each v_wt_i is given a unique value when b_i=1  (3)

[0184] Constraints (1) and (2) can be particularly useful when the MLWF is multiplication. When a multiplication MLWF is used, a problem can be the weight for a minterm m, expressed as wt_m, becoming too large for convenient representation in a computing system. This can be addressed by further limiting each variable weight v_wt_i to a value that is close to one. Each weight v_wt_i can differ from its next consecutive weight v_wt_i+1 by a fixed amount (e.g., 0.01). Therefore, an example sequence of weights can be as follows:
1.00, 1.01, 1.02,

[0185] Multiplication of floating point values can produce rounding errors. Such errors can compound when producing an overall weight for a D1 and an overall weight for a D2. The errors can cause the weight for the D1 to appear different from the weight for the D2 when, in fact, the difference is just due to rounding errors. A technique for addressing this problem is to require that the weights, for D1 and D2, differ by at least a predetermined tolerance before it is concluded that the two combinational designs are functionally different. An example tolerance is 10⁻²⁰.

3.2. Example Sub-Design

[0186] An example sub-design f to which WMC can be applied is as follows:
f=v₀+v₁ v₂

[0187] The minterms of f can be represented, in a form suitable for OMC, by the Karnaugh map of FIG. 2A.

[0188] An example VLWF for f, VLWF_ex1, can be as follows:
v_wt_i=VLWF_ex1(i, b_i), for 0≦i≦2, where
v_wt_i=1 when b_i=0  (1)
v_wt₀=2 when b₀=1 and i=0  (2)
v_wt₁=3 when b₁=1 and i=1  (3)
v_wt₂=4 when b₂=1 and i=2  (4)

[0189] When the above-defined VLWF_ex1 is combined with an example MLWF, MLWF_ex1, of multiplication and an example DLWF, DLWF_ex1, of addition, the resulting weighted Karnaugh map is shown in FIG. 2B.

3.3. Application To BDDs

[0190] Where a sub-design is expressed as a BDD, and where the VLWF, MLWF and DLWF to be applied are known, a suitable set of expressions, for the efficient determination of the BDD's WMC, can be determined.

[0191] In this section, a set of expressions is presented for the case where the DLWF is summation, the MLWF is multiplication and the VLWF satisfies constraints (1) and (2). The variables of the sub-design are v₀ to v_n−1, where v₀ is represented by the root node and v_n−1 is represented by the BDD nodes closest to the constant “1” nodes.

[0192] 3.3.1. Example Expressions

[0193] A suitable set of expressions, for the determination of a BDD's WMC, is shown in FIGS. 3A-3E.

[0194] FIG. 3A defines an expression to determine a value for wmc(nd_p), where nd_p is a node p of a BDD and wmc(nd_p) is the WMC of that node. wmc(nd_p) can be applied to any node of a BDD, except for the constant “1” nodes. wmc_t(nd_p) finds the WMC of the “then” branch of nd_p, while wmc_e(nd_p) find the WMC of the “else” branch of nd_p. nd2v(nd_p) returns the variable v_i represented by node nd_p. v2wt(v_i) returns the weight assigned to variable v_i.

[0195] FIG. 3B defines an expression to determine wmc_t(nd_p). nd_then is the “then” node pointed-to by nd_p. p₂con_adj_fac(i) and p2chi_adj_fac(i, j) are adjustment factors defined in, respectively, FIGS. 3D and 3E. As can be seen in FIG. 3B, the value determined by wmc_t(nd_p) depends upon whether nd_then is a constant “1” node. If it is, then its WMC is 2ⁿ scaled by an adjustment factor. As can be seen in FIG. 3D, if nd_p is already at the maximum BDD depth of n−1 (i.e., the i value passed to p2con_adj_fac is n−1), the adjustment factor is simply “1.” However, if nd_p is not at the maximum BDD depth, p2con_adj_fac scales 2ⁿ appropriately.

[0196] If nd_then is not a constant “1,” then its WMC is that of wmc recursively applied to nd_then, scaled by an adjustment factor. As can be seen in FIG. 3E, the adjustment factor depends upon the difference between the level of nd_p and nd_then. If nd_then is a direct parent of nd_p (i.e., the difference between their BDD levels is one), a scaling factor is not needed and so p2chi_adj_fac returns one. However, if nd_p and nd_then are not directly consecutive BDD levels, p2chi_adj_fac scales wmc(nd_then) appropriately.

[0197] FIG. 3C defines an expression to determine wmc e(nd_p). nd_else is the “else” node pointed-to by nd_p. FIG. 3C is more complex than FIG. 3B because the “else” edge of a BDD can be inverted while, according to typical BDD notation, the “then” branch cannot be inverted. The combination of whether nd_else is a constant “1,” with whether the edge between nd_p and nd_else is inverted, admits of four possibilities. For the two possibilities where the edge between nd_p and nd_else is not inverted, operation of wmc_e(nd_p) is the same as wmc_t(nd_p), except that nd_else is substituted for nd_then.

[0198] For the two possibilities where the edge between nd_p and nd_else is inverted, wmc_e(nd_p) works as follows. If nd_else is a constant “1” node, then wmc_e(nd_p) is zero. If nd_else is not a constant “1” node, then wmc_e(nd_p) is determined as follows. The WMC for nd_else, where nd_else is a constant “1” node connected to nd_p through a non-inverted edge, is determined. From this is subtracted the following: the WMC for nd_else, where nd_else is not a constant “1” node and connected to nd_p through a non-inverted edge.

[0199] 3.3.2. Example Pseudo-Code

[0200] FIGS. 4A-4E present example pseudo-code for implementing the expressions of FIGS. 3A-3E. The pseudo-code of FIG. 4A corresponds to the expression of FIG. 3A. The pseudo-code of FIG. 4B corresponds to the expression of FIG. 3B. The pseudo-code of FIG. 4C corresponds to the expression of FIG. 3C. The pseudo-code of FIG. 4D corresponds to the expression of FIG. 3D. The pseudo-code of FIG. 4E corresponds to the expression of FIG. 3E.

[0201] 3.3.3. Example BDDs

[0202] FIG. 5A depicts an example BDD to which the expressions of FIG. 3A-3E have been applied along with VLWF_ex1, MLWF_ex1 and DLWF_ex1. FIG. 5B depicts another example BDD to which the expressions of FIG. 3A-3E have been applied. The BDD of FIG. 5B differs from the BDD of FIG. 5A in that the redundant nodes of FIG. 5A have been eliminated. Non-redundant BDDs can provide a more efficient representation of a function. The BDDs of FIGS. 5A and 5B represent the same function, shown in Karnaugh map form, as FIG. 2B.

[0203] Even if OMC indicates D1 and D2 are different, there can be exceptions to classifying the designs into different equivalence classes. The two basic types of exceptions are: output inversion and input inversion. These two basic types of exceptions can be combined to produce a total of three exception types. Each of these exception types is addressed below.

[0204] Some of the functions, used for defining the below exceptions, are defined in section 7 (“Functions For Defining Exceptions”).

4.1. Output Inversion

[0205] The output inversion exception can be expressed as follows: D1 is consistent with being the same as D2, except that the output of D2 is inverted with respect to the output of D1.

[0206] The output inversion exception can be tested-for as follows. Determine a design that determines the inverse functionality of D2 (i.e., −D2). Compare omc(D1) to omc(−D2) (see FIG. 6A). Alternatively, omc(−D2) is equivalent to the expression shown in FIG. 6B, which can be more efficient to determine.

4.2. Input Inversion

[0207] Using known techniques, one can determine the following: whether, as a necessary-but-insufficient condition for equivalency between D1 and D2, a pair of corresponding inputs, one input applied to D1 and the other input applied to D2, must be inverted with respect to each other. Such detection of necessary-but-insufficient input inversion can be accomplished, for example, as described in the J. Mohnke and S. Malik paper (see Glossary for citation to paper). However, the J. Mohnke and S. Malik paper discusses building a BDD for an entire circuit design, which can be intractable when the circuit design is too large. This shortcoming can be addressed by applying the methods of the J. Mohnke and S. Malik paper to a pair of combinational sub-designs where only some of the inputs are kept symbolic and the rest are assigned binary values.

[0208] Each pair of inputs identified as needing to be inverted, as a necessary-but-insufficient condition, can then be further tested to determine whether the pair is consistent with being inverted when tested according to OMC. If all such pairs are consistent with being inverted according to OMC, then D1 and D2 can be kept in the same equivalence class.

[0209] An example expression, for application of OMC, is shown in FIG. 6C. The expression of FIG. 6C assumes that D1 and D2 share the same set of variables v₀ to v_n−1, where k of the variables, referred to as v₀ to V_k−1, have been identified, as a necessary-but-insufficient condition, as needing to be input inverted between the two combinational sub-designs. For each of these k variables, FIG. 6C contains one expression within square brackets that tests whether a pair of inputs is, in fact, consistent with being input inverted according to OMC.

4.3. Output Inversion and Input Inversion

[0210] As discussed above, each pair of inputs identified as needing to be inverted, as a necessary-but-insufficient condition, can be further tested to determine whether the pair is consistent with being inverted when tested according to OMC. In addition, the outputs of the two combinational sub-designs can be compared, using OMC, to determine whether they are consistent with being output inversions of each other.

[0211] An example expression, for application of OMC, is shown in FIG. 6D.

[0212] Even if WMC indicates that D1 and D2 are different, there can be exceptions to classifying the sub-designs into different equivalence classes. The two basic types of exceptions are: output inversion and input inversion. The two basic types of exceptions can be combined to produce a total of three exception types. Each of these three exception types is addressed below.

[0213] Some of the functions, used for defining the below exceptions, are defined in below section 7 (“Functions For Defining Exceptions”).

[0214] In considering the below-presented exceptions, each “equality” tested-for, between a pair of WMCs, can also be satisfied by the operands being within a tolerance of each other.

5.1. Output Inversion

[0215] The output inversion exception can be expressed as follows: D1 cannot be distinguished from the inverse functionality of D2 (i.e., −D2). See FIG. 7A where wmc(D1) is compared to wmc(−D2).

[0216] Alternatively, wmc(−D2) is equivalent to the expression shown in FIG. 7B, which can be more efficient to determine. FIG. 7B is comprised of two expressions. The second expression determines WMC for a function of n variables that represents a constant “1.” The second expression of FIG. 7B iterates over each variable of D2. For each variable of D2, its adjusted weight is determined (one is added to the weight and the sum is divided by two). The product of the adjusted weights is determined, which is multiplied by an adjustment factor (the OMC for a function of n variables that represents a constant “1” )

5.2. Input Inversion

[0217] As discussed above in section 4.2 (“Input Inversion” with OMC), using known techniques one can determine which pairs of inputs between two sub-designs, as a necessary-but-insufficient condition for equivalency between the two sub-designs, must be inverted with respect to each other.

[0218] Each pair of inputs identified as needing to be inverted, as a necessary-but-insufficient condition, can then be further tested to determine whether the pair is consistent with being inverted when tested according to WMC. If all such pairs are consistent with being inverted according to WMC, then D1 and D2 can be kept in the same equivalence class.

[0219] An example expression, for application of WMC, is shown in FIG. 7C. The expression of FIG. 7C assumes D1 and D2 share the same set of input variables v₀ to v_n−1 and that k of the variables, referred to as v₀ to v_k−1, have been identified, as a necessary-but-insufficient condition, as needing to be input inverted between the two combinational sub-designs. For each of these k variables, FIG. 7C contains one expression within square brackets that tests whether a pair of inputs is, in fact, consistent with being input inverted according to WMC.

5.3. Output Inversion and Input Inversion

[0220] As discussed above in section 5.2, each pair of inputs identified as needing to be inverted, as a necessary-but-insufficient condition, can be further tested to determine whether the pair is consistent with being inverted when tested according to WMC. In addition, the outputs of the two combinational sub-designs can be compared, using WMC, to determine whether they are consistent with being output inversions of each other.

[0221] An example expression, for application of WMC, is shown in FIG. 7D.

[0222] When an MC is applied with D1 having a don't care specification, even if the MC indicates that D1 and D2 are different, there can be exceptions to classifying the sub-designs into different equivalence classes. The two basic types of exceptions are: output inversion and input inversion. The two basic types of exceptions can be combined to produce a total of three exception types. Each of these three exception types is addressed below.

[0223] Some of the functions, used for defining the below exceptions, are defined in below section 7 (“Functions For Defining Exceptions”).

[0224] In considering the below-presented exceptions, each “equality” tested-for, between a pair of WMCs, can also be satisfied by the operands being within a tolerance of each other.

6.1. Output Inversion

[0225] An expression to test for output inversion with OMC is essentially identical to an expression to test for output inversion with WMC. The only difference is the OMC test (see example of FIG. 8A) being expressed in terms of an OMC function and the WMC test (see example of FIG. 8B) being expressed in terms of a WMC function.

[0226] Further, the OMC and WMC expressions to test for output inversion are essentially identical to the expression, presented above in section 1.2 (“With Don't Cares”) in connection with step 115 of FIG. 1B, for applying MC with don't cares. The only difference is that each instance of D2 is replaced with −D2.

6.2. Input Inversion

[0227] As discussed above, a set of k input variables can be determined, as a necessary-but-insufficient condition for equivalency between two sub-designs, as needing to be inverted with respect to each other.

[0228] Given the set of k input variables, an expression to test, with OMC, whether those variables are consistent with being input inverted, is presented in FIG. 9A.

[0229] Given the set of k input variables, an expression to test, with WMC, whether those variables are consistent with being input inverted, is presented in FIG. 9B.

[0230] As can be seen, FIG. 9A is similar to FIG. 9B. The two differences are as follows. FIG. 9A is expressed in terms of an OMC function and FIG. 9B is expressed in terms of a WMC function. FIG. 9B determines a phase-shifted WMC, of a conjunction, while FIG. 9A determines a non-phase-shifted OMC of a conjunction.

6.3. Output Inversion and Input Inversion

[0231] FIG. 10A is the same as FIG. 9A, except each instance of D2 is inverted. Likewise, FIG. 10B is the same as FIG. 9B, except each instance of D2 is inverted.

[0232] cofac(D, v_st): Finds the co-factor of a design D. The co-factor found is the design defined by design D when its variable v is in state v_st.

[0233] sub(D, sub_v₀, sub _v₁, . . . sub _v_k−1): The operation of sub, also referred to herein as a “substitution” operation, can be defined as follows. If design D is expressed as a Boolean formula, for each occurrence of a variable sub _v_x in D, where 0≦x≦k−1, sub_v_x is replaced with −sub_v_x and −sub_v_x is replaced with sub_v_x.

[0234] wmc_ps(D, ps_v₀, ps_v₁, . . . ps_v_k−1): Finds the WMC of a design D, but with variables ps_v₀, ps_v₁, . . . ps_v_k−1 phase shifted. Such phase shifting can be defined as follows. Design D can be expressed as a collection of minterms. For each minterm, its weight, for purposes of determining WMC, can be found by multiplying the value of each literal, composing the minterm, by the weight of the variable represented by the literal. Literals representing the “true” form of a variable become the value one multiplied by the weight of the variable represented by the literal. If the literal represents a variable that is an element of ps_v₀, ps_v₁, . . . ps_v_k−1, then the phase of the value one, used for multiplying with the weight of the variable, is shifted 180 degrees to be a zero. Literals representing the “negated” form of a variable become the value zero multiplied by the weight of the variable represented by the literal. If the literal represents a variable that is an element of ps_v₀, ps_v₁, . . . ps_v_k−1, then the phase of the value zero, used for multiplying with the weight of the variable, is shifted 180 degrees to be a one.

[0235] A D1 and D2 may be too large for complete conversion into a BDD representation. However, since the goal of analyzing the BDDs, that represent D1 and D2, is to determine whether D1 and D2 are different, it is not necessary for the entirety of D1 and D2 to be converted into the BDD form. Heuristic approaches can be used to select the appropriate portions of D1 and D2, for conversion into BDDs, such that the ability to distinguish D1 and D2 will be preserved.

[0236] Without loss of generality, it will be assumed that D1 and D2 both accept n inputs. Some of those n inputs are m state bits. One of the sub-designs (for purposes of example D1 is selected) is used for guiding the partial BDD construction. A first compare design, from which D1 can be drawn, can be represented by m such sub-designs, each of which determines the value of a state bit. For those sub-designs in a same EC, their outputs, when present among the n inputs, can be treated as a single input.

[0237] Of the n inputs to D1, k inputs (where k≦n) can be selected to remain as symbolic variables, with the remaining n−k inputs assigned a literal binary value. Selection of the k inputs can be accomplished by any suitable method, including heuristically-guided methods. Selection of binary values for the remaining n−k inputs can be accomplished by any suitable method, including heuristically-guided methods. Symbolic variables can be selected in conjunction with selection of binary values, or the two can be accomplished by separate processes.

8.1. Symbolic Variable Selection

[0238] An example heuristically-guided method for symbolic variable selection is as follows.

[0239] For each of the n inputs, i₀ . . . i_n−1, its transitive fanout, with respect to the complete first compare design, can be determined such that the number of state bits, driven by that input, can be determined. The number of state bits, driven by each input, can be expressed as nsb₀ . . . nsb_n−1, where each nsb_x (0≦x≦n−1) corresponds to an i_x (0≦x≦n−1).

[0240] Inputs i₀ . . . i_n−1 can be put in ascending order according to their corresponding nsb₀ . . . nsb_n−1 values. The k inputs, to be selected for keeping in symbolic form, can be selected from the ordered list so as to insure that an even distribution, of the nsb₀ . . . nsb_n−1 values, is selected. A “gap value” G can be determined as follows: G=n/k. Starting from one end of the ordered list of inputs, every Gth input can be selected to remain symbolic.

[0241] 8.1.1. Example

[0242] An example of symbolic variable selection is depicted in FIGS. 12A-12C.

[0243] FIG. 12A depicts an example sequential circuit comprised of three state bits: s₀, s₁, s₂. Each of these state bits is driven by its own circular symbol in FIGS. 12A-12C. Each circular symbol has a single output, representing the current state of its one state bit. Each circular symbol can have multiple inputs since it also encompasses the combinational sub-design that determines the next state for that one state bit.

[0244] The example sequential circuit of FIG. 12A also includes three primary inputs: pi₀, pi₁, pi₂. In FIG. 12B, the circuit of FIG. 12A is rearranged into a bipartite graph where all inputs, that can effect the next state, are on the left side and each state bit, along with its combinational next state function, is on the right side.

[0245] In FIG. 12C, the inputs to each combinational sub-design are renamed as follows. It is assumed that the sub-designs for s₁ and s₂ are currently in the same EC, as indicated by dashed outline 1230. Primary inputs pi₀, pi₁, pi₂ are re-named: i₀, i₁, i₂. Present state input s₀ is re-named i₃ while present state inputs s₁, s₂ are re-named i₄. The corresponding values of nsb₀, nsb₁, nsb₂, nsb₃, nsb₄, for i-₀, i₁, i₂, i₃, i₄, are: 1, 2, 3, 1, 2. In ascending order, the inputs, and the number of state bits driven by each, are i₀, i₃, i₁, i₄, i₂ and 1, 1, 2, 2, 3. If k=2, G=n/k= 5/2=2.5 If G is rounded down to 2, then the primary inputs selected to remain symbolic are: i₀, i₁. If G is rounded up to 3, then the primary inputs selected to remain symbolic are: i₀, i₄.

8.2. Binary Value Selection

[0246] The remaining n−k inputs can each be assigned a literal binary value by any appropriate method. An example method is as follows.

[0247] The n−k inputs can be assigned non-controlling values, depending upon the types of gates each controls. For example, for a 2-input AND gate, the logic value “1” is non-controlling since it permits the other logical value, at the other input to the AND gate, to have an observable effect on the AND gate's output. Similarly, for a 2-input OR gate, the logic value “0” is non-controlling.

[0248] When assigning non-controlling values, any appropriate method can be used to determine the order in which non-controlling values are assigned and the “neighborhood” of gates, associated with each of the n−k inputs, used for determining whether a value is non-controlling.

[0249] A strategy, that can be applied when assigning non-controlling values, is to select values that will allow the k symbolic inputs to each have, as much as possible, an observable effect on the m state bits. An example implementation of this strategy is as follows.

[0250] For each sub-design, a depth-first search, starting at the sub-design's state-bit, is performed in order to create a BDD representation of the sub-design. During the course of each depth-first search, when each of the n−k inputs is encountered, it is given a non-controlling value based upon the type of gate that was last traversed.

[0251] 8.2.1. Example Pseudo-Code

[0252] An example pseudo-coded procedure, for performing such binary value assignment, is discussed below in section 9.4 entitled “BuildBddInEqClass.” The pseudo-code itself is presented in FIGS. 19A-19B.

9.1. Distinguish_Designs

[0253] FIG. 13 presents a pseudo-code procedure “distinguish_designs” that accepts a first and second compare designs, each of which is comprised of m sub-designs. The sub-designs of the first compare design can be represented as follows:
D1₀(i₀, i₁, . . . i_n−1), D1(i₀, i₁, . . . i_n−1), . . . D1_m−1(i₀, i₁, . . . i_n−1)

[0254] The sub-designs of the second compare design can be represented as follows:
D2₀(i₀, i₁, . . . i_n−1), D2(i₀, i₁, . . . i_n−1), . . . D2_m−1(i₀, i₁, . . . i_n−1)

[0255] If distinguish_designs is successful in its application of WMC, each EC, of the EC_all returned, should contain two sub-designs that constitute a combinational design pair.

[0256] As discussed above, a potential application of distinguish_designs is the sequential equivalence problem. If all combinational design pairs are equivalent, it can be concluded that the first and second compare designs are equivalent.

[0257] Each sub-design passed to distinguish_designs (see FIG. 13, line 1) accepts n input variables. Each sub-design represents the next-state function for one-bit of state storage. Therefore, the first and second compare designs are each assumed to have m state bits.

[0258] Initially, distinguish_designs puts all sub-designs, of the first and second compare designs, into a single EC called EC_one. Lines 3-5. Initially, EC_one becomes the first member of EC_all. Lines 6-7.

[0259] The procedure “BreakEqClassWithOmc” is called (line 13) to divide EC_one into the largest numbers of ECs possible, given the functional distinguishing capability of OMC. Next, “BreakEqClassWithWmc” is used (line 21), on each member of EC_all, in order to apply the additional functional distinguishing capability of WMC.

9.2. BreakEqClassWithOmc

[0260] FIG. 14 presents a pseudo-code procedure “BreakEqClassWithOmc.” BreakEqClassWithOmc begins by testing whether EC_one is already composed of just two sub-designs. Line 6.

[0261] If not, a BDD is generated for each sub-design of EC_one. Line 17. However, depending on the size of the first and second compare designs, there may be too many variables for production of the BDD. In this case, a procedure, such as the “ChooseSymbolicVariables” procedure invoked at line 11, can be used to select a subset of the variables of EC_one (referred to in FIG. 14 as V_s) to remain symbolic. EC_all is also passed to ChooseSymbolicVariables to identify which groups of state bits are currently to be treated as a single input for each sub-design of EC_one. While a pseudo-coded procedure for ChooseSymbolicVariables is not presented, a functional specification of ChooseSymbolicVariables is presented in above section 8.1 (“Symbolic Variable Selection”).

[0262] A BDD for each sub-design of EC_one can be produced by calling BuildBddInEqClass. Line 17. BuildBddInEqClass can operate by performing a depth-first search of each sub-design. During such depth-first search, variables that are to be non-symbolic can have binary values assigned.

[0263] A procedure “FindMatchWithOmc” can be called to determine whether EC_one can be subdivided, into smaller ECs, with OMC. Line 21. The subdivisions are stored in “NewEC.” If EC_one cannot be further subdivided, FindMatchWithOmc returns an unchanged EC_all. If EC_one can be further divided, EC_all is updated as follows: EC_one is removed from EC_all and the ECs of NewEC are added to EC_all. Line 28.

[0264] Then, for each EC of NewEC (referred to in the pseudo-code as EC_cur), BreakEqClassWithOmc is called recursively (line 36) to determine whether EC_cur can be further subdivided with OMC. In effect, BreakEqClassWithOmc may be able to find further subdivisions of EC_one, once EC_one has already been partially subdivided with OMC, because the partial subdivision has introduced new variables that can change how FindMatchWithOmc operates.

9.3. FindMatchWithOmc

[0265] FIG. 15 presents a pseudo-code procedure “FindMatchWithOmc.” FindMatchWithOmc is passed an EC EC_one. Line 1. For each sub-design of EC_one (line 7) the parameter “BDD” of FindMatchWithOmc contains a corresponding BDD.

[0266] The new subdivisions of EC_one, that FindMatchWithOmc is able to find, are stored in NewEC which is initialized to an empty set. For each sub-design D_i of EC_one a “for” loop (lines 7-39) can cause the following to be done.

[0267] The OMC of D_i, called omc_D_i, can be found with “find_OMC.” Line 11.

[0268] A set called matches_D_i can be found. Line 14. matches_D_i is the set of ECs, in NewEC, that match omc_D_i. If don't cares are not represented by the sub-designs, then “matching,” between an OMC value omc_D_i and an EC NewEC_i of NewEC, can be defined as follows. Since the sub-designs of NewEC_i do not represent don't cares, each sub-design of NewEC_i (which can be referred to as NewEC_i,s) has the same OMC value that shall be referred to as omc_NewEC_i. omc_D_i matches omc_NewEC_i if they are numerically equal.

[0269] If the sub-designs of NewEC_i do represent don't cares, each sub-design NewEC_i,s of NewEC_i can have a min and max value (that can be referred to as min_NewEC_i,s and max_NewEC_i,s). Also, the OMC for D_i can be expressed as the following two values: min_omc_D_i and max_omc_D_i. min_omc_D_i and max_omc_D_i can be regarded as a range (referred to herein as the “don't care range” for D_i). Similarly, for each sub-design NewEC_i,s of NewEC_i, its min_NewEC_i,s and max_NewEC_i,s can be regarded as a range (referred to herein as a “don't care range”).

[0270] A NewEC_i,s is a member of NewEC_i, because between it, and any other member NewEC_i,s2 of NewEC_i, there is either overlap between the don't care ranges of NewEC_i,s and NewEC_i,s2 or, transitively, in combination with other sub-designs of NewEC_i, there is overlap between the don't care ranges of NewEC_i,s and NewEC_i,s2. Therefore, a D_i is added to NewEC_i if the don't care range of D_i overlaps the don't care range of any sub-design that is already a member of NewEC_i.

[0271] If there are no ECs for which the OMC of D_i matches (“if” of line 16 tests true), then a new EC, just for D_i, is started (take action of line 20). Otherwise, the following steps are performed (see “else” of lines 21-38). The ECs that match the OMC of D_i are combined, along with D_i, to produce a new EC called “NewElement.” Line 35. The ECs that match the OMC of D_i are removed from NewEC. Line 32. NewElement is added to NewEC. Line 37.

9.4. BuildBddInEqClass

[0272] FIGS. 19A-19B present a pseudo-code procedure “BuildBddInEqClass.” BuildBddInEqClass takes as input an equivalence class “EC” of sub-designs and a set of variables “V_s” that are to remain symbolic. Line 3, FIG. 19A. For each sub-design “F” of EC, BuildBddInEqClass applies BuildBdd; Lines 8-11, FIG. 19A.

[0273] BuildBdd takes three parameters (see line 19, FIG. 19A, for beginning of definition of BuildBdd): a point “F” in a design to be converted to a BDD, the location of a parent “P” to point “F” and the set V_s of variables that are to remain symbolic. BuildBdd does the actual recursive, depth-first, traversal of a sub-design “F.”

[0274] BuildBdd begins by testing whether a BDD has already been constructed for “F.” Lines 22-23, FIG. 19A. If not, the case of “F” representing an input is addressed (see lines 27-45, FIG. 19A). If “F” represents a variable that is to remain symbolic (i.e., the “if” of line 30, FIG. 19A, test true), a BDD node, representing the variable of V_s represented by “F,” can be generated. Line 31. Otherwise, “F” is to be assigned a binary value (see “else” of lines 32-43).

[0275] The case of “F” being an AND or OR is also addressed. Line 46, FIG. 19A to line 6, FIG. 19B. If “F” is an AND, its BDD can initially be a constant “1” (line 4, FIG. 19B) that is ANDed with the BDDs created (by recursive calls to BuildBdd) for each child of “F.” If “F” is an OR, its BDD can initially be a constant “0” (line 6, FIG. 19B) that is ORed with the BDDs created (by recursive calls to BuildBdd) for each child of “F.” Recursive calls to BuildBdd, for each child of “F,” are handled by the “for” loop of lines 9-17, FIG. 19B.

[0276] If “F” has an output inversion, its BDD can be negated. Lines 19-20.

9.5. BreakEqClassWithWmc

[0277] FIG. 16 presents a pseudo-code procedure “BreakEqClassWithWmc.” BreakEqClassWithWmc is similar to BreakEqClassWithOmc. Some of the differences are as follows. BreakEqClassWithWmc calls ChooseUniqueWeights to determine a set of weights U_s. Line 14. U_s assigns a unique weight to each variable of V_s that is to remain symbolic. U_s is included as a parameter to FindMatchWithWmc. Line 24.

9.6. FindMatchWithWmc

[0278] FIG. 17 presents a pseudo-code procedure “FindMatchWithWmc.” FindMatchWithWmc is passed an EC EC_one. Line 1. For each sub-design of EC_one the parameter “BDD” of FindMatchWithWmc contains a corresponding BDD.

[0279] The new subdivisions of EC_one, that FindMatchWithWmc is able to find, are stored in NewEC which is initialized to an empty set. Line 3.

[0280] For each sub-design D_i of EC_one a “for” loop (line 4) cause the following to be done.

[0281] A nested “for” loop (line 7) iterates over each EC, called EC_cur, that is a member of NewEC. A representative sub-design “R,” of EC_cur, is selected. Line 10. A test is performed, with CheckRelationsWithOmc, to determine if “R” can be distinguished from D_i with OMC. Line 14. If “R” and D_i can be distinguished, then the next EC of NewEC is tried. Lines 15-16. If “R” and D_i appear to be the same, under OMC, then a test is performed, with CheckRelationsWithWmc, to determine if “R” can be distinguished from D_i with WMC. Line 22. If “R” and D_i can be distinguished, then the next EC of NewEC is tried. Lines 23-24. Otherwise, D_i is added to EC_cur. Line 28.

[0282] CheckRelationsWithOmc can operate as follows. The OMC of “R” and D_i can be compared. If they have the same value, a true can be returned. If they do not have the same value, the seven OMC exceptions can be applied. If, when any one of the seven OMC exceptions is applied, “R” and D_i have the same value, a true can be returned. Otherwise, a false can be returned.

[0283] If CheckRelationsWithOmc returns a true, FindInputInversions can be applied (FIG. 17, line 19) prior to application of CheckRelationsWithWmc. FindInputInversions can identify any input inversions between “R” and D_i and store such input inversions in “Inv.”

[0284] CheckRelationsWithWmc can operate in the same way as CheckRelationsWithOmc, except for the following. The WMC of “R” and D_i can be compared by utilizing the unique weight, contained in U_s, that is assigned to each symbolic variable. If they do not have the same value, seven WMC exceptions can be applied. Testing for certain of the exceptions can involve utilization of the input inversion information passed to CheckRelationsWithWmc in “Inv.”

9.7. FindInputInversions

[0285] FIG. 18 presents a pseudo-code procedure “FindInputInversions.” The input parameters to FindInputInversions (line 1) are as follows: a sub-design SD1, a sub-design SD2, a BDD “BDD_SD1” for SD1 and a BDD “BDD_SD2” for SD2.

[0286] TestedVars can be the set of all variables tested for whether, as a necessary-but-insufficient condition for equivalency between SD1 and SD2, input inversion is required. If a variable v1 of an SD1 and a variable v2 of an SD2 are identified as needing to be input inverted, this means that if SD1 and SD2 are to be equivalent to each other, then v1 and v2 must be input inversions of each other.

[0287] For all variables of BDD_SD1 and BDD_SD2 that are symbolic, whether a pair of variables between them needs to be input inverted, as a necessary-but-insufficient condition for equivalence between two sub-designs, can be tested for by “TestInputInversions.” Line 7. As discussed above in section 4.2 (“Input Inversion”), TestInputInversions can use the technique of the J. Mohnke and S. Malik paper. A key difference in the operation of TestInputInversions, from the J. Mohnke and S. Malik paper, is that testing for input inversion is only done on the subset of variables currently symbolic.

[0288] The variables of BDD_SD1 and BDD_SD2 that are symbolic can be identified as the support of BDD_SD1 or BDD_SD2. The support of BDD_SD1 or BDD_SD2 can be added to TestedVars to indicate that these variables have been tested for input inversion., Line 10.

[0289] A “while” loop (lines 12-28) can be utilized by FindInputInversions to test for input inversion between all variables, of BDD_SD1 and BDD_SD2, that are assigned binary values. Each iteration of the “while” selects at least one variable, called “var_cur,” for input inversion testing. Line 16. ChooseDirectedSymbolicVariables is called. Line 22. ChooseDirectedSymbolicVariables chooses a set of variables to remain symbolic, where the set of symbolic variables includes var_cur. The variables not chosen by ChooseDirectedSymbolicVariables, to remain symbolic, are assigned binary values. BDDs are built for each sub-design (lines 23-24) and TestInputInversions is executed. Each execution of TestInputInversions differs from the J. Mohnke and S. Malik paper by testing for input inversion with only a subset of the variables being symbolic.

[0290] The combinational design distinguishing architecture of the present invention, or each of its component sub-systems individually, can be executed within a computing environment (or data processing system) such as that of FIG. 20. FIG. 20 depicts a workstation computer 6000 comprising a Central Processing Unit (CPU) 6001 (or other appropriate processor or processors) and a memory 6002. Memory 6002 has a region 6003 in which is stored the software tools (or computer programs) and data of the present invention. While 6003 is depicted as a single region, those of ordinary skill in the art will appreciate that, in fact, such software may be distributed over several memory regions or several computers. Furthermore, depending upon the computer's memory organization (such as virtual memory), memory 6002 may comprise several types of memory (including cache, random access memory, hard disk and networked file server). Computer 6000 can be equipped with a display monitor 6005, a mouse pointing device 6004 and a keyboard 6006 to provide interactivity between the software of the present invention and a chip designer. Computer 6000 also includes a way of reading computer readable instructions from a computer readable medium 6007, via a medium reader 6008, into the memory 6002. Computer 6000 also includes a way of reading computer readable instructions via the Internet (or other network) through network interface 6009.

[0291] In some embodiments, computer programs embodying the present invention are stored in a computer readable medium, e.g. CD-ROM or DVD. In other embodiments, the computer programs are embodied in an electromagnetic carrier wave. For example, the electromagnetic carrier wave may include the programs being accessed over a network.

• [0292] combinational design discriminator (CDD): a technique for determining whether first and second combinational designs are functionally different. Example CDDs are OMC and WMC.
• [0293] combinational sub-design: without loss of generality, can be regarded as comprised of n input variables and one output variable. Can be referred to herein as D1 or D2.
• [0294] EC: equivalence class.
• [0295] The “J. Mohnke and S. Malik paper” is the following paper that is herein incorporated by reference in its entirety: J. Mohnke and S. Malik, “Permutation and phase independent Boolean comparison,” In Proceedings of the European Conference on Design Automation, pages 86-92, February 1993.
• [0296] Literal: a symbolic representation of a binary value assigned to a Boolean variable.
• [0297] MC: refers to generic minterm counting, that can be OMC or WMC.
• [0298] Pseudo-code: The pseudo-code presented herein is loosely based on the C programming language. The C programming language is described in such texts as “A Book on C,” by A. Kelley and I. Pohl, Benjamin Cummings Pub. Co., Third Edition, 1995, ISBN 0-8053-1677-9, herein incorporated by reference in its entirety. In pseudo-code procedure calls, a parameter is prefixed with the “&” operator to indicate that the called procedure will operate on the data object of the calling procedure. This use of the “&” operator is a standard part of the C programming language.
• [0299] OMC: ordinary minterm counting.
• [0300] support of a sub-design: the set of input variables, to a sub-design, that are symbolic and have not been assigned a particular binary value.
• [0301] WMC: weighted minterm counting.

[0302] While the invention has been described in conjunction with specific embodiments, it is evident that many alternatives, modifications and variations will be apparent to those skilled in the art in light of the foregoing description. Accordingly, it is intended to embrace all such alternatives, modifications and variations as fall within the spirit and scope of the appended claims and equivalents.