Formal Moment Of Zen

22 Oct 2008 • 3 minute read

Most of my experience in functional verification prior to my dabbling in FPV was in the area of SystemC/SCV and simulation acceleration. I naturally brought a simulation-mindset to FPV. As a matter of fact, it is possible to go far in FPV by thinking about the verification problem in procedural terms. Instead of writing BFMs and behavioral checkers, you write properties that each model a small portion of the environment, and together model the whole. You can almost imagine (wrongly, of course, as pointed out in my last post) FPV as some form of random simulation based on the PSL/SVA/OVL constraints.

It was a while before I realized that FPV might call for a whole different way of looking at the problem domain. My moment of zen was triggered by a piece of code that someone had sent me. It went something like this -

1.... module test ( );
2....
3....     ...
4....     wire        wen;
5....     wire        ren;
6....     wire [4:0] wdata;
7....     wire [4:0] rdata;
8....
9....     fifo i_fifo(clk, rst, wen, wdata, ren, rdata);
10..
11..     wire [4:0] data;
12..
13..     stability_constraint: assume property (
14..         @(posedge clk) disable iff(rst)
15..         data == $past(data)
16..     );
17..
18..     data_check: assert property (
19..         @(posedge clk) disable iff(rst)
20..         (wen && wdata == data) |-> ##[0:$] (ren && rdata == data)
21..     );
22..
23.. endmodule

The purpose of this piece of code was to check that the FIFO -

Did not corrupt data
Did not drop data

Lines 13-16, declare that the undriven wire "data" must always be equal to its value in the previous cycle. This "data" signal is then used in the assertion of the FIFO's data integrity in,

Lines 18-21, which express the assertion that -
Whenever we see a write into the FIFO, the same data must eventually be read out.

I spent a while trying to parse the assumption (13-16) and how it affected the assertion (18-21). My a-ha moment was the realization that,

the assumption "fixed" the current value of the "data" in terms of its value in the previous cycle,
but it said nothing about the initial value of "data" at i.e. at time 0, and
since the initial value of "data" is undefined and there are no other drivers on it, formal analysis has to consider all possible initial values for "data".

If you followed the discussion so far you would appreciate, as I did at the time, the perfectly cool way in which this achieved data enumeration by relying on the first principle of formal analysis - that it considers all possible states that are admitted by the constraints.

To elaborate this further, since the "data" value is un-initialized, the analysis will initialize it to all values between 0-31 and analyze the assertion for each. In pseudo-code the analysis might be represented by -

foreach i in (0 ... 31)
fork // Imagine each check is analyzed simultaneously
    data_check_i: assert property (
        @(posedge clk) disable iff(rst)
        (wen && wdata == i) |-> ##[0:$] (ren && rdata == i)
    )
join
endfor

It was the first time I really understood the significance of formal analysis considering all possible states within the set of constraints. Further, I was blown away by how concisely I could represent the data-integrity property of the FIFO that -

Could be rigorously proven using formal methods
Was immediately usable in the verification of most FIFO implementations

I have subsequently discovered other cool ways of expressing properties that are specific to FPV and are not completely intuitive to someone from a simulation background. But these patterns and idioms of FPV are intuitive once the mechanics of formal analysis are internalized. Frequently, all it requires is a single moment of zen.

Have you a formal moment of zen to share?