Posted by mike keating on June 23rd, 2009
There is a conventional argument that complete verification is impossible. It goes like this: even a simple design of 100 flops has a state space of 2^100, which, simulating at a GHz, would take longer than the life of the universe to completely test. This argument raises some important points.
One key point is that verification is the hardest problem in chip design and in EDA. It is NP-complete, like many other problems in EDA, such as optimization. But it is the one problem for which we do not have heuristics that give us a “good enough” solution. Therefore we must keep the state space of a design as small as possible – the only practical way to manage NP complete problems.
Another key point is that a state space of 2^100 is clearly too large for any human to understand. So we are developing designs no one understands. This can’t be good!
In my experience, most designs can be refactored to reduce the state space by orders of magnitude. By parititioning the design well we can make the resulting state space much easier to understand. In fact, improving how we manage design state space is the key to improving how we do design and verification.
Chapter 4 of the Art of Good Design discusses this key issue of state space management.