Concurrent formal verification of logic synthesis

This disclosure relates to formal verification. More specifically, this disclosure relates to concurrent formal verification of logic synthesis.

The importance of verification in integrated circuit (IC) design cannot be over-emphasized. It would be highly risky to use IC designs in mission-critical devices and applications if the IC designs had not been thoroughly verified. One approach for verifying an IC design involves simulating the IC design. However, this approach cannot provide any guarantees regarding the behavior of the IC design because it is computationally infeasible (and often impossible) to exhaustively simulate non-trivial IC designs. Another approach is to use formal verification to mathematically prove that the IC design will operate correctly.

An important problem in the area of formal verification involves equivalence checking between two or more circuit designs that are specified at the same or different abstraction levels. For example, equivalence checking can be performed between two register transfer level (RTL) designs or between an RTL design and a netlist that is produced by synthesizing the RTL design.

FIGS. 1A and 1B illustrate how equivalence checking is performed in existing approaches. As shown in FIG. 1A , RTL design 102 can be synthesized to obtain netlist 104 . Specifically, as shown in FIG. 1B , RTL design 102 can be provided to synthesis tool 106 which can produce netlist 104 . Synthesis tool 106 can perform numerous transformations and optimizations on RTL design 102 during synthesis. It is important to check if netlist 104 is functionally equivalent to RTL design 102 . This can be accomplished by providing RTL design 102 and netlist 104 to equivalence checking tool 108 . Equivalence checking tool 108 can formally verify whether or not RTL design 102 is functionally equivalent to netlist 104 . If the equivalency check succeeds, then subsequent IC design flow operations can be performed on netlist 104 . If the equivalency check fails, then the failure can be reported, and an IC designer can take corrective actions.

Unfortunately, existing formal verification tools can take a long time to check equivalence of an RTL design with a corresponding netlist. Moreover, the synthesis and the formal equivalence checking steps need to be performed every time formal equivalence checking fails, which can significantly increase the overall IC design cycle time. Hence, what are needed are techniques and systems to efficiently perform formal equivalence checking without the above-described problems.

Some embodiments described herein provide techniques and systems for concurrently performing formal verification during logic synthesis. A synthesis tool executing on a computer can synthesize a netlist design d n based on an RTL design d 0 of an IC. While synthesizing the netlist design d n , the synthesis tool can output a sequence of intermediate checkpoint designs d 1 , d 2 , . . . , d n-1 . A formal verification engine executing concurrently with the synthesis tool on the same computer or a different computer can check equivalence between designs d i and d j , where 0≤i<j≤n.

In some embodiments, an intermediate checkpoint design is a structural netlist that is not completely mapped to a specific technology library. In some embodiments, the intermediate checkpoint design can refer to a generic technology library model. In some embodiments, the intermediate checkpoint design includes at least one unimplemented RTL operator block. In some embodiments, the intermediate checkpoint design includes at least one generic sequential primitive.

In some embodiments, outputting the sequence of intermediate checkpoint designs comprises copying forward at least one of: metadata, real data, and user setup data. In some embodiments, the metadata comprises expression strings defining word-level functions of arithmetic operators. In some embodiments, the metadata comprises data-flow graphs specifying operators and connectivity. In some embodiments, the real data comprises a second implementation of an operator that replaced a first implementation of the operator, wherein the second implementation requires less computation to check equivalence than the first implementation. In some embodiments, the user setup data includes a user command to force a particular signal in the design to a constant value.

FIGS. 1A and 1B illustrate how equivalence checking is performed in existing approaches.

FIGS. 2A and 2B illustrate concurrent formal verification of logic synthesis in accordance with some embodiments described herein.

FIG. 3 illustrates a process for performing concurrent formal verification of logic synthesis in accordance with some embodiments described herein.

FIG. 4 illustrates a computer system in accordance with some embodiments described herein.

The following description is presented to enable any person skilled in the art to make and use the invention, and is provided in the context of a particular application and its requirements. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the present invention. Thus, the present invention is not limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features disclosed herein.

Overview of IC Design and Manufacturing

An IC design and manufacturing process produces IC chips. IC design software tools can be used to create an IC design. Once the IC design is finalized, it can undergo fabrication, packaging, and assembly to produce IC chips. The overall IC design and manufacturing process can involve multiple entities, e.g., one company may create the software for designing ICs, another company may use the software to create the IC design, and yet another company may manufacture IC chips based on the IC design. An IC design flow can include multiple steps, and each step can involve using one or more IC design software tools. An improvement to one or more of these steps in the IC design flow results in an improvement to the overall IC design and manufacturing process. Specifically, the improved IC design and manufacturing process can produce IC chips with a shorter time-to-market (TTM) and/or higher quality of results (QoR).

An IC design can be represented by using different data formats or languages as the IC design progresses through an IC design flow, wherein the different data formats or languages represent the IC design at different levels of abstraction. In general, higher levels of abstraction contain fewer details of the IC design than lower levels of abstraction. Typically, the IC design is described at a high level of abstraction in the early stages of the IC design flow, and the level of abstraction becomes progressively lower as the IC design moves through the IC design flow (the description of the IC design becomes more specific as the IC design progresses through the IC design flow).

For example, toward the beginning of the IC design flow, an IC design can be described at a high level of abstraction by using a hardware description language (HDL) which describes the functionality of the IC design but does not include information about the actual geometric shapes that will be printed on the wafer. Toward the end of the IC design flow, the same IC design can be represented in a low level of abstraction by using a data format or language such as GDSII or OASIS, which contains a description of the actual geometric shapes that are to be printed on the wafer. In between the two ends of the IC design flow, the IC design may be represented in numerous data formats or languages that describe the same IC design at different levels of abstraction.

Some examples of IC design steps and the associated software tools are described below. These examples are for illustrative purposes only and are not intended to limit the embodiments to the forms disclosed. This disclosure describes embodiments that can be used in one or more IC design steps.

IC design software tools enable IC designers to describe the functionality that the IC designers want to implement. These tools also enable IC designers to perform what-if planning to refine functionality, check costs, etc. During logic design and functional verification, the HDL, e.g., SystemVerilog, code can be written and the design can be checked for functional accuracy, e.g., the design can be checked to ensure that it produces the correct outputs.

During synthesis and design for test, the HDL code can be translated to a netlist using one or more IC design software tools. Further, the netlist can be optimized for the target technology, and tests can be designed and implemented to check the finished chips. During netlist verification, the netlist can be checked for compliance with timing constraints and for correspondence (i.e., equivalence checking) with the RTL design and/or HDL code.

During design planning, an overall floorplan for the chip can be constructed and analyzed for timing and top-level routing. During physical implementation, circuit elements can be positioned in the layout and can be electrically connected.

During analysis and extraction, the IC design's functionality can be verified at a transistor level and parasitics can be extracted. During physical verification, the design can be checked to ensure correctness for manufacturing, electrical issues, lithographic issues, and circuitry.

During resolution enhancement, geometric manipulations can be performed on the layout to improve manufacturability of the design. During mask data preparation, the design can be “taped-out” to produce masks which are used during fabrication.

Overview

Formal logical equivalence checkers prove that the netlist a synthesis tool creates is logically equivalent to its original RTL design. As explained above, in existing approaches, equivalence checking must run after synthesis is complete, reading the original RTL design and the derived netlist, and verifying their equivalence. Synthesis tools may also produce a “guidance” file that gives the equivalence checker hints about optimizations it performed to improve the tractability of the equivalence checking problem, which is NP-complete. Such guidance improves the equivalence checker's ability to complete the verification.

Some embodiments described herein comprise two components that together improve equivalence checking completion and time to results. Specifically, in some embodiments, a synthesis tool writes intermediate checkpoint designs that embody the state of the design under synthesis as optimization progresses. Meanwhile, formal equivalence checking proceeds in parallel with synthesis and checks the intermediate checkpoint designs for equivalence.

Specifically, one implementation can be as follows: (1) at start of compile, a synthesis tool invokes a formal logic equivalence checker, (2) the synthesis tool writes intermediate checkpoint designs (and any additional information, e.g., guidance) as optimization progresses, (3) in parallel with ongoing synthesis and optimization, the formal logic equivalence checker reads each checkpoint design (and any additional information, e.g., guidance) as it is written or outputted, and verifies its equivalence to the previous checkpoint design (or original RTL design in the case of the first intermediate checkpoint design), and (4) at end of compile, the synthesis tool writes the final netlist and the formal logic equivalence checker verifies its equivalence to the last checkpoint design. This concurrent approach verifies the final netlist's equivalence to the original RTL by inference. Each checkpoint verification and the final verification are more tractable (i.e., require less computation) than the RTL-to-final-netlist verification would be, because the designs are more similar to each other. Moreover, formal equivalence checking completes quickly after synthesis.

Some embodiments described herein provide techniques and systems for checking logical equivalence between an RTL design and a netlist that is created by a synthesis tool by synthesizing the RTL design. Specifically, in some embodiments, (1) an RTL design can be received by a synthesis tool executing on a first processing mechanism, (2) a final netlist can be created by the synthesis tool based on the RTL design, wherein the synthesis tool creates one or more intermediate checkpoint designs before creating the final netlist, and wherein the synthesis tool provides the intermediate checkpoint designs to a formal logic equivalence checking tool that is executing in parallel on a second processing mechanism, and (3) the formal logic equivalence checking tool can formally verify functional equivalence between: (i) the RTL design and an intermediate checkpoint design, (ii) two intermediate checkpoint designs, or (iii) an intermediate checkpoint design and the final netlist.

Concurrent Formal Verification of Logic Synthesis

FIGS. 2A and 2B illustrate concurrent formal verification of logic synthesis in accordance with some embodiments described herein. RTL design 202 can be synthesized to produce netlist 204 . In some embodiments described herein, multiple intermediate checkpoint designs can be outputted during synthesis. Specifically, as shown in FIG. 2A , RTL design 202 is the initial design do, netlist 204 is the final design d n , and designs d i and d j , where 1<i<j<n, are intermediate checkpoint designs. An intermediate checkpoint design d i can be checked for equivalence against (1) the original RTL design d 0 , (2) another intermediate checkpoint design d j , or (3) the final netlist d n .

As shown in FIG. 2B , synthesis tool 206 can receive RTL design d 0 as an input, and output a sequence of intermediate checkpoint designs, e.g., d i , . . . , d j , while performing synthesis, and finally output netlist d n when synthesis is completed. Equivalence checking tool 208 can receive, as input, any two of the following IC design representations: the original RTL design d 0 , the intermediate checkpoint designs d i , . . . , d j , and the final netlist d n . Next, equivalence checking tool 208 can check equivalence between the two IC design representations.

Specifically, equivalence checking tool 208 can execute concurrently with respect to synthesis tool 206 . For example, synthesis tool 206 can output intermediate checkpoint design d i after performing a set of synthesis operations, and continue performing additional synthesis operations to further transform and/or optimize the IC design. After synthesis tool 206 has outputted intermediate checkpoint design d i , and while synthesis tool 206 is performing further synthesis operations, equivalence checking tool 208 can concurrently check equivalence between RTL design d 0 and intermediate checkpoint design d i . Subsequently, when synthesis tool 206 outputs another intermediate checkpoint design d j , equivalence checking tool 208 can concurrently check equivalence between intermediate checkpoint designs d i and d j . Finally, when synthesis tool 206 outputs netlist d n , equivalence checking tool 208 can check equivalence between an intermediate checkpoint design and the final netlist d n . Specifically, in some embodiments, as the synthesis tool is outputting IC designs d i , 1≤i≤n, the equivalence checking tool concurrently checks equivalence between IC designs d i and d i-1 .

If equivalence checking tool 208 determines that the two designs are not equivalent, then equivalence checking tool 208 can report the failure, and a user can take appropriate actions to correct the problem. Corrective actions include, but are not limited to, modifying the RTL design and/or changing the number and/or type of transformations/optimizations that are performed during synthesis. In some embodiments, the corrective action can be to continue synthesis and attempt proving equivalence with the next intermediate checkpoint design. For example, if equivalence checking between intermediate checkpoint designs d i and d j fails, then the process can allow synthesis to continue, and attempt to prove equivalence between intermediate checkpoint designs d i and d j+1 once the intermediate checkpoint design d j+1 becomes available. On the other hand, if all equivalence checks succeed, then netlist 204 can undergo subsequent steps in the IC design flow to result in IC chips.

In embodiments described herein, the wall clock time (i.e., the time from which synthesis starts to the time when verification ends) required to synthesize a netlist from an RTL design, and to check equivalence by inference between the RTL design and the netlist is substantially less than existing approaches because equivalence checking is performed concurrently with logic synthesis. After the final netlist d n is outputted, some embodiments described herein only need to check equivalence between intermediate checkpoint design d n-1 and the final netlist d n , which takes significantly less time than checking equivalence between initial RTL design d 0 and final netlist d n .

Note that it is not obvious to perform equivalence checking concurrently with logic synthesis. Requiring the synthesis tool to write intermediate checkpoint designs increases the amount of computational time and resources required by the synthesis tool to produce a netlist based on an RTL design. Embodiments disclosed herein are based on the following non-obvious insight: the increase in the computational time and resources for writing intermediate checkpoint designs is more than offset by the amount of time saved by concurrently performing equivalence checking.

FIG. 3 illustrates a process for performing concurrent formal verification of logic synthesis in accordance with some embodiments described herein. The process can begin by synthesizing a netlist design d n based on an RTL design d 0 of an IC by using a synthesis tool executing on a computer (step 302 ). A sequence of intermediate checkpoint designs d 1 , d 2 , . . . , d n-1 can be outputted by the synthesis tool while synthesizing the netlist d n based on the RTL design d 0 (step 304 ). The process can then check equivalence between designs d i and d i , where 0≤i<j≤n by using a formal verification engine that is executing concurrently with the synthesis tool on the same computer or a different computer (step 306 ).

Note that an intermediate checkpoint design is not an RTL design, nor is it a final netlist. In some embodiments, an intermediate checkpoint design is a structural netlist, but it may not be completely mapped to a specific technology library as a final netlist is. An intermediate checkpoint design may refer to generic technology library (“GTECH”) models, and it may refer to completely unimplemented RTL operator blocks (arithmetic operators such as adders, multipliers, etc., or generic mux operators) that have no internal content. The equivalence checking tool must interpret such operator blocks as if they were RTL. The intermediate checkpoint design may also include references to a generic sequential primitive (“SEQGEN”), inferred from RTL but not yet mapped to a real register model.

In some embodiments, certain design-related data can be copied forward across intermediate checkpoint designs, i.e., if the data is created while generating design d i , then the data can be copied forward to designs d i , where j>i. Specifically, three types of data can be created and copied forward in this manner:

(1) Metadata. Expression strings defining the word-level functions of arithmetic operators are derived when the logic synthesis tool generates guidance for the equivalence tool. These strings are attached to specific operator blocks. When a subsequent checkpoint is encountered, they can be carried forward from the pre-checkpoint reference design to the checkpoint, for use in subsequent guidance processing. In some embodiments, a data-flow graph specifying the operators and connectivity can be created to facilitate equivalence checking. Specifically, such data-flow graphs may be needed to describe more complex data-paths which would be too cumbersome to describe by using only string expressions. (2) Real data. In some cases, a checkpoint may include arithmetic operator blocks that have been implemented, but the implementation is not friendly to subsequent guidance processing. In these cases, the equivalence checking tool discards the internals of the operator in the intermediate checkpoint design and replaces it with its own, friendlier, implementation. Specifically, the real data can include a second implementation of an operator that replaced a first implementation of the operator, wherein the second implementation requires less computation to check equivalence than the first implementation (that is why it is called a “friendlier” implementation). (3) User setup data. If user set-up commands, for example forcing a certain signal to a constant value, have been applied to the original RTL design, then such set-up commands can be carried forward across each checkpoint.

Computer System

The term “computer” or “computer system” generally refers to a hardware-based system that can perform computations required for the design and manufacture of ICs. FIG. 4 illustrates a computer system in accordance with some embodiments described herein. Computer system 402 can include processor 404 , memory 406 , and storage device 408 . Computer system 402 may include multiple processors, and processor 404 may include multiple cores. Specifically, memory locations in memory 406 can be addressable by processor 404 , thereby enabling processor 404 to access (e.g., via load/store instructions) and manipulate (e.g., via logical/floating point/arithmetic instructions) the data stored in memory 406 . Computer system 402 can be coupled to display device 414 , keyboard 410 , and pointing device 412 . Storage device 408 can store operating system 416 , IC design tool 418 , and data 420 . Data 420 can include input required by IC design tool 418 and/or output generated by IC design tool 418 .

Computer system 402 may automatically (or with user help) perform one or more operations that are implicitly or explicitly described in this disclosure. Specifically, computer system 402 can load IC design tool 418 into memory 406 , and IC design tool 418 can then be used to produce a synthesized IC design, wherein the IC design tool 418 can perform equivalence checking concurrently while producing the synthesized IC design. Specifically, IC design tool may include a synthesis tool and a formal verification engine that are executed on separate computer systems, or separate processors of the same computer system, or separate cores of the same processor. When the synthesized IC design is manufactured, the resulting IC chips contain the synthesized IC design which was formally verified using techniques and systems described herein.

The above description is presented to enable any person skilled in the art to make and use the embodiments. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art, and the general principles defined herein are applicable to other embodiments and applications without departing from the spirit and scope of the present disclosure. Thus, the present invention is not limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features disclosed herein.

The data structures and code described in this disclosure can be partially or fully stored on a computer-readable storage medium and/or a hardware module and/or hardware apparatus. A computer-readable storage medium includes, but is not limited to, volatile memory, non-volatile memory, magnetic and optical storage devices such as disk drives, magnetic tape, CDs (compact discs), DVDs (digital versatile discs or digital video discs), or other media, now known or later developed, that are capable of storing code and/or data. Hardware modules or apparatuses described in this disclosure include, but are not limited to, application-specific integrated circuits (ASICs), field-programmable gate arrays (FPGAs), dedicated or shared processors, and/or other hardware modules or apparatuses now known or later developed.

The methods and processes described in this disclosure can be partially or fully embodied as code and/or data stored in a computer-readable storage medium or device, so that when a computer system reads and executes the code and/or data, the computer system performs the associated methods and processes. The methods and processes can also be partially or fully embodied in hardware modules or apparatuses, so that when the hardware modules or apparatuses are activated, they perform the associated methods and processes. Note that the methods and processes can be embodied using a combination of code, data, and hardware modules or apparatuses.

The foregoing descriptions of embodiments of the present invention have been presented only for purposes of illustration and description. They are not intended to be exhaustive or to limit the present invention to the forms disclosed. Accordingly, many modifications and variations will be apparent to practitioners skilled in the art. Additionally, the above disclosure is not intended to limit the present invention. The scope of the present invention is defined by the appended claims.