Archive for June, 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.

Most of the code I read – and I read a lot of other people’s code – is utterly incomprensible at a first reading. In the last post, I described the major cause of this: the unstructured format of most RTL.

Chapter 3 of The Art of Good Design describes a project where I re-wrote (refactored) a large (28 page) module to make it simpler and easier to understand. The initial code was well-written and completely clear – to the engineer who created it. I was determined to understand its behavior without consulting the original author. Limiting myself to just reading the code, it took me weeks to figure out what the code really did. Even then, I had to restructure the code extensively to analyze it. My claim is that once I rewrote the code in a more structured fashion, the code became clear and obvious. I also claim that it is quantitatively much simpler – the state space is much, much smaller.

Here is Chapter 3.