Wednesday, December 9, 2015

Fun and Games with CRV: Einstein's Puzzle (Revisited)

Two weeks ago, Aurelian from AMIQ published a post on how to solve the so-called Einstein's puzzle using e. At the end, he challenged us readers to try and improve on his solution. Not being one to shy away, I rolled up my sleeves and got to work.

He started out by defining a struct to hold the information about a resident:

<'
struct resident {
  nationality : nationality_t;
  house_color : house_color_t;
  cigarette : cigarette_t;
  pet : pet_t;
  drink : drink_t;
};
'>

He gave up on this idea after he tried to constrain the residents to have unique nationalities, house colors, etc. Here's what he tried:

<'
struct neighborhood {
  keep residents.nationality.is_a_permutation(all_values(nationality_t));
  // ...
};
'>

This looks reasonable, right? Why didn't it work then? That's because even though residents.nationality returns a list of all residents' nationalities, it isn't generative. I didn't find anything normative in the Language Reference or the Generation User Guide that explicitly states this, but this seems to be the case. The proper way of ensuring all nationalities are unique is to use the all_different(...) pseudo-method:

<'
struct neighborhood {
  keep residents.all_different(it.nationality);
  // ...
};
'>

Now that we've got our infrastructure set up, it's time to start converting the 15 facts into code. There are three types of facts given to us. The first type only involves individual residents. For example, we know that the one living in the red house is English. This can be represented as a constraint inside the resident class itself:

<'
extend resident {
  keep nationality == ENGLISH => house_color == RED; // #1
};
'>

There are seven more such constraints, but I won't show them here, since they are very similar to this one. You can find the complete code on SourceForge.

The second type of fact we know about our residents describes a characteristic of the resident living in a particular house. For example, we know that the resident in the first house is Norwegian. This kind of constraint needs to be added to the neighborhood:

<'
extend neighborhood {
  keep residents[0].nationality == NORWEGIAN; // #9
};
'>

The third type of fact gives hints about residents in relation to their neighbors. For example, we know that the green house is located to the left of the white house. Here we need to loop over all elements of the list. Per definition, the green house can't be the last one in the list, because then it wouldn't be located to the left of anything:

<'
extend neighborhood {
  // #4
  keep for each (resident) in residents {
    resident.house_color == GREEN =>
      index < 4 and residents[index+1].house_color == WHITE;
  };
};
'>

The fact that the Blend smoker lives next to the cat owner is a bit more involved, but it follows the same principle. This means that the Blend smoker is either located to the left (which is the same situation as before) or is located to the right, in which case the respective house can't be the first one:

<'
extend neighborhood {
  // #10
  keep for each (resident) in residents {
    resident.cigarette == BLEND =>
      index < 4 and residents[index+1].pet == CAT or
        index > 0 and residents[index-1].pet == CAT;
  };
};
'>

Since we have three more such constraints to write, we could save ourselves some typing by defining a macro:

<'
define <neighbors'statement> "<first'exp> neighbors <second'exp>" as {
  extend neighborhood {
    keep for each (resident) in residents {
      resident.<first'exp> =>
        index < 4 and residents[index+1].<second'exp> or
          index > 0 and residents[index-1].<second'exp>;
    };
  };
};
'>

The macro "call" would look like this:

<'
cigarette == BLEND neighbors pet == CAT; // #10
'>

With these three types of constraints we can model all fifteen facts and solve the puzzle. I was pretty surprised that it worked the first time and gave the right solution - the German keeps the fish. When I solved the zebra puzzle in SystemVerilog (which is essentially the same puzzle as this one, just with slightly different facts about the residents) I ran into problems because I used the implication operator. Basically, saying that the English resident lives in the red house doesn't just mean that nationality == ENGLISH => house_color == RED, but that at the same time house_color == RED => nationality == ENGLISH. There isn't any equivalence operator (also called double implication) in e, but this can be expressed using the equality operator, "==":

<'
extend resident {
  keep (nationality == ENGLISH) == (house_color == RED); // #1
};
'>

I've shown you my solution. Now it's time to pass the baton to you and challenge you to improve it even more.

Sunday, December 6, 2015

Packages, Class Names and UVM

Some time ago I wrote a post that challenged some of the established coding conventions of modern SystemVerilog. In particular, I expressed my displeasure with the fact that all training material from EDA companies, tutorial sites and other learning resources state that packages should always contain a "_pkg" suffix appended to the package name and that all identifiers in the package (class/function/constant names) should contain the package name as a prefix. I attribute this to the significant C legacy that exists in our field, as the C language doesn't have any construct for packaging code.

I've started to drop the package name prefix from any new code I'm writing, both for the blog (as you might have noticed), but also at work. By seeing how this works out in "real life", I've noticed some pitfalls. The first is, of course, that people will come and complain that this doesn't satisfy the commandments given to us by the lords of SystemVerilog. I've yet to hear any compelling argument against dropping package names from classes. Moreover, the only arguments I've ever heard were "this isn't how everybody else is doing it" and my favorite "we've always done it this way". Until someone can come up with something better, I'll continue to believe that the much larger communities of C++, Java and other modern programming languages are onto something.

Now let's look at what happens when applying this idea when also using UVM. Normally, we'd have a package that contains a class definition. Inside this class, we'd use the utils macro to reduce the amount of boilerplate code needed to make it a productive member of a UVM environment:

package some_package;
  // ...

  class some_class extends uvm_object;
    // ...

    `uvm_object_utils(some_class)
  endclass

endpackage

If we'd try to print an object of this class, we'd get something like this:

---------------------------------
Name      Type        Size  Value
---------------------------------
some_obj  some_class  -     @338
---------------------------------

The type column would rightly show some_class, but that isn't very informative, as some colleague pointed out. Having the package name as a prefix made it instantly possible to identify the scope where the class is defined. This is particularly helpful when classes from different packages use the same name.

And speaking of using the same name for multiple classes... Let's say that we also have another package that defines a some_class type:

package some_other_package;
  // ...

  class some_class extends uvm_object;
    // ...

    `uvm_object_utils(some_class)
  endclass

endpackage

Because the classes have the same name, when they get registered with the factory, we'll get the following warning:

UVM_WARNING @ 0: reporter [TPRGED] Type name 'some_class' already registered with factory. No 
string-based lookup support for multiple types with the same type name.

Aside from disabling the set_*_override_by_name(...) functions (which I anyway wouldn't recommend using), it doesn't do anything else. Everything else still works just fine. Nevertheless, extra warning message aren't nice, because they clutter the log file. For one or two classes it might be ok, but try working with multiple UVC packages that each define a driver, monitor, agent, etc. class... I tried to come up with a way to disable the warning, but I wasn't successful.

I've thought about these problems on multiple occasions, went down a few dead ends and dreamt up some silly solutions. I kept thinking that the problem was with UVM, that the macros were to restrictive because they don't consider the class's parent package. Then I realized that the name that gets displayed by the print(...) function and that gets registered with the factory is merely the one supplied as the macro argument. Instead of using just the class name, we can just as well use its fully qualified name, that includes the package name and the scope operator, "::". This means we can change our code to this:

  class some_class extends uvm_object;
    // ...

    `uvm_object_utils(some_package::some_class)
  endclass

Now we won't get any more warning from the UVM factory and the text displayed by print(...) will make it clear which class we're dealing with:

-----------------------------------------------
Name      Type                      Size  Value
-----------------------------------------------
some_obj  some_package::some_class  -     @338
-----------------------------------------------

With this small tweak, it's possible to drop the package prefix from classes while still getting nice prints in UVM and avoiding any warnings from the factory. Now we have two reasons less against shortening our class names.