The Joy of Verification

Verification is often considered the wicked step-child of design. Most designers want to design because to design is to create. There is not an ounce of creative work that goes into verification. Designers tell verification engineers what tests to write and the verification engineers job is simply to code these tests with little or no input on their part on the design of the tests. It’s not surprising, then, that most engineers want to be designers.

However, this view of verification engineering misses the point. In fact, looked at from a non-engineering point of view, verification can actually be viewed as the more critical task and, more importantly to the verification engineer, the more prestigious task. It all comes down to how one defines the job ‘engineering’ as opposed to, say, ’scientist’, or ‘artist’. From a societal point-of-view, each one of these jobs is equally important. In fact, it is often the case that scientists look down their noses at engineers because engineers simply use knowledge that scientists discover. Engineers point out that most of today’s technological marvels are created by engineers, not scientists. Artists look down on both since neither of them creates anything beautiful.

The relationship between design and verification is analogous to the relationship between engineers and scientists. Thus, it is understandable that designers can look down on verification and, at the same time, verification can rightly hold a position of respect equal or higher than design.

The task of engineering can be viewed as a combination of art and science. Science is defined as the discovery of knowledge. This is usually taken to mean some fundamental knowledge about the universe, but can, in a broader sense, apply to any knowledge. For example, suppose no one has ever designed an 10G Ethernet controller in 65nm technology and you were tasked with doing exactly that. Clearly, it would be necessary to first gain some knowledge of how to do this. Since no one has done this before, you essentially would be performing the role of a scientist while gaining this knowledge. In fact, all through the design process, most of the work will be taken discovering knowledge about how to design such a product. Generalizing broadly, we can say that 99% of engineering is science.

The primary tool at the scientist’s disposal is the scientific method: hypothesize, perform experiments, conclude results. Usually, hypothesizing and concluding require virtually no time, making experimentation the most time consuming part. The most time consuming part of this effort is designing the experiment. Designing is engineering. Consider the Apollo moon program. The actual science conducted in this project was a few hours gathering moon rocks. Engineering the experimental apparatus, which is to say, the moon rocket required thousands of man-years of effort. Thus, again generalizing broadly, we can say that 99% of science is engineering.

Art is the creation of beautiful objects, engineering is the creation of useful objects. Although the output of these acts is very different, the actual process has many similarities. Most people understand that engineering useful objects is a very rule-bound process. The creation of art is also a very rule-bound process. In painting, beauty comes about because of a detailed understanding of color, composition, materials, and a number of other factors. It is possible for you or I to create art without understanding these rules, but the probability of creating something beautiful is as remote as if one randomly soldered together some resistors, capacitors, and transistors and it ended up being something useful. Music, in particular, has intricate rules that often leave little choice in what notes to choose during composition. It is often thought that genius is the ability to break rules and find new and better rules. In fact, the opposite is true. Whether it be Mozart or Einstein, geniuses do sublime work by strictly following the rules. In fact, it is their deeper understanding of the rules that allows them to see better what can be done.

We can define engineering as combining the creativity of art and the discovery of knowledge of science. Design is the artistic side, but which still requires strict discipline in following rules, which are given by specifications and other design rules. At the same time, design requires figuring out how to design something which has never been designed before. There clearly is some up front scientific discovery needed.

Verification is like science. A verification engineer is given a design, about which very little is known. In particular, it is not known whether there are any bugs in the design or what they might be. The goal of the verification process is to discover any bugs. This, more than anything, is science. Thus, if design brings out the artist in an engineer, verification brings out the scientist. Both are noble.

The training of an engineer is highly disciplined and is done with a heavy dose of the scientific method. Why, then, do engineers disdain verification so much? Much of the blame can be laid on the need for instant gratification. At the very beginning, both verification and design require some amount of discovery of knowledge in the form of studying the specification. After this, the first step of design is purely creative, the fun part of design. The first step in verification is pure drudgery, setting up test benches, scripts, and writing endless tests. After the creative part of the design is done, the rest is pure drudgery. The fun part of verification occurs after all the drudgery is complete, and that is when the verification engineer starts discovering bugs in the design.

There is no greater joy than discovering a bug that reveals some fundamental mis-understanding about the design. This new knowledge can have a dramatic effect on the design teams perception of the design. This effect is not unlike that of a scientist discovering something that contradicts some well-established principle of the natural world. The most famous example of this is probably Einstein’s Theory of Relativity which changed how we view fundamental laws of physics. This analogy is more instructive than appears. Newtonian mechanics work most of the time. Relativity corrects those cases in which it fails. But, Relativity does not simply tack additional refinements on to Newtonian mechanics. It provides a different point of view and shows how Newtonian mechanics are a special case of this new point of view. Although many bugs found during verification are simple refinements of something that is correct, bugs are found which show the true principles of how a design works and that the initial design was simply an instance of these principles that happened to work most of the time. It is these bugs that provide the real satisfaction to verification engineers.

The Day the Universe Changed

If you have ever taped out a chip and gotten it back in the lab, you have inevitably had the experience of finding a bug which makes you say, “how in the world did we miss this?” When the chip taped out, it was running weeks of regression and random tests without finding any bugs. You reviewed everything and believed that the verification is comprehensive such that, if there are any holes, they are not big ones.

But then, when you get the chip back in the lab, it hits a bug within a second of turning the chip on. When you analyze it, you find that is a very simple case, maybe, a certain bus request in conjunction with a particular configuration bit being set is sufficient to trigger the bug. You think, “how could we have missed something so simple?”

The answer is simple also: the Universe has changed.. It is not unlike the day the Universe changed when Einstein discovered the Relativity principle.What changed that day is the same as what changed the day you got your chip back in the lab. You are looking at the problem with a different mindset.

The mindset you started off with came about when you wrote your initial verification test plan. To understand this, consider how a test plan is created. A test plan basically divides the entire space of possible behavior into different sets. For example, consider the creation of a test plan for a simple memory system. First, the set of all tests can be dividided into two basic types: reads and writes. Next, each of these could be sub-divided into cacheable and uncacheable. Next, each subclass can be divided based on address alignment. We also need to consider sequential behavior. Therefore, each class is further subdivided by being followed by a second request, each of which could be sub-divided based, again, on cacheable/uncacheable, etc.

This test plan can be represented by a tree in which each branch represents a division based on a choice such as read or write, cacheable/noncacheable. This tree grows very quickly and it is up to the verification engineer to decide how deep is sufficient to be considered comprehensive. For anything of any complexity, the number of leaves of the tree is far more than can be tested in a reasonable amount of time. Directed and random testing are ways of sampling the leaves of the tree in a uniform way such that there are no major holes.

A Test Plan For a Simple Memory System

Clearly, bugs can slip through if they occur in one of the leaves that ends up untested. But, if tests are uniformly distributed across leaves, then there should be no major holes. So, for example, if reads don’t work at all, this will be detected because we have sampled on the read side of the tree.

Now suppose we reorder the tree. For example, instead of the order being read/write, cacheable/uncacheable, aligned/unaligned, we reverse the order.

A TestPlan For a Simple Memory System - Reordered

This reordering can cause a uniform distribution of tests to suddenly become non-uniform. Reordering can reveal large holes in the testing. Reordering in this case reveals that the combination of unaligned/uncacheable requests is not tested, something that was not obvious in the original tree.

This is how the Universe changes when we get the chip back in the lab. We find a bug, but we are looking at it with a different ordering of the tree. We are imagining a tree in which the top of the tree is the bus request and next branch is that particular configuration bit and are seeing that whole side of the tree is completely untested. When we think “how did we miss this?”, we are forgetting that back at the beginning, we were looking at a different tree, one in which that configuration bit was near the bottom. Because of this we didn’t notice that, despite the fact that we were sampling the leaf nodes comprehensively, we were never setting this configuration bit in conjunction this particular bus request.

So, to avoid these kinds of bugs in future, you might try, as you near tapeout, to change the Universe by reordering the tree you used to create your testplan.

Languages: Software got it Right, Hardware got it Wrong

In the late Sixties, efforts were underway to define the second generation of programming languages. The first generation of languages, FORTRAN, algol, and cobol, had been in user for almost ten years and enough experience had been built up to allow improved languages to be built. At the time, IBM was the dominant player in programming languages and was in a position to define a language and have it become the defacto standard programming language. The language they designed, called PL/1, was basically a superset of the existing mainstream languages of the time. It had features to support scientific computing, business computing, and systems programming. IBM made PL/1 its flagship programming language and they expected it to become the dominant programming language in the industry.

Meanwhile, at Bell Labs, a programming language called C was being developed. The philosophy behind C was completely opposite to that of PL/1. Instead of being a superset of all existing languages, C was a minimal common subset. C made it easy to create libraries that made up for the lack of features found in other languages. The practice of having a standard library associated with a language started with the C language. Essentially, C is not a language for writing programs, it is a language for writing libraries. Applications are built by putting libraries together. In fact, it is not possible to write a Hello World program in C without using a library (stdio). Today, all modern programming languages still follow this basic philosophy.

The whole Open Source movement is enabled by the philosophy behind C. Imagine if Pl/1 had won the language race and the only way to add new standard features was to add them to the language. The PL/1 compiler was controlled by IBM and the language was not designed to be easily compilable. The software industry would not be as nearly as advanced today if PL/1 had won the language wars.

Contrast this with how hardware design languages have evolved. The analogs of FORTRAN, algol, and cobol in hardware are Verilog and VHDL. These were first generation hardware description languages (HDLs) developed about twenty years ago. Shortly after that, specialized verification languages, such as e and Vera, were introduced that added features useful for verification. Then, along came assertion languages such as PSL and SVA. Today, the hardware design world is migrating to a language called SystemVerilog. Can you guess which path it took? Yup, the PL/1 path. SystemVerilog is a superset of Verilog, Vera, and SVA. The initial release version was version 3.1a. That’s right, it took three major revisions to get it right, then someone decided to add some functionality to get version 3.1. Oh, but wait, that still wasn’t enough, we just had to have a few extra features to get to 3.1a.

And it gets worse. In 35 years, there has been exactly one revision of the C language. SystemVerilog is due for a revision next year after only five years. Verilog has undergone four major revisions in twenty years. The proprietary languages, e and Vera, are changed practically every quarter.

The cost of all this is that it is much harder to innovate in hardware design than it is in software design. At Nusym, we spend 90% of our effort (and money) on language support rather than our core differentiating technology. To illustrate this problem, we have spent dozens of person-years developing Verilog and Vera infrastructure for our tool. By contrast, we had one person spend three months to prototype it on C.

Is there a solution to this problem? Well, there are C-based hardware design languages, such as SystemC. But, using C directly as a hardware design language is trying to fit a square peg into a round hole. Developers and users of SystemC do leverage the ability to easily create libraries, but the goal of this language is to raise the level of abstraction, not create a minimal hardware design/verification language.

It would be interesting to think of what a real equivalent of C for hardware design/verification would be. If there is any interest, I can post my ideas of how to do this and others can contribute. I don’t know if anything would come out of this, but it might be interesting to look at.

The Zen of Design: Specification, Abstraction, and How We Think

To find a Buddha, you have to find your nature.
- Bloodstream Sermon

We perceive the world as an abstraction of reality. When we look at a tree, we see a tree, we don’t see all the individal branches and leaves that make it up. Even if we viewed a tree that way, branches and leaves are still abstractions. Even if it were somehow possible to view a tree as all the individual molecules that make it up, that is still an abstraction. There is no escaping abstraction in how we relate to the world.

A monk asked Dongshan Shouchu, “What is Buddha?” Dongshan said, “Three pounds of flax.”
- Zen Koan

The core of Zen Buddhism is trying to see past the abstractions that our minds crave so desperately in order to make sense of reality. There are very few people who find enlightenment because of the power that abstraction holds over our minds. To the enlightened, those who see reality as it is, questions framed in terms of orthodox abstractions make no sense.

This is the fundamental issue that makes creating anything hard. What we create is real, but how we view it is through the lens of abstraction, and there is no escaping this. We generally believe that we conceive at a high level of abstraction and implement at a low(er) level of abstraction. We strive to increase the level of abstraction because we believe this is the way to improve productivity.

Productivity vs. Abstraction Level: Conventional Wisdom

This turns out not to be entirely true. The closest concrete representation of how we conceive of a design is the written specification. As reviled as it is, this document best represents our intentions at the level of abstraction that we conceive of the design. But, if we look at an average written spec., we find that it encompasses many levels of abstraction. We find:

• textual descriptions that are written at a very high level of abstraction, “it’s a bus that has a processor, memory controller, and I/O controller sitting on it.”
  • structural, behavioral, data, and temporal abstraction.
• Block diagrams of major subunits showing how they are connected.
  • unabstracted structure at a high level, structural abstraction of blocks, behavioral, data and temporal abstraction.
• Equations, code snippets, gate-level diagrams.
  • basically no abstraction.
• truth tables
  • structural abstraction only
• waveforms
  • structural abstraction, behavioral abstraction, unabstracted data, time.

and many other levels of abstraction in between. What this indicates is that as we conceive of a design, we jump around to different levels of abstraction as we consider different aspects of the design. And this holds even if we try to move the level of abstraction up. A new abstraction level just adds to the set of abstraction levels that we can use. What this means is that there is a law of diminishing returns as we move up in abstraction.

Productivity vs. Abstraction: Law of Diminishing Returns

Even more importantly, productivity doesn’t increase monotonically as we raise the level of abstraction. Design is the process of translating from the abstractions that we conceive to those required by the implementation. The greater the gap between these, the lower our productivity in implementing the design.

The conventional wisdom that productivity increases as abstraction increases is based on analyzing just two points on the abstaction continuum. If we plot productivity vs. abstraction level, the only points that we really can count on to improve productivity are those that are close to the natural abstractions at which we conceive.

Productivity vs. Abstraction: Accounting for Translation from Natural to Implementation Abstraction Level

Productivity falls off rapidly as the gap between implementation and conception abstraction levels increases. This is one of the reasons that it has been such a struggle to raise the level of abstraction in design. Finding the right fit that matches how we think at the highest levels of abstraction is exceedingly difficult, but is key if we want to continue to improve productivity by raising the level of abstraction at which we design.

Raising the Level of Abstraction

The obvious solution to the problem of increasing complexity is to raise the level of abstraction at which we design. If we look at the languages used to design software and hardware, the level of abstraction has not increased significantly in over 30 years in software and 20 years in hardware. Why is this if it is such an obvious and compelling solution to the complexity problem?

To understand this, we first must understand why raising the abstraction level increases productivity. In the “Mythical Man-Month”, Brooks concludes that the number of bugs per line of code is constant regardless of what level of abstraction you are working at. Designing at higher levels of abstraction requires less code for the same functionality. Therefore there are fewer bugs per function when coding at a higher level of abstraction, resulting in higher productivity.

So, the goal of abstraction is to reduce the amount of code written to achieve the same level of functionality. The improvement in productivity was dramatic when the move was made from assembly language to the first high-level languages such as FORTRAN and Algol. The procedural programming language, C, became the dominant language in the seventies. C maintained its dominance despite the introduction of languages such as APL and LISP, which did significantly increase the level of abstraction.

Since then, object-oriented programming (OOP) has become the standard programming methodology. But, does OOP represent an increase in the level of abstraction? We can answer this by looking at the four types of abstraction. OOP languages have the same level of structural abstraction as non-OOP procedural languages. The fact that OOP allows member functions and private data doesn’t change the level of structural abstraction, it just allows abstraction errors to be detected at compile time. There is no difference in behavioral abstraction. Both methodologies use the same data abstractions so there is no difference there and temporal abstraction does not really apply to programming languages. Thus, they are at the same level of abstraction.

Have there been any increases in the level of abstraction in programming that have had a significant impact? Scripting languages such as Perl, in which variables are declared implictly, are a form of data abstraction since the implicit declaration hides these details. Garbage collected languages such as Java hide the details of construction/destruction. Templates, such as is found in C++, are another form of data abstraction. All of these innovations have had some effect on improving productivity, but none has had the dramatic impact that the move from assembly to high-level languages had. In summary, there has been no sigificant increase in the level of abstraction of programming languages in over 30 years of software design.

In hardware design, the story is similar. Initially, IC design entry was done by drawing the masks directly. A significant jump in abstraction level occurred when most designs were entered at the gate-level with tools automating the creation of masks. RTL synthesis was the next major jump in abstraction level. Since then, there have been attempts to increase the abstraction level, primarily by trying to do temporal abstraction, but these have not caught on.

We are left with the question of: how have we been able to design much more complex systems with languages that have not increased in their level of abstraction in decades?

The answer is reuse. Today, no complex software or hardware design is built from scratch. We use either standard building blocks or IP blocks, either externally or internally developed. Today, SOCs are designed which consist of a small amount of custom-designed logic which glues together a number of existing IP blocks. The software that runs on these SOCS consists of off-the-shelf operating systems, drivers, and libraries with a few simple applications. Using this methodology, very complex devices can be developed very quickly.

Does this mean that abstraction is not the answer or is not even relevant? No. When we analyze this, we find that reuse is just another way of raising the abstraction level. An IP block or library is an implementation of some behavior. The block itself is a black box; that is, we don’t care how it is implemented. In abstraction terms, when using this block, we have effectively abstracted away all its structure and only care about its behavior. Thus, reuse is a way of dramatically increasing the level of structural abstraction. This is why the abstraction level has not raised in languages in many years. There has been no need because reuse has achieved the necessary results.

Reuse is likely to continue to be the dominant method of raising the abstraction level for the foreseeable future. It is not without its problems, however. First, IP blocks and libraries are generally very inflexible. IP reuse works best when fitting a round peg into a round hole and the benefit/cost ratio drops off rapidly the worse the fit. If the IP block that is available doesn’t quite fit what you want, the temptation is to use it anyway. More often than not, it requires less effort to design a round peg from scratch than try to make a square peg fit, but designers are forced to reuse an ill fitting block anyway.

The other problem with reuse is with verification. From the designer’s viewpoint an IP/library block is a black box. But from a verification standpoint, it is not. First, the IP block is implemented at a low level of abstraction. Therefore, when executing the code for verification purposes, execution occurs at the lowest level of abstraction, making run time a bottleneck. Second, it is usually necessary to exercise all of the code in the IP/library block to ensure correctness. But, this is a very time consuming task because the low level of abstraction means that there are many cases that need to be tested.

In conclusion, from a design standpoint, reuse is the best way today of achieving increasingly higher levels of abstraction. From a verification standpoint, the issues with reuse fuel a desire to find languages that raise the level of abstraction and this is true even at the block level. Because language decisions are primarily driven by design considerations rather than verification, there has been no incentive to increase the level of abstraction in languages, which is why methodologies such as behavioral synthesis and ESL have not caught on.

Executable Specs are not the Answer

In previous posts, I have tried to illustrate that writing complete, unambiguous specifications is hard, if not impossible. A solution that is proposed often but never seems to take hold is to write “executable” specifications. That is, rather than writing text-based specifications, write code that tools can then use to automate the process of producing the design. Today, specification is still done the same way it was twenty years ago, using (electronic) paper and pencil. Why is this? Why do we continue to write text-based specifications despite dramatic increases in complexity and the obvious need for more automation?

I gained some insight into this problem from research carried out by Kanna Shimizu, my colleague at Stanford. In bus protocols such as PCI, the protocol rules are spelled out in the spec. The traditional way of verifying PCI would be to design a PCI controller first then verify that all the properties held for that controller. Kanna’s idea was to code the protocol rules into simple propositions that could be formally verified for consistency.  The advantage of this method is that you did need a design in order to simply verify that the protocol itself had no problems. The types of errors that could be detected were things like conflicts between rules where, by one rule, a signal was supposed to be asserted at some time, while by another one, it was supposed to be deasserted. Suprisingly, a number of such inconsistencies were found in the PCI protocol using this approach.

When I first heard this result, my reaction was that it did not seem right. If there were that many bugs in the PCI protocol, it would not be possible to design any working hardware, yet PCI was a widely using protocol and there was no evidence that these inconsistencies had caused problems.

I didn’t think much about this until Kanna came to me one day with a case she had discovered while working on an Intel processor bus protocol, which happened to be the same one used on the HAL MCU design that I had worked on and, therefore, was familiar with. She had discovered a case where a bus agent could hang the bus forever under certain conditions. I was certain this could not happen, but after analyzing it, found that the protocol did indeed allow such a thing to happen. Again there was a disconnect between what I knew about the protocol and what the spec. actually was saying.

I didn’t think much about it until much later when I realized what the problem was. You would have to go out of your way to design an agent to do this. In fact, it would have to be malicious. Even though the spec. had holes, there is the intent to build a bus that communicates data. This intent was missing from the set of properties being verified. The intent is actually written in the spec., but not in a way that is easy to translate to code. It says, simply, “It’s a bus with the following rules.” The rules were what Kanna verified. While it was easy to code the rules into properties that could automatically verified, coding the requirement “it’s a bus” is consderably more difficult. That one sentence corresponds to potentially thousands of lines of code.

When claims are made about executable specs being better in some: either being more concise, easier to write, less ambiguous, proponents usually point to these easy to code protocol rules, while neglecting the difficulty of translating inherently concise specifications like “it’s a bus”. I believe this is one of the main reasons that executable specifications have not caught on as a better way of specifying complex designs. This will continue into the future, specifications will continue to be text-based because there is no solution on the horizon to this problem.

Abstraction 201: The Good, the Bad, and the Ugly

In my previus post on abstraction, we were left with the question of what makes a valid abstraction. For example, suppose we have a gate-level design of an adder. If we write:

    a = b * c;

we can see that this is a higher level of abstraction, but we would not generally consider it a valid abstraction of an adder. A valid abstraction would be:

    a = b + c;

In general, functions are not as simple as adders and multipliers. We need to define some way of determining whether a design is a valid abstraction of another design.

A valid abstraction is one that preserves some property of the original design.

In RTL, the property of interest is that the abstract function should produce the same output for all inputs, i.e. functionality is preserved. What abstractions are being used in RTL? Let’s look at our adder example. There is structural abstraction because we have eliminated all gates. There is data abstraction from bits to bit vectors. There is temporal abstraction if you consider that the gates have non-zero delays. There is no behavioral abstraction because values are specified for all possible input values. This is a valid abstraction if all output values of the abstraction are the same as the non-abstracted version.

Abstraction works like a less-than-or-equal (<=) operator. Suppose you have designs A and B. If A is an abstraction of B, we can write A <= B. Suppose also that B is an abstraction of C, B <= C. We know that if A <= B and B <= C, then A <= C. This also holds for abstractions. Since abstraction is the hiding of irrelevant detail, you can think of the less than relation as meaning “less detailed than”.

Suppose you have designs D, E, and F, with D<=E and D<=F. We know D is an abstraction of E and F, but what do we know about the relative abstraction levels between E and F? We cannot consider one as being an abstraction of the other even though they are equivalent in some sense. This type of relationship is important in design where D is a specification and E and F are different implementations of the same specification.

The flip side of this is: suppose we have designs P, Q, and R, with P<=R and Q<=R. In other words, P and Q are different abstractions of R. Again there is nothing we can say about the relative abstraction levels between P and Q. This relationship is important in verification where P and Q are different abstract models of the design R.

One last note: it is generally an intractable problem to prove that an abstraction is valid. If you are familiar with equivalence checking, this is basically a method to prove that an abstraction is valid.

Abstraction 101: Making Sense of Complex Systems

Abstraction: the suppression of irrelevant detail

Abstraction is the single most important tool in designing complex systems. There is simply no way to design a million lines of code, whether it be hardware or software, without using multiple levels of abstraction. But, what exactly is abstraction? Most designers know intuitively that, for example, a high-level programming language ,such as C, is a higher level of abstraction than assembly language. Equivalently, in hardware, RTL is a higher level abstraction than gate-level. However, few designers understand the theoretical basis for abstraction. If we believe that the solution to designing ever more complex systems is higher levels of abstraction, then it is important to understand the basic theory of what makes one description of a design more or less abstract than another.

There are four types of abstraction that are used in building hardware/software systems:

• structural
• behavioral
• data
• temporal

Structural Abstraction

Structure refers to the concrete objects that make up a system and their composition For example, the concrete objects that make up a chip are gates. If we write at the RTL level of abstraction:

    a = b + c;

this is describing an adder, but the details of all the gates and their connections is suppressed because they are not relevant at this level of description. In software, the concrete objects being hidden are the CPU registers, program counter, stack pointer, etc. For example, in a high-level language, a function call looks like:

    foo(a,b,c);

The equivalent machine-level code will have instructions to push and pop operands and jump to the specified subroutine. The high-level language hides these irrelevant details.

In general, structural abstraction means specifying functions in terms of inputs and outputs only. Structural abstraction is the most fundamental type of abstraction used in design. It is what enables a designer to enter large designs.

Behavioral Abstraction

Abstracting behavior means not specifying what should happen for certain inputs and/or states. Behavioral abstraction can really only be applied to functions that have been structurally abstracted. Structural abstraction means that a function is specified by a table mapping inputs to outputs. Behavioral abstraction means that the table is not completely filled in.

Behavioral abstraction is not used in design, but is extremely useful, in fact, necessary, in verification. Verification engineers instinctively use behavioral abstraction without even realizing it. A verification environment consists of two parts: a generator that generates input stimulus, and a checker, which checks that the output is correct. It is very common for checkers not to be able to check the output for all possible input values. For example, it is common to find code such as:

    if (response_received)
        if (response_data != expected_data)
           print("ERROR");

The checker only specifies the correct behavior if a response is received. It says nothing about the correct behavior if no response is received.

A directed test is an extreme example of behavioral abstraction. Suppose I write the following directed test for an adder:

    a = 2;
    b = 2;
    dut_adder(out,a,b);
    if (out != 4)
       print("ERROR");

The checker is the last two lines, but it only specifies the output for inputs, a=2, b=2, and says nothing about any other input values.

Data Abstraction

Data abstraction is a mapping from a lower-level type to a higher-level type. The most obvious data abstraction, which is common to both hardware and software, is the mapping of an N-bit vector onto the set of integers. Other data abstractions exist. In hardware, a binary digit is an abstraction of the analog values that exist on a signal. In software, a struct is an abstraction of its individual members.

An interesting fact about data abstraction is that the single most important abstraction, from bit vector to integer, is not actually a valid abstraction. When we treat values as integers, we expect that they obey the rules or arithmetic, however, fixed with bit vectors do not, specifically when operations overflow. To avoid this, a bit width is chosen such that no overflow is possible, or special overflow handling is done.

Temporal Abstraction

This last abstraction type really only applies to hardware. Temporal abstraction means ignoring how long it takes to perform a function. A simple example of this is the zero-delay gate model often used in gate-level simulations. RTL also assumes all combinational operations take zero time.

It is also possible to abstract cycles. For example, a pipelined processor requires several cycles to complete an operation. In verification, it is common to create an unpipelined model of the processor that completes all operations in one cycle. At the end of a sequence of operations, the architecturally visible state of the two models should be the same. This is useful because an unpipelined model is usually much simpler to write than a pipelined one.

The four abstractions described above comprise a basis for the majority of abstractions used in design and verification. That is, any abstraction we are likely to encounter is some combination of the above abstractions. However, we are still left with the question of what is a valid abstraction. I will defer answering this until the next post.

(note: this discussion is based on the paper, “Abstraction Mechanisms for Hardware Verification” by Tom Melham. There is slightly more high-level description of these abstractions in this paper along with a lot of boring technical detail that you probably want to skip.)

A Hero, A Slow-Moving Reptile, and a Pair o’ Clocks

Achilles: I must confess, Mr. T, you got me with that Zeno nonsense. But, trick me no more you will! I have decided to build a clock. A most perfect clock that will measure the exact moment that I pass you in our race.

Tortoise: A great idea, Achilles, but how will you know your clock has the correct time?

Achilles: Simple, I will compare it against the best clock available.

Tortoise: But, how do you that clock is correct?

Achilles: Hmm, I hadn’t thought about that.

Tortoise: I doubt that you can build a clock that will ever tell the right time, because I don’t think you can even describe what a correctly functioning clock looks like.

Achilles: Of course I can! Everybody knows how to tell if a clock is correct or not.

Tortoise: OK, then. Why don’t you give me a specification for your clock and I will build it for you.

Achilles: OK. The clock must have a round face with 60 evenly distributed marks around the edge. It must have the numerals 1-12 imprinted around the circumference evenly spaced every five tick marks with 12 at the top. It must have a big hand and a little hand. The big hand points to the hour and the little hand points to the minute. The hands must point to the correct time at all times.

Tortoise left and returned a while later with clock in hand. Achilles examined it.

Achilles: The hands are pointing to exactly 12PM, but it is now 4PM. Furthermore, there is nothing inside this clock. Its hands don’t move! This doesn’t even come close to meeting the requirements of my specification. Mr. T, I am disappointed. I thought you would do much better.

Tortoise: Not so fast, my friend. I claim my clock is more accurate than any clock you could dream up based on the specification you gave me.

Achilles: I don’t need to dream too hard to think up a clock that actually has hands that, you know, move.

Tortoise: OK, suppose I built a clock that had springs, gears, and an escapement, you know, all the things that clocks have. Let’s say that my clock is accurate to one minute a day. Furthermore, let’s say I set it to the exact correct time based on some reference clock that we agree upon.

Achilles: Now you are talking.

Tortoise: But, my dear Achilles, that clock would be far less accurate than the clock I just built you!

Achilles: How is that possible?

Tortoise: You are right about the clock I built. It doesn’t move. But, it is exactly right twice every day, no more, no less.

Achilles: I see that, but twice per day is nothing to write home about.

Tortoise:Now, let’s analyze your clock. It is accurate at the time I set it, but it immediately becomes inaccurate because it loses one minute per day. It will only be accurate every 720 days. So you see, my clock is actually far more accurate.

Achilles: Ha, Ha. Very funny. You know that all you have to do is make my clock more accurate.

Tortoise: OK, let’s say it only loses one second per day instead of one minute. Then, it will only be accurate one every 43,200 days. I would rather have the clock that is one minute slow.

Achilles: OK, then make it more accurate.

Tortoise: But, this is not possible. No matter how accurate you make it, it is not possible to be exactly synchronous with the reference. You are doomed to failure. And, paradoxically, the closer you get, the less accurate your clock is!

Achilles: I think you are trying to get Zeno back into this conversation.

Tortoise: No, I am just trying to point out that your clock specification is very poor.

Achilles: OK, then how do we fix it?

Tortoise: How do you think we should fix it?

Achilles: We amend it to say that the clock can be off by plus or minus one minute with respect to the correct time.

Tortoise: But my dear Achilles, this just delays the inevitable. Your clock will be correct for the first day by that measure, but will not be accurate again for another 718 days. My clock will be accurate for four minutes every day. My clock is still twice as accurate as yours.

Achilles: Mr. T, you are missing the point. Yes, my clock may become inaccurate after a day, but the user can always reset it to the correct time.

Tortoise: Ah, but that was not part of the specification. Do you want to amend your specification yet again?

Achilles: Yes, I will amend it to say that the user can reset the watch whenever she/he wants.

Tortoise: OK, I will produce a new clock that meets your specification.

Tortoise left and, after a time, came back with a new clock.

Achilles: this clock is no better than your previous clock, Mr. T. It still doesn’t move and there is nothing inside it to make it move.

Tortoise: But, it meets your specification. My first clock had the hands glued to the time 12 O’clock. They could not be moved. This clock has hands that can be moved and therefore, be reset at any time. And, it still has the advantage of being more accurate than your clock when the user decides to not bother with resetting it. On top of that, if the user is not happy with the time displayed by my clock, they can simply set it to to any time they desire.

Achilles: You are trying to use technicalities to avoid admitting you are wrong. You know as well as I do what a clock should look like and how it should behave. The specification I gave you is good enough.

Tortoise: OK, I’ll give you one last chance. If it is that simple, you should be able to give me a specification that gives me no choice but to give you what you want. If I don’t have to think too hard about how to beat you, your specification can’t have been that good and you must concede the point. Do you agree?

Achilles: Alright, I’ll give it one last shot. I am going to add one more condition to my specification. Assume we have a reference clock. It doesn’t matter how accurate it is, as long as its accuracy is acceptable to me. And I am not going to specify that because it doesn’t matter. What I am going to specify is that the clock that you give me must have its hands move at the same rate as the reference clock plus or minus 1/60 of the reference clock’s rate. That is, if we assume that the reference clock’s big hand turns exactly 360 degrees in one hour, your clock’s big hand can be off by one minute per hour. Similarly, the hour hand rate must match the reference clock’s big hand rate with the same accuracy.

Tortoise: Whew, that was quite a mouthful!

Achilles: I will concede that specifying things completely is harder than I thought, but I think this is finally bulletproof. You will have to build me a clock with hands that move, so I am not willing to concede yet the main point that I cannot guarantee that I get the clock I want.

At that, Tortoise left yet again, presently to return bearing two clocks.

Tortoise: First, I will tell you that you used one of the most common copouts when it comes to specification. You specified how it should work rather than its behaivor. The function of a clock is to tell time, not have hands that go round in circles. That is implementation details. However, having said that, here is my clock.

Achilles: It is the same clock! The hands still don’t move. You violated my specification!

Tortoise: No, I didn’t. You specified the hands should move at the same rate as a reference clock. Here is my reference clock. It is an atomic clock with a digital display. It has no hands. Therefore, I am not violating your spec. Yet, atomic clocks are the most accurate in the world, so I think even you would concede that it is accurate enough to meet your specification.

Achilles: OK, I give up. I concede. There appears to be no way to completely specify even something as simple as a clock in a bulletproof way.

Tortoise: You are finally seeing the light, my friend. I suggest you stick to things you are good at, like foot races with slow moving creatures like me.

[with apologies to Lewis Carroll and Douglas Hofstader]

The Intelligent Testbench: This Year’s DFM?

I gave a talk on the intelligent test generation technology we are developing at Nusym at this year’s HLDVT conference. The term “intelligent testbench” has become one of those terms, like DFM, that is so vaguely defined that it can be used to mean anything anybody wants.  So, in the first part of my talk, I defined precisely what we mean when we say that we do intelligent test generation. This was well received so I decided to post this part of the talk here.

The goal of verification is demonstrate that a design works for all possible inputs. A testbench is a software environment that can generate a set of one or more possible inputs. For example:

  begin
     a = $random;
     b = $random;
     c  = $random;
     cmdv = 1'b1;
     @(posedge clk);
     cmdv = 1'b0;
     @(posedge clk);
     ...
   end

In this example, variables a, b, and c are the primary inputs. A testbench can generate a large number of tests. A test corresponds to a particular set of all values for each primary input. Values can be randomized over time, so, more generally, a test consists of sequences of values:

   time 0 1 2 3 4 5 ...
   a =  0 9 5 2 8 5 ...
   b =  9 7 2 4 1 7 ...
   c =  8 1 3 7 2 2 ...

An input sequences defines a point in the input space of the design. The input space is the set of all possible input sequences

In general, the input space is vast. The number of points in the input space exceeds the number of atoms in the universe even for simple designs. So, the question is: how do we verify the design,  given that there is no hope of exercising all points in the input space?

The first simplification that we do is to limit testing to the legal input space.

The legal input space is vastly smaller than the total input space, but is still vast. So, we need some other way of managing the legal input space. This is where coverage comes in.

A coverage point is defined as:  a condition that must be true at some point during testing. For example, a branch condition is defined by the conditions that cause the branch to be taken. A functional coverage point is defined by the set of conditions specifying the functionality to be exercised.

We can define a semantics of coverage points in terms of the input space. Semantically, a coverage point is the set of all points in the input space that hit that coverage point. A coverage point is considered hit if at least one of these tests is executed.

(A coverage model is a set of coverage points, each one specifying a different subset of the input space. A coverage model has the effect of partitioning the input space into disjoint areas (note: this does not mean that coverage points are necessarily disjoint). Generally, the goal is to define coverage points such that exercising one test that hits that coverage point is sufficient to consider all functionality defined by that coverage point to have been tested. In this way, coverage points reduce the vast input space into a tractable set of tests that need to be generated to consider the design fully tested.

In the old days, when designers did their own verification, they would define a test plan, which basically was a set of functional coverage points defining a coverage model. Designers had the most insight into how to partition the input space to maximize the probability of finding bugs.

They would then write directed tests (represented by the white dots in the slide below) to hit all testplan items.

With the advent of the RTL+synthesis, verification was done by separate engineers who did not have the same insight into the design.  Without an good understanding of the design, verification engineers may come up with a completely different test plan.

If they write directed tests, they may get 100% coverage, but end up missing fairly easy to find bugs.

The solution to this problem is random testing, specifically constrained random testing, which tests only within the legal input space. Today, constrained random testing is the dominant pre-silicon verification methodology.

Before the advent of specialized Hardware Verification Languages (HVLs), constraining random values was often done naively. For instance, a naive way to constrain a value to being within a max and min range is as follows:

   task rand_range(min,max)
   begin
      rand_range = $random;
      if (rand_range > max)
         rand_range = max;
      else if (rand_range < min)
         rand_range = min;
   end
   endtask

This would result in a lot of max and min values being generated, but very few in between:

A better solution is constraint-based random testing. Modern HVLs have the ability to specify static constraints on generated values. A built-in constraint solver generates random values that satisfy all constraints.

     rand reg[3:0] x,y;
     rand integer z;
     constraint c1 {
         x < 100;
         y > 5;
         z == x + y;
      }

Static constraints and constraint solving more uniformly distribute values across the legal space, which increases the probability of finding bugs.

We can then combine constraint-based random simulation with a coverage model

The result is of this is that high coverage can be achieved fairly easy, but it can be difficult to get coverage closure, which is defined as achieving 100% reachable coverage. Today, coverage closure is achieved in two ways: 1) directed tests can be written to fill in the missing holes, or 2) the constraints can be biased to try to influence the solver into generating values to fill the holes. Both of these methods are labor intensive, fragile, and require designer insight, which makes coverage closure very painful.

This is where the intelligent testbench comes in. Gary Smith invented this term back in 1998 or thereabouts. He defined it as:

intelligent testbench -
the generation of a testbench from a system-level design description…

This is an intractable problem. Taking an existing testbench and automating the generation of tests to fill coverage holes is a much more tractable problem (although still very difficult, in general). There are two properties that an automated test generator must have to be considered intelligent:

intelligent test generation -

1. it must be able to find a test (settings of random variables or other primary inputs) to hit a specified coverage point with probablity significantly greater than random.
2. it must adapt automatically to design and coverage model changes. That is, a design or testbench change may cause the semantically defined set of tests for a given coverage point to change such that a test that was hitting the coverage point no longer hits it. An intelligent test generation tool will be able to find a new test to hit the coverage point with no other changes required to the testbench.