Wednesday, July 23, 2014

A Quick Look at eUnit

Earlier this month I started a new project. I'm using Specman again, so this means you'll probably see more e related posts in the future.

In a previous post I wrote about how I wanted to improve my coding skills. In particular, I want to produce more reliable code. While I was in SystemVerilog mode, I dabbled with unit testing using the open source SVUnit library.

As luck would have it, in the meantime Cadence released eUnit, a unit testing library for e. I gave it a try developing a new scoreboard. This worked out pretty well since there wasn't any design to code against, but I didn't want to idle while waiting for it. I developed the scoreboard in isolation, based solely on the specification. I didn't get to integrate it yet, as at the time of writing I still didn't get a chance to simulate it together with the design, though I am pretty hopeful.

During this short foray in using eUnit I found different things, some good, some bad. Read on if you want to know more.

eUnit is pretty lightweight when it comes to libraries, as it contains very few lines of code, though in typical Specman fashion, a lot of the internals are built into the tool itself in the form of built-in structs and methods. Getting started with it is pretty easy, as it provides a code generator to quickly get an up and running testing environment. Though the eUnit code generator also provides mockups and other nice features, I still get the feeling however that SVUnit was easier to get into precisely because it generated less code which didn't overwhelm a new user.

The first thing that hit me when running my first test was that there isn't much information displayed to the console. I for one don't like staring at a blank screen; I want my programs to give me feedback and show me that they are actually running. Error messages are suspiciously not printed to the screen, but the output is written to a log file. This is easily fixable with a patch.

Another thing that I found it lacked was displaying the source of error messages. SVUnit has the nice thing of showing which `FAIL_* macro failed (at what location in which file), making it very easy to understand what's going on and what could have cause the error. This can also be fixed, but the solution requires rewriting all of the eu_expect macros (I'm not particularly thrilled about this).

Since we're on the topic of debugging failed tests, a nice feature that eUnit has and SVUnit doesn't is running a single test. This makes analyzing it much easier, by removing the background noise of other tests. There are however slight mismatches when running just one tests versus running the entire test suite. When running just one test, all built-in phase are called, so for example you can see the effect of any code you may have in a check() method (one of the phases that comes after run()), whereas this won't get executed when running all tests.

Another thing I don't like is that there isn't any nice summary at the end of a test suite that shows how many tests were run, how many failed and how many passed. While I have been able to live without it for now, I am looking into how to add this as well as a patch.

One thing that caused me a bit of trouble was testing clocked behavior (or any kind of temporal behavior for that matter). There isn't any clear example in the manual on how to do this. It also doesn't show how to test signal based behavior, though it does mentions that there is a unit called eu_ports_bundle that can be used to connect to any ports inside the feature under test (FUT). Because Specman is decoupled from a simulator, things are a little trickier. I'm not sure how many people know how to fully use Specman standalone (I for one don't really know that well), but information on how to do this is available in other parts of the manual. It would have been nice, though, to have a few mentions in the eUnit section as well. Here are some examples of things you have to look out for:

  • any clock events have to be set to sys.any or, what I prefer, triggered manually
  • there can't be any @sim events present in standalone mode
  • there can't be any ports that are externally bound; they must be bound to mock ports of the opposite direction (this is where the eu_ports_bundle comes in)
  • driving ports is delayed - this means that the effect of a write will be seen on the next tick (this models delta cycles inside a simulator)
  • events and temporal expressions get triggered at the end of a tick, so some checks have to be delayed until after sys.tick_end or to the next tick (the same things happens when using SVUnit due to the SystemVerilog scheduler)

A pleasant surprise was that it's very easy to do code seams, due to the aspect oriented nature of e. This makes it very easy to test methods in isolation. In fact, adding code seams is a bit too easy, which tempted me to test based on values of internal state fields, instead of through the struct's public API. This makes the tests brittle, because they will need fixing should the internal implementation change.

The biggest issue I have with eUnit is that there aren't any setup() or teardown() methods defined for the test suite. Sure, there is a unit_tests_setup() method that is called once at the beginning of the suite, but this isn't enough. I mentioned earlier that we want to test in isolation. Well, isolation also means that tests are completely independent of each other; if they're not independent, then test dependencies may mask bugs because we aren't executing the exact scenario we think we are. The classical case is testing an e unit. Units almost always have state and we have to start each test with a blank state. For structs we could just create a new instance each time, but units can only be created once, at the beginning, during the test phase. We would need to execute some cleaning code before the start of each test, which is why we need a setup() hook. For the moment, the jury's still out on this one as some authors recommend not using setup() or teardown() as it may ruin test readability and it may lead to tests that are more integration tests than unit tests. Some xUnit frameworks have done away with them altogether (for example NUnit). A discussion on this topic may make the topic of a future post, but for now I'm leaning toward wanting them, one of the reasons being the scenario that I described above with the unit. Other programming languages don't have this problem because they don't have the concept of a static hierarchy. SystemVerilog has it as well if you want to test modules, interfaces or checkers, which is why it's neat that SVUnit provides these two hooks.

My impression up to now is that eUnit is not as mature as SVUnit and it shows. I makes me feel like I'm fighting against it sometimes to make it do what I want. Some essential features (for me at least) are missing, but with the right additions it can become more user friendly.

I have a few patches in place and I'm working on a few more. I'll share these in a future post, so consider subscribing if you don't want to miss it.

In the meantime, I'll keep using eUnit to produce code that contains less bugs and to have a safety net in place should I need to make any big changes. If you use e, I recommend that you give it a try and see for yourself!

Tuesday, July 15, 2014

Fun and Games with CRV: The Zebra Puzzle

The Zebra Puzzle is a classic logic puzzle, first published by Life International in 1962. Older versions of it exist and it is also sometimes called Einstein's puzzle. According to "Of Camels and Committees" by Tom Fitzpatrick and Dave Rich, it was used in the early days of constrained random verification (CRV) to show off EDA tools at marketing events.

The puzzle consists of a set of fifteen statements:

  1. There are five houses.
  2. The Englishman lives in the red house.
  3. The Spaniard owns the dog.
  4. Coffee is drunk in the green house.
  5. The Ukrainian drinks tea.
  6. The green house is immediately to the right of the ivory house.
  7. The Old Gold smoker owns snails.
  8. Kools are smoked in the yellow house.
  9. Milk is drunk in the middle house.
  10. The Norwegian lives in the first house.
  11. The man who smokes Chesterfields lives in the house next to the man with the fox.
  12. Kools are smoked in the house next to the house where the horse is kept.
  13. The Lucky Strike smoker drinks orange juice.
  14. The Japanese smokes Parliaments.
  15. The Norwegian lives next to the blue house.

(Life International, 1962)

Based on these statements, the reader is asked to deduce who drinks water and who owns the zebra.

Deductive reasoning makes my head hurt, so I want to have the computer solve it for me. As with Sudoku, we don't want to build an algorithm that finds the solution. This is exactly the kind of problem constraint programming is perfect for: expressing logical relations between variables. Let's dive right in!

The first step is to formalize the problem. We know that the houses are of different colors, contain people of specific nationalities that drink some things, smoke some cigarette brands and own some pets, again all different. We will model all of these as enumerations.

First let's handle the house colors:

typedef enum { RED, GREEN, IVORY, YELLOW, BLUE } color_e;

Second, nationality is mentioned:

typedef enum { ENGLISH, SPANISH, UKRANIAN, NORWEGIAN, JAPANESE } nationality_e;

Third, here are the pets:

typedef enum { DOG, SNAILS, FOX, HORSE, ZEBRA } pet_e;

Fourth, this is what the inhabitants like to drink:

typedef enum { COFFEE, TEA, MILK, ORANGE_JUICE, WATER } drink_e;

And fifth, this is what they like to smoke:

typedef enum { OLD_GOLD, KOOL, CHESTERFIELD, LUCKY_STRIKE, PARLIAMENT } cigarettes_e;

The easiest way to model the houses is by using a struct:

typedef struct {
  rand color_e       color;
  rand nationality_e nationality;
  rand pet_e         pet;
  rand drink_e       drink;
  rand cigarettes_e  cigarettes;
} house_t;

The second step is to write the starting statements as constraints. We can't know on which instance of the house to apply a specific statement; this is what we want to find out. The statements must apply to all houses (with the exception of a few that apply to a specific house), which means that for the most part we will write foreach constraints.

Statement 1 just says that there are five houses. This isn't a constraint per se, but more of a modeling topic. We model this by declaring our neighborhood as a vector of houses that contains five elements:

class zebra_puzzle_solver;
  rand house_t house[5];
  
  // ...
endclass

Statement 2 says that the Englishman lives in the red house:

constraint statement2_c {
  foreach (house[i])
    house[i].nationality == ENGLISH -> house[i].color == RED;
}

From statement 3 we learn that the Spaniard owns the dog:

constraint statement3_c {
  foreach (house[i])
    house[i].nationality == SPANISH -> house[i].pet == DOG;
}

Statement 4 tells us that the person who drinks coffee lives in the green house:

constraint statement4_c {
  foreach (house[i])
    house[i].drink == COFFEE -> house[i].color == GREEN;
}

We know from statement 5 that the Ukrainian drinks tea:

constraint statement5_c {
  foreach (house[i])
    house[i].nationality == UKRANIAN -> house[i].drink == TEA;
}

Statement 6 is a bit tricky. It tells us that the green house is immediately to the right of the ivory house. This means that we have to take care in our foreach constraint that we don't end up outside the neighborhood (i.e. access a non-existing location in our vector):

constraint statement6_c {
  foreach (house[i])
    if (i < 4)  // make sure we don't go out of bounds
      house[i].color == IVORY -> house[i+1].color == GREEN;
}

Moving on, statement 7 informs us that the Old Gold smoker owns snails:

constraint statement7_c {
  foreach (house[i])
    house[i].cigarettes == OLD_GOLD -> house[i].pet == SNAILS;
}

At the same time, as per statement 8, the Kools smoker lives in the yellow house:

constraint statement8_c {
  foreach (house[i])
    house[i].cigarettes == KOOL -> house[i].color == YELLOW;
}

Statement 9 only applies to the middle house and says that milk is drunk there:

constraint statement9_c {
  house[2].drink == MILK; // no. 2 is the middle house
}

Statement 10 also only applies to only one house, the first one, and tells us that the Norwegian lives there:

constraint statement10_c {
  house[0].nationality == NORWEGIAN;  // no. 0 is the first house
}

Statement 11 becomes tricky again. From it we know that the Chesterfield smoker lives next to the fox owner. "Next to" means either to the left or to the right. As with statement 6, we have to make sure we don't fall off of the neighborhood map. We have three cases to consider. If he lives in the first house (the leftmost) then this means his neighbor to the right owns the fox. Likewise, if he lives in the last house (the rightmost), this means that his neighbor to the left owns the fox. However, if he lives in one of the middle houses, then either one of his neighbors could potentially own the fox. Expressed as constraints, this would look like this:

constraint statement11_c {
  house[0].cigarettes == CHESTERFIELD -> house[1].pet == FOX;
  house[4].cigarettes == CHESTERFIELD -> house[3].pet == FOX;
  
  foreach (house[i])
    if (i > 0 && i < 4)
      house[i].cigarettes == CHESTERFIELD ->
        (house[i-1].pet == FOX) || house[i+1].pet == FOX);
}

Statement 12 is similar to the previous one, but it tells us that the Kools smoker lives next to the horse owner. The constraint looks very much like the one before:

constraint statement12_c {
  house[0].cigarettes == KOOL -> house[1].pet == HORSE;
  house[4].cigarettes == KOOL -> house[3].pet == HORSE;
  
  foreach (house[i])
    if (i > 0 && i < 4)
      house[i].cigarettes == KOOL ->
        (house[i-1].pet == HORSE) || house[i+1].pet == HORSE);
}

Statement 13 is simple again and informs us that the Lucky Strike smoker drinks orange juice:

constraint statement13_c {
  foreach (house[i])
    house[i].cigarettes == LUCKY_STRIKE -> house[i].drink == ORANGE_JUICE;
}

Similarly, from statement 14 we find out that the Japanese smokes Parliament:

constraint statement14_c {
  foreach (house[i])
    house[i].nationality == JAPANESE -> house[i].cigarettes == PARLIAMENT;
}

Statement 15 is again more involved, finally telling us that the Norwegian lives next to the blue house. We could type a bit less here (because we know the Norwegian lives in the first house) and directly say that the second house is blue, but I want the constraint solver to work hard for its money. Let's just write the constraint as we did for statements 11 and 12:

constraint statement15_c {
  house[0].nationality == NORWEGIAN -> house[1].color == BLUE;
  house[4].nationality == NORWEGIAN -> house[3].color == BLUE;
  
  foreach (house[i])
    if (i > 0 && i < 4)
      house[i].nationality == NORWEGIAN ->
        (house[i-1].color == BLUE) || house[i+1].color == BLUE);
}

Ideally, the third step should be to just run our code and find the solution, but as always nothing works right on the first try. I kept getting some very weird results at first, that were completely off. The reason for this is that we used implication constraints. Saying that being English implies you live in the red house is not enough. We don't know the order in which fields are assigned by the solver, so we also need to say that if you live in the red house, then you are English. Luckily, SystemVerilog provides us the equivalence operator <->. Here's how the constraint for statement 2 should really look like:

constraint statement2_c {
  foreach (house[i])
    house[i].nationality == ENGLISH <-> house[i].color == RED;
}

For brevity I won't show all of the fixed constraints here.

Even with the equivalence constraints in place, I got three Japanese and two Norwegians in my neighborhood. I looked at each of the constraints and they all applied (though some vacuously). The last one, however (the one I chose to write long), didn't, but only because the compiler had no problem with me saying that the Norwegian lives next to the house with the color fox (you won't see it in the code I posted as I already fixed that).  Surprisingly, there was no error, no warning, no nothing, even though such a conversion is illegal. Let this be a lesson to us for the future: some simulators are a bit more relaxed with their interpretation of the SystemVerilog standard and we need to make sure to enforce strict LRM compliance, otherwise we're going to have a bad time debugging implicit type conversions.

Even after fixing the foxy house, I still got a neighborhood full of Norwegians with all blue houses. Three of them smoked Chesterfields, while the other two liked Old Gold (and had snails as well, of course). Most drank milk and only one drank water. Also, the middle guy had the zebra. You get the idea, something was still missing. Well, the wording of the puzzle is important. It always said "the Norwegian..." or "the Lucky Strike smoker..." which means there is only one Norwegian and only one Lucky Strike smoker. The original article in Life International adds this fact as a clarification: "[It] must be added that each of the five houses is painted a different color, and their inhabitants are of different national extractions, own different pets, drink different beverages and smoke different brands of American cigarets [sic]."

To reflect this, we just need to add a uniqueness constraint. Unfortunately, because constraint operands have to be of integral types, we can't just say that the houses are unique. We have to declare auxiliary lists for nationalities, pets, etc. and constrain these to be unique. In e we could have accessed these directly, without the need for extra fields, but here is how it looks like in SystemVerilog:

local rand color_e       color[5];
local rand nationality_e nationality[5];
local rand pet_e         pet[5];
local rand drink_e       drink[5];
local rand cigarettes_e  cigarettes[5];

constraint create_sublists_c {
  foreach (house[i]) (
    color[i] == house[i].color &&
    nationality[i] == house[i].nationality &&
    pet[i] == house[i].pet &&
    drink[i] == house[i].drink &&
    cigarettes[i] == house[i].cigarettes
  ); 
}

constraint all_unique_c {
  unique { color };
  unique { nationality };
  unique { pet };
  unique { drink };
  unique { cigarettes };
}

Even with the uniqueness constraint in place, we still get a contradiction error. This one took me a bit to figure out. The problem is with our "complicated" constraints (the ones for statements 11, 12 and 15). Here is how the constraint for statement 11 looks after swapping implication for equivalence, in particular the constraint for the middle houses:

constraint statement11_c {
  foreach (house[i])
    if (i > 0 && i < 4)
      house[i].cigarettes == CHESTERFIELD <->
        (house[i-1].pet == FOX) || house[i+1].pet == FOX);
}

The mistake is with respect to the relation between the equivalence and logical operators. Let's take a step back and let me explain what I mean by that. For the case of implication, the following is true:

a -> (b || c) == (a -> b) || (a -> c)

The same is however not true for equivalence:

a <-> (b || c) != (a <-> b) || (a <-> c)

For all of you math enthusiasts, this means that equivalence is not distributive over disjunction. If you write the truth tables you will see that this is the case. What we're interested in is the right hand side of the expression (the neighbor on the left smokes Chesterfields or the neighbor on the right smokes Chesterfields), but what we have implemented is the expression on the left hand side. Now that we know this, we can fix the constraints (shown for statement 11):

constraint statement11_c {
  foreach (house[i])
    if (i > 0 && i < 4)
      (house[i].cigarettes == CHESTERFIELD <-> house[i-1].pet == FOX) ||
      (house[i].cigarettes == CHESTERFIELD <-> house[i+1].pet == FOX);
}

Technically, more correct would have been to say A <-> B xor A <-> C, because the neighbor can only be either on the left or on the right. This might speed things up a bit and might also make it so that uniqueness constraints are not needed. Unfortunately, we can't try this out as there is no logical exclusive "or" operator in SystemVerilog.

After fixing this last thing, everything now works! We find out that the Norwegian drinks water and that the Japanese owns the zebra. Much easier than deductive reasoning...

I hope you enjoyed this post. It was a lot of fun to make and I learned a bit more about the constraint capabilities of SystemVerilog. If you want to play with the solver, you can download it from SourceForge.

Stay tuned for more fun and games with CRV!

Sunday, July 6, 2014

The Not So Comprehensive Guide to SystemVerilog Array Constraints

A few weeks back, during a late evening, I was writing some SystemVerilog code that was declaring constraints on arrays. My brain was already powering down and I just wanted to search the net for a code snippet I could quickly copy and adapt. I couldn't find anything, so that inspired me to write this post, to save some snippets for posterity (and for search engines).

The problem I was facing was how to constrain the last element of a dynamic array to have a specific value. I didn't know the exact size of the array, so I tried the naïve approach:

rand int some_dynamic_array[];

constraint last_elem_c {
  some_dynamic_array[some_dynamic_array.size() - 1] == 5;
}

Turns out that using size(), or any other random value, as an index is not allowed. Some programming languages provide a short hand for the last item in the array, e.g. Python allows us to get the last element of a list by doing list[-1]. This isn't possible in SystemVerilog, so what we want to do is going to take a bit more code:

constraint last_elem_c {
  foreach(some_dynamic_array[i])
    if (i == some_dynamic_array.size() - 1)
      some_dynamic_array[i] == 5;
}

Let's take a look at a few more array constraints that could be useful. What we might want is to constrain an array to contain a specific element. This is easily done using the inside operator:

constraint contains_c {
  2 inside { some_dynamic_array };
}

Our array will now contain the value 2, but we don't care at what exact index. The complementary of this is that we want an array to not contain a specific element. This is simply the negation of the above expression:

constraint not_contains_c {
  !(-3 inside { some_dynamic_array });
}

The LRM also shows an example of how to achieve this using the unique operator, but that requires more lines of code and also makes the elements of the array unique. And speaking of unique elements...

Another constraint we may want to place on array is that all of its elements are unique. This can be done using the unique operator:

constraint all_elems_unique_c {
  unique { some_dynamic_array };
}

This is short and sweet, but the unique operator is something that was just recently added in the SystemVerilog 2012 standard. Some of you may want to stay away from it for now (either because of you are using legacy simulators or because you don't want to be early adopters). We can write this constraint in 2009 syntax, but it's going to need a few more lines of code:

constraint all_elems_unique_c {
  foreach (some_dynamic_array[i])
    foreach (some_dynamic_array[j])
      if (i != j)
        some_dynamic_array[i] != some_dynamic_array[j];
}

This old school snippet may remind you of the days when you just started out with programming, when you used double traversal to compare two arrays.

A nifty feature when it comes to array constraints (and not only) is to be able to write multiple constraint expressions under a single foreach (or as in this case if) block:

constraint using_constraint_sets_c {
  foreach (some_dynamic_array[i])
    if (i == 1) {
      some_dynamic_array[i] % 2 == 1;
      some_dynamic_array[i] != 1;
    }
}

The snippet above constrains the second element to be odd, but at the same time to not be 1. The way I was writing this a little while back, before knowing that I can group constraints with brackets, resulted in very long expressions and could potentially result in issues with operator precedence:

constraint using_constraint_sets_c {
  foreach (some_dynamic_array[i])
    if (i == 1)
      some_dynamic_array[i] % 2 == 1 && some_dynamic_array[i] != 1;
}

What we may also want to constrain is that two arrays are equal. If our arrays are packed, then we can use the == operator:

rand bit[9:0][3:0] some_packed_array, some_other_packed_array;

constraint packed_arrays_equal_c {
  some_packed_array == some_other_packed_array;
}

Using the == operator is not possible for unpacked arrays, as they are not integral expressions. In this case we have to explicitly constrain each element via a foreach block:

rand bit[3:0] some_unpacked_array[10], some_other_unpacked_array[10];

constraint unpacked_arrays_equal_c {
  foreach (some_other_unpacked_array[i])
    some_other_unpacked_array[i] == some_unpacked_array[i];
}

Before closing, let's have a look at an example of how we can use some of these constraints together: generating a permutation of a one-dimensional array. For simplicity, I'll assume that the source array's elements are unique.

rand int some_other_dynamic_array[];

// assumes the source array has unique elements
constraint is_a_permutation_c {
  // arrays must have the same size
  some_other_dynamic_array.size() == some_dynamic_array.size();

  // all elements in the source array must be in the destination array
  foreach (some_other_dynamic_array[i])
    some_other_dynamic_array[i] inside { some_dynamic_array };

  // all elements in the destination array must be unique
  unique { some_other_dynamic_array };

  // "inside" operator is bidirectional
  // - if we don't want to change the src array, we have to solve it before
  solve some_dynamic_array before some_other_dynamic_array;
}

The first requirement for a permutation is to be of the same size as the original array. Second, each of the elements in our permutation must be contained inside the source array. This doesn't guarantee, however, that all of the elements of our original array will be present in the "permutation"; e.g. if the source array is { 1, 2, 3 }, then the "permutation" could just as well be { 2, 2, 2 }. Because we assumed that our source array contains only unique elements, then by constraining our "permutation" to also contain only unique elements, we will make sure that each element in the first array will be present in the second array. Because the inside operator is bidirectional, any constraints we add on the permuted array will also potentially propagate to the source array. If we don't want this to happen, we can also force unidirectionality by using a solve ... before ... block.

These are the most interesting array constraints I could think of for the moment. I will gladly update the list if more come up. If you have tried implementing any tricky array constraint, but couldn't quite get it to work, let me know in the comments section. If we put our heads together then maybe we can find a way to solve it.