TDEB Top Bar

Trending
Semiconductor Industry News — The Digital Electronics Blog
Follow Us

TDEB Masthead

The Semiconductor Hub

Semiconductors.  Chips and Systems.  Innovation.

Indexed by leading Search Engines, AI and referenced by Engineers worldwide 500+ Articles 10M+ Pageviews 30+ Reports 50+ Citations

Formal Verification and Equivalence Checking

The Editor's Desk
by
0
Share Facebook X LinkedIn WhatsApp Email

Design verification must show that the design, expressed at the RTL or structural level, implements the operations described in the data sheet or whatever other specification exists.

Verification at the RTL level can be accomplished by means of simulation, but there is a growing tendency to supplement simulation with formal methods such as model checking. At the structural level the use of equivalence checking is becoming standard procedure. In this operation the RTL model is compared to a structural model, which may have been synthesized by software or created manually. Equivalence checking can determine if the two levels of abstraction are equivalent. If they differ, equivalence checking can identify where they differ and can also identify what logic values cause a difference in response.

Simulation versus formal methods, in plain words

Simulation applies test inputs and checks the outputs. It is flexible and easy to understand, but it only proves the design works for the inputs you tried. A 64-bit adder has 2128 input combinations; no simulator will ever try them all.

Formal methods use mathematics instead of test vectors. They reason about every possible input at once, so when a formal tool says a property holds, it holds for all inputs. When it fails, the tool produces a counterexample: a specific input sequence that shows the bug. There are two main families.

  • Model checking (property checking): you write properties, such as "a request is always granted within 8 cycles" or "the FIFO never overflows", and the tool proves or disproves them on the RTL.
  • Equivalence checking: you give the tool two versions of the same design and it proves that they produce the same outputs. No properties are needed; one version is the reference.

Where equivalence checking fits in the flow

Once the RTL has been verified by simulation and property checking, it becomes the "golden" reference. Every later transformation is checked against it rather than re-simulated:

  • RTL to synthesized netlist, to catch synthesis bugs and wrong constraints.
  • Netlist to netlist after scan insertion and other test logic, with test mode disabled.
  • Netlist to netlist after placement, clock tree synthesis and timing optimization, which resize, buffer and restructure gates.
  • Manual engineering change orders (ECOs), where an engineer edits the netlist by hand late in the project.

Each check runs in minutes to hours, against days or weeks for a full gate-level regression, which is why it became standard sign-off practice.

Update, December 18, 2008

Another series of steps in equivalence checking goes beyond what was described above:

  • RTL to pre-synthesis netlist
  • Pre-synthesis netlist versus post-synthesis netlist

Splitting the check this way isolates problems: a mismatch in the first step points at how the RTL was read and elaborated, a mismatch in the second at the optimization itself.

Deep dive: the numbers and details

This part holds how the tools work, a small worked example and the common pitfalls. Skip it if the overview is all you need.

Combinational equivalence: matching the registers first

Most RTL-to-netlist checks rely on the fact that synthesis keeps the same registers. The tool first maps "compare points" between the two designs: primary outputs, and the inputs of every flip-flop and latch. It matches them by name, by structure and by simulation signatures. Once the registers are paired, the problem breaks into many small combinational checks. For each compare point, the logic cone that drives it in design A must compute the same Boolean function as the cone in design B, given the same register outputs and primary inputs.

Formally, for two cones fA(x) and fB(x), the tool builds a "miter": the XOR of the two outputs, m(x) = fA(x) XOR fB(x). The designs are equivalent at that point if and only if m(x) = 0 for every input x. Showing that m cannot be 1 is a satisfiability question.

The two engines: BDDs and SAT

Two families of Boolean reasoning do the work, often in the same tool (see formal equivalence checking: methods):

  • Binary decision diagrams (BDDs): a canonical graph form of a Boolean function. Two functions are equal exactly when their reduced, ordered BDDs are identical, so the comparison is trivial once the BDDs are built. The catch is size: for some functions, such as multipliers, BDDs grow exponentially.
  • SAT solvers: search for an input that makes the miter output 1. If none exists, the cones are equivalent. If one is found, it is the counterexample. Modern solvers handle very large cones, and internal equivalent points found by simulation are used to cut the problem into smaller pieces.

A worked example

RTL: y = (a AND b) OR (a AND c). Synthesis factors it to y' = a AND (b OR c) to save a gate.

abcy (RTL)y' (netlist)miter
000000
001000
010000
011000
100000
101110
110110
111110

The miter is 0 for all 8 inputs, so the two are equivalent. A real cone may have hundreds of inputs; enumerating 2n rows is impossible, which is why the tool uses BDDs or SAT instead of a truth table. Now suppose a bad ECO changed the netlist to a AND (b AND c). The solver returns the counterexample a=1, b=1, c=0: the RTL gives 1, the netlist 0. That is exactly the "what logic values cause a difference" mentioned above.

Sequential equivalence

Some transformations change the registers themselves: retiming moves flip-flops across logic, state machines are re-encoded (binary to one-hot, for example), and pipelines are added. The compare points no longer match one to one, and the check becomes sequential: do the two machines produce the same output sequence for every input sequence, starting from corresponding reset states? This cannot be reduced to a set of combinational checks and is much harder, so tools either use special handling for known transformations (retiming, FSM re-encoding) or sequential equivalence engines with bounded or inductive proofs.

Common pitfalls

  • Unmapped compare points: renamed or merged registers that the tool cannot pair. Unmapped points are not verified, so they must be reviewed, not ignored.
  • Constant and test logic: scan chains and test modes must be held in functional mode with set-up constraints, or every scan multiplexer shows up as a difference.
  • Don't-care handling: 'X' assignments in RTL let synthesis choose 0 or 1. The checker must be told whether the RTL X means "anything is fine".
  • Black boxes: memories and analog macros are not checked inside; only their pins are. The models used must match the real cells.
  • Proving the wrong thing: equivalence shows two designs match, not that either is correct. A bug in the golden RTL passes straight through, which is why simulation and property checking remain necessary.

Interview angle

Common questions: what is a compare point; why is combinational equivalence enough after synthesis but not after retiming; what does an equivalence checker need from DFT insertion to pass; and why does a passing equivalence check not prove the design is correct. Each answer is in the sections above.

Commercial tools

Widely used equivalence checkers include Cadence Conformal and Synopsys Formality, with Siemens (formerly Mentor Graphics) and others offering their own (list of commercial equivalence checkers).

Further reading

The Editor's Desk
About the Author
The Editor's Desk
Share Facebook X LinkedIn WhatsApp Email

Post a Comment

0 Comments

Your comments will be moderated before it appears here.

Post a Comment (0)

#buttons=(Ok, Go it!) #days=(20)

Our website uses cookies to enhance your experience. Learn more
Ok, Go it!