September 27, 2011

What the Heck is FEC?

Focused Expression Coverage Explained

by Ray Salemi

When you think about it, simulating your FPGA is a lot like exercising on a treadmill.  You do both of them because you want to avoid bad consequences.  Some people seem to like doing it, though you might not see it that way.  And you may or may not yet have seen the positive consequences in your life.

In both the case of the treadmill and of FPGA simulation, the biggest question in your mind is "When can I stop?"  This is a tougher question for simulation because you don't have a sadistic trainer who makes you keep going.  In fact, you probably have an impatient manager telling you to stop.  So what we really need is an objective way of knowing when to stop.

One approach is to use the same technique we use when we throw down lawn fertilizer.  You do it until you're bored or out of fertilizer and say, "Yeah.  That should cover it." 

A better approach would be to make a list of things we want to test and, assuming we haven't forgotten anything, we stop when we've tested those things.  This is a good technique and should not be discarded.

The most objective approach would be to take advantage of the code coverage tools built into most simulators to see when we've actually simulated every piece of our RTL.  Code coverage answers this question using five different kinds of measurement that can be summed up in a simple (and useful) sentence:

Some Beer For Extra Courage

Like that old sentence that reminded us of our resistor colors, this mnemonic reminds us of the five kinds of code coverage:

  • Statement—Did we cover every statement?
  • Branch—Did we cover every IF branch and CASE entry?
  • Finite State Machine—Did we cover all states and transitions?
  • Expression—Did we fully test our single-bit expressions
  • Condition—Did we test all the conditions in our IF statements? 

We use these five kinds of code coverage to convince ourselves and others that we've fully simulated our design–that we've crammed stimulus into all RTL's nooks and crannies, and that we're confident that the thing works as expected.  Our coverage report gives us a clear picture of what we've simulated, and more importantly what we've missed.

A coverage report is easy to understand when it comes to statement, branch and FSM coverage.  We know what it means to have simulated a statement of code and what it means to have touched all the cases in our case statements.  The idea of simulating, or not simulating, a state or transition in a state machine translates into a specific set of steps that we need to create to drive our state machine into all its possible behaviors.

Things are not as simple when it comes to expression and condition coverage. Conditions and single-bit expressions define clouds of logic that take a set of single-bit inputs and generate a single bit output.  What does it mean to fully simulate one of these expressions?

It doesn't mean that we've simulated the line of code that defined the equation.  That's statement coverage.  Instead, it means that we've created stimulus that is so complete that it would catch a synthesis logic error.   It means that we've fully simulated every interesting set of inputs.

The simple way to approach this problem is to make sure that we've simulated every possible set of inputs–if there are three inputs we need to simulate eight possible combinations.  There are three problems with this simple-minded approach:

  1. There may be illegal input combinations that we'll never see.
  2. Some of the input combinations may be redundant.
  3. The number of combinations increases exponentially with the number of input bits.

We need a smarter way of choosing our required input combinations, and Focused Expression Coverage (FEC) delivers it.  FEC is the reigning champion of expression and condition coverage.  All the major simulators provide FEC output.  In addition, Focused Expression Coverage makes sense to auditing authorities who are accustomed to Modified Condition/Decision Coverage (MCDC), a standard that is used in the software auditing world.

 

Focused Expression Coverage breaks the problem of expression coverage down into an examination of individual input signals.  It looks at each input signal and asks three questions:

  1. What is the list of input combinations in which setting this signal to a 0 would affect the output?
  2. What is the list of input combinations in which setting this signal to a 1 would affect the output?
  3. Have we tested all these combinations?

For example, in a simple two input AND equation, setting an input to 1 would only affect the output if the other input were also set to 1. The same is true for setting an input to 0, the effect will only be seen if the other signal is set to a one.   To fully test the AND, you need to set the input signal to 0 and 1 while holding the to a 1.  Let's examine FEC with an example design: the TinyCache.

The TinyCache is a 16-word, single-level, cache.  It uses the bottom four address bits to access a tag ram and cache data.  When you read from the TinyCache, it stores the data in the cache ram, and stores the associated address in the tag ram.  Then when you read from that same memory location, it checks to see if the tag ram contains the address you're requesting.  If they match, you have a cache hit, otherwise you have a cache miss.

We reset the TinyCache with an invalidation register that has one bit per cache entry.  We set all the bits in the register to 1 upon reset, so that we force a cache miss.

The TinyCache only checks for a cache miss when you do a read operation.  It uses the following equation: 

Screen_Shot_2011-09-26_at_1.36.27_PM.png

The equation is of the form (A or B) and C.  We need to write simulation stimulus that fully tests this equation as well as the rest of the RAM. 

Here is our test plan:

  1. Reset the cache.
  2. Read twice from each location to test the cache hit functionality.  The first read will be a miss and the second read will be a hit.
  3. Write to each location and read from it to test the write functionality.
  4. Read from each location in the cache twice, then read from a location 16 words higher in the memory to force a cache miss, finally read from the original location to force another cache miss.

This test plan should fully test the TinyCache.  Let's see what happens when we run this stimulus through Mentor's Questa Simulator (click to enlarge):

simulator.png

Clearly we have a miss.  We haven't fully tested the equation input from the invalid register.  Let's examine the report to understand what we've missed. 

The report has two sections.  The top section shows us the inputs to our equation.  Remember this is of the form (A or B) and C.  The tag ram check is A.  The invalid-bit check is B, and the read signal is C. 

The second section examines each of these inputs when they are set to 0 and set to 1, and displays the conditions under which those values can make a difference to the output.  For example, Row 1 shows us that a 0 from the tag_ram equation can only affect the output if the invalid register is also set to 0 (because of the OR function). 

Rows 5 and 6 show us the two input conditions needed to fully cover the read signal.  That signal only affects the output if either the tag_ram input is set to 1 or the invalid bit input is set to 1 while the tag_ram input is 0.  We've simulated all these cases.

Row 4, on the other hand, is a miss.  We've never delivered stimulus that will show us whether setting the invalid signal to a 1 will affect the output.  This is because we've never seen a case where the tag_ram equation returns a 0 while the invalid bit is returning a 1.  How is this possible given our test plan?

We must convert the missed input combination into a description of the cache behavior.  The equation says that we've never tested the case where we would have had a cache hit but for the fact that the invalid bit was set.

We see this is true when we look at our test plan.  We only reset the cache once, and so there was never a case where the cache contained good data that had been invalidated by a reset.  This is a hole in our testing.

To paraphrase Neal Stephenson, getting the last bit of code coverage completed is like trying to get the last bit of water out of an old tire.  This especially becomes true when one looks at expression and condition coverage.  However, it is worth the effort because these forms of coverage can highlight subtle oversights in our verification plan, oversights that could come back to bite us in the lab or even at the customer site.  

Turning on Focused Expression Coverage is well worth the effort.

 

simulator.png

Comments:


raysalemi

Total Posts: 42
Joined: Feb 2010

Posted on September 27, 2011 at 2:08 PM

Have you had a chance to try the condition and expression coverage tools in your simulator?
You must be logged in to leave a reply. Login »

Related Articles

Going Vertical

Ecosystem for Interposer-based Design?

by Kevin Morris

Weve talked a lot lately in these pages about the impending demise of Moores Law. Consensus is that, somewhere around the half-century mark,...

Theres a Processor in My FPGA!

Hey, Theres LUT Fabric in my SoC!

by Kevin Morris

The idea of processors and FPGAs working together is exactly as old as the idea of FPGAs. Perhaps older, in fact, because even the prehistoric...

Optimization Moves Up a Level

Mentors RealTime Designer Rises to RTL

by Bryon Moyer

There are a lot of reasons why we can create so much circuitry on a single piece of silicon. Obvious ones include hard work developing...

Superstar

The Truth About Engineering Talent

by Kevin Morris

People who are sports fans often watch in amazement when a superstar athlete gets a contract worth tens of millions of dollars. Why, they ask, ...

Middle Child Syndrome

Is 20nm the Forgotten FPGA Node?

by Kevin Morris

28nm is a calm, mature node. Sure, everyone was excited when it was the first to reach modern price, performance, and cost levels. We applauded...

  • Feature Articles RSS
  • Comment on this article
  • Print this article

Login Required

In order to view this resource, you must log in to our site. Please sign in now.

If you don't already have an acount with us, registering is free and quick. Register now.

Sign In    Register