Cooking at Home or Eating Out? - The Pros and Cons of Homegrown VIP

By now, we're all pretty much convinced that reuse is essential in the semiconductor industry. Gone are the days when we built everything from scratch an re-invented the wheel on each project. Today, to build a new SoC we stitch together multiple blocks that we've already used on previous projects, maybe tweaking them a little, while only designing those new things that will help our product differentiate itself from the competition.

The same principle also holds for the testbenches we develop for those blocks and SoCs. It makes sense, right? If we have a block with an AHB interface, do we really need to write a verification component that can drive the AHB protocol for each new iteration of that block? What if we have multiple blocks that communicate through AHB? Why couldn't the same verification component be used within all of those testbenches? The industry recognized this and some time ago new languages appeared that borrowed from general purpose programming languages to make it easier to develop reusable verification intellectual property (VIP).

These days, we have two choices when considering VIP. We can either buy commercial products from established vendors or we can take charge and implement these ourselves. There are many ideas scattered throughout the net on the make or buy dilemma as it applies to VIP. Most of them were written by VIP vendors and really, what are they going to say? I don't claim any authority on the topic with this post, but I want to share my view as both a homegrown VIP developer and subsequent user.

A little while back our team decided to go the way of the warrior and develop our own in-house UVCs for the AMBA protocols we use. This was by no means anything new within the company. We already had a considerable portfolio of eVCs and other UVCs (of varying quality) for various protocols our chips employ, both proprietary and standard. I was lucky enough to have just finished a project around that time and to get a chance to be involved in the development. Now, more than a year later, I've started to use some of them on my current project. This is a good time to reflect on the pros and cons of homegrown VIP.

The most obvious advantage to building versus buying is the financial one. The cost model I've seen up to now for VIP involves subscription fees for licenses. This is money that can be saved. We do have to pay upfront by having to spend engineering time developing the VIP, though. This can lead to somewhat of a ski rental problem because we might not really be able to say how high this initial cost will be, but for simple protocols I'd argue this isn't such a big deal. For example, I'd say that a UVC for a simple protocol like APB could be developed in about one man-week and one for something more complicated like AHB maybe in something of the order of one man-month. Protocols of the complexity order of AXI and beyond are a whole different matter...

While money is an important factor, that wasn't the reason we went down the route of writing our own UVCs. The main one was stability. I think a lot of us have seen the case where VIP from vendor X doesn't work with the simulator from vendor Y. We know that the SystemVerilog standard isn't specific enough and open to interpretation in some places and different simulators can treat a construct in different ways. At the same time, the degree to which different vendors have implemented the standard also varies, with some constructs being supported in one tool, but not in another. Having the source code under our control means that we can tackle such issues, so switching simulator vendors won't impact us so dramatically anymore. But having write access to the source code can be both a blessing and a curse...

We have to admit that more often than not, when starting something new we get very excited and want to jump directly into our text editors and start writing some code. This "code first, think later" mentality can only hurt us because instead of focusing on quality from the beginning we might just say "we can weed out the bugs later". Bugs in a UVC can be disastrous as they can lead to design bugs escaping the net and making it onto silicon. This isn't to say that commercial VIP is 100% bug free (as I've seen my fair share), but vendors are more likely to have good quality control procedures set up, meaning that bugs become rare. Unit and integration testing are the tools we can use to mitigate such problems. If you haven't already I invite you to have a look at SVUnit. I've also written about it in this post. If there's anything that really, really, really needs be properly tested, it's our UVCs!

Another blessing when we have access to the source code of our UVCs (and not jus read-only) is extendability. It's much easier to accommodate deviations from the standard protocol when we can build these directly into the UVC and not have to bolt them onto a standard UVC. How we do this, however, should depend on whether or not we need to implement the standard protocol too.

The curse begins to manifest itself when we would like to have our UVC do some cool thing that we only need in our current project, but that no one else needs. Since we have the source code under our command, we might think that it won't do any harm to add new capabilities to the UVC. They may be useful to others someday too! It's also easier that using OOP concepts like inheritance and/or composition, so the temptation is just too big. What we get with such feature creep, though, is a tangled mess of configuration switches, extra interface signals that don't exist in the specification and spaghetti code for our UVC components. What we need is a clear vision of what is of general interest and what is not. We can use our power over the code for good, by adding hooks to it to facilitate extendability, but not to implement everything on a whim.

Homegrown UVCs will also tend to have ad-hoc maintenance practices. This is also coupled with lax release processes, with no guidelines for deprecating old features and adding new ones. My biggest pet peeve is source code management, where everything will get dumped into the main branch, instead of making use of branches and labels (or whatever the terminology of your SCM is) and other tools that are provided to us. The main question here is "do we release tar files with specific versions or do we point to the repository where the UVC development is done?". This, in my opinion, is the root of all evil. In the latter case, users will get itchy fingers and want to change code to fit their needs. As we saw above, even when done with the best intentions, this isn't a good idea. I tend to avoid this even for fixes, even if I do have access to the source code and the development repository. If I need to tweak the behavior of the UVC I prefer to create extended classes in my verification environment rather than change something in the UVC itself. These can always be incorporated later or be released as a standalone package for others to use.

Last but not least, since documentation is always a second class citizen, it will just fall behind (I plead guilty here!). Even if we spend time to do the documentation properly and to keep it up-to-date, people still won't read it if they have someone to ask in person. To prove this, how many times have you asked your simulator's application engineer about something instead of reading up on it in the manual?

Lately, open source UVCs have started appearing. The guys over at AMIQ Consulting have already released three VIP packages: Ethernet, APB and DCR. I haven't looked at them, so I won't comment, but the company does have an EDA arm hence I'm guessing they understand development concepts much better than I do (and they could probably even add to the points above). I'm hoping to see many more such such releases in the future, from them and from others. I mentioned open source UVCs here since they have the potential of saving us the initial development cost associated with building our own, while still providing all of the advantages. They also, however, carry the same temptations. Remember, having write access to the source code is power and, as we know already, power corrupts!

In conclusion, having homegrown VIP can be a really good thing, as long as we invest the time to do it right. The list ended up having more cons than pros, but these can be mitigated. We just need to plan changes appropriately and not just commit every single thing into the UVC repository without thinking and especially not without testing. It might not seem worth it to spend the extra effort, but if we don't we'll end up using a lot of our time fire-fighting and we may have just been better off buying the VIP. We need to set responsibilities for the UVC's source code and stick with them. We need to know that we have two hats to wear, one as a customer and one as a developer, and we need to know when to wear each.

On SystemVerilog Coding Conventions - Challenging the Status Quo

When I first started out I remember reading all of these nice naming conventions for SystemVerilog. For example, when developing a new verification component, we're supposed to choose a descriptive name for it, preferably as short as possible. To distinguish it from other VCs doing the same thing, we should add a prefix that's unique to our organization to the name we chose. If, for example, we would be developing an AHB VC, a recommended name for it would be vgm_ahb. For the name of the package that contains the code we should add the pkg suffix, hence it should be called vgm_ahb_pkg. Any classes we write for our VC should also contain vgm_ahb in their names. For example, our driver class would be called vgm_ahb_driver, our monitor would be called vgm_ahb_monitor, etc.

I didn't pay too much attention to this at first. As a beginner I thought that there were surely good reasons for these conventions and I just happily followed them. Besides, everyone else was doing it. If we look at UVM, the package we import is called uvm_pkg. The classes we use are called uvm_object, uvm_component, etc.

Lately I got to thinking more about this and now I'm asking myself the question "Why?". A reason we might get for why things are like this is so that we can use the ever popular "wildcard import" operator, import some_pkg::*, and still avoid naming collisions. If we try to wildcard import two constructs that have the same name, the compiler will get confused. Making sure that class names are unique means that we'll never have any problems. The jury's still out on whether wildcard imports are good or bad. I haven't yet read any justification that managed to sway me one way or the other, so this is a discussion for another time.

What we can notice, though, is there is a lot of redundancy in the names. For UVM, for example, there are uvm prefixes flying around everywhere. This includes types and enumeration literals. The C language doesn't have any scoping constructs, so everything is visible. This gives people headaches when linking, as name collisions are possible. To avoid this, C developers typically try make their names unique. In SystemVerilog, however, we have the package concept, which is very similar to Java's packages or C++'s namespaces.

If we were creating a UVC, following the current guidelines it might look like this:

// file: vgm_ahb_driver.svh

class vgm_ahb_driver extends uvm_driver;
  // ...
endclass

// file: vgm_ahb_monitor.svh

class vgm_ahb_monitor extends uvm_monitor;
  // ...
endclass

// file: vgm_ahb_agent.svh

class vgm_ahb_agent extends uvm_agent;
  vgm_ahb_driver drv;
  vgm_ahb_monitor mon;

  // ...
endclass

// file: vgm_ahb_pkg.sv

package vgm_ahb_pkg;
  import uvm_pkg::*;

  `include "vgm_ahb_driver.svh"
  `include "vgm_ahb_monitor.svh"
  `include "vgm_ahb_agent.svh"
endpackage

That's a a bit too much vgm_ahb for my taste. What if we tried to shorten some of these names? Let's just cut the vgm_ahb prefix:

// file: driver.svh

class driver extends uvm_driver;
  // ...
endclass

// file: monitor.svh

class monitor extends uvm_monitor;
  // ...
endclass

// file: agent.svh

class agent extends uvm_agent;
  driver drv;
  monitor mon;

  // ...
endclass

// file: vgm_ahb.sv

package vgm_ahb;
  import uvm_pkg::*;

  `include "driver.svh"
  `include "monitor.svh"
  `include "agent.svh"
endpackage

If we were to have a testbench that instantiates an AHB agent, the code would look like this:

class env extends uvm_env;
  agent ahb_agent;

  // ...
endclass

If we were to have a second AXI UVC built in the same way, then we'd need another way to be able to differentiate between the two agents, since the class names are now identical. We can just use the scoping operator:

class env extends uvm_env;
  vgm_ahb::agent ahb_agent;
  vgm_axi::agent axi_agent;

  // ...
endclass

Why this is basically the same as using prefixes for our class names, isn't it? (There is one extra character in there because a "::" is longer than a "_", but in the grand scope of things I'd say it's negligible.) We could even go one step further and (in about 20 years) have UVM cleaned up. This would make our driver (and other component) definition(s) look like this:

// file: driver.svh

class driver extends uvm::driver;
  // ...
endclass

This frees up UVC developers to use short and descriptive names for their classes. The discussion whether to use wildcard import or not becomes orthogonal. For classes where there aren't any name collisions it's just going to work. For classes where there is one, we just use the explicitly scoped name, which is anyway (almost) as long as if we would have used the prefix.

This also applies to type definitions and enumerated literals; basically to anything that has package scope. What can't be scoped, though are macros. Those annoying `uvm_object_utils still have to contain a prefix, since they can't be defined in packages. That's ok, though, since we all agree that macros are evil and we won't use them, right? (Yeah, right!)

Going the way of no prefixes has a tiny inconvenience with the current generation of tools, though. When we compile a testbench, we very often want to do the whole compile with one tool call:

compiler +incdir+path/to/vgm/ahb vgm_ahb.sv +incdir+path/to/vgm/axi vgm_axi.sv ... 

If both packages include files called driver.svh, then for the case above we'll have the nice surprise that the AXI package includes AHB source files instead of its own. This is because the AHB directory is going to be searched before the AXI directory. We just have to separate the compile into multiple tool invocations:

compiler +incdir+path/to/vgm/ahb vgm_ahb.sv
compiler +incdir+path/to/vgm/axi vgm_axi.sv ... 

How often do we need to compile our UVCs anyway? I think this is something we could live with for now, but it would have been really great if the compiler would have automatically searched the directory where the package is located. Then we wouldn't need any funky +incdir+ arguments and this whole issue could have been averted.

Another topic I want to touch upon is those include guards we all see everywhere. I guess this is C++ legacy, where we need to include library headers to use them. The use model in SystemVerilog (similar to Java) is to import packages, though. Coming back to the example above, it doesn't make any sense for a verification environment to include the AHB driver.svh file, since that file file comes bundled with the vgm_ahb package. Trying to protect ourselves from including that file again is analogous to trying to protect ourselves from others including our cpp files in C++. Anybody who does this will be immediately informed by the compiler that something is wrong.

Coming back to macros again, that's the only place where such include guards have any place, since a macro header could get included in multiple files in the current compilation unit. I guess a lot of the confusion stems from the fact that the same svh file extension is used for both code that is intended to be included by the user (i.e. macro headers) and for code that package developers are supposed to include in their packages (as was the case above for driver.svh, monitor.svh, etc.). Maybe it would make more sense to create a new file extension for the latter case. Off the top of my head, maybe svi (SV implementation) would be a good name. Then we could publish the guideline that svh files can be included, but svi files cannot.

SystemVerulog is mixed up enough, with its design/hierarchy constructs on one side and OOP constructs on the other. The OOP constructs themselves are a confused amalgamation of C++ and Java. We can't just blindly take conventions from the latter languages and bolt them on here. We're going to need to develop our own coding conventions that make sense in the context of this language.

Do You Want Sprinkles with That? - Mixing in Constraints

The goal of modern verification techniques is to do as much as possible with as little code as possible. This is best done with a "write once, tweak everywhere" approach to test development. This type of flexibility comes for free in AOP; that's why it's built into e's DNA. For OOP, however, it requires thought and planning, and is achieved by using design patterns. One reason why the UVM exists is to encapsulate some of these patterns for us (especially the factory). Even so, this doesn't mean that some design pattern knowledge won't help us do fancy stuff in our code.

In this post I want to talk about how to layer constraints across the sequence item class hierarchy. My points would be best understood by looking at a concrete example. Let's say that our DUT has an AHB bus. I've chosen AHB because it's very widespread and most of you will have already worked with it. We'll keep things simple and only consider a reduced sequence item:

class vgm_ahb_item extends uvm_sequence_item;
  rand bit[31:0] addr;
  rand direction_e direction;
  rand burst_e burst;
  rand size_e size;
  rand mode_e mode;
  rand privilege_e privilege;

  rand int unsigned delay;


  constraint delay_init_val {
    delay inside { [0 : 10] };
  }

  constraint no_instr_write {
    mode == INSTR -> direction == READ;
  }

  constraint aligned_address {
    size == HALFWORD -> addr[0:0] == 0;
    size == WORD -> addr[1:0] == 0;
  }

  // ...
endclass

Address and direction are pretty self explanatory. Burst tells us how many bus cycles will be performed. Size represents the number of bytes transferred in each bus cycle. Mode tells us whether we are moving data or instructions. Finally, there is also privilege that shows us from what part of the code the access originated. The item already contains some structural constrains given by the protocol.

Let's say we've written two tests for our DUT. The first test does write/read-back pairs at random locations to make sure that the entire address space is accessible. It does this by starting the following sequence:

class write_read_sequence extends uvm_sequence #(vgm_ahb_item);
  virtual task body();
    req = vgm_ahb_item::type_id::create("req");

    for (int i = 0; i < 20; i++) begin
      start_item(req);
      if (!req.randomize() with { direction == WRITE; })
        `uvm_error("RANDERR", "Randomization error")
      finish_item(req);

      start_item(req);
      req.direction = READ;
      if (!req.randomize(delay))
        `uvm_error("RANDERR", "Randomization error")
      finish_item(req);
    end
  endtask
endclass

The second test does purely random accesses inside the address space by starting another sequence:

class random_access_sequence extends uvm_sequence #(vgm_ahb_item);
  virtual task body();
    req = vgm_ahb_item::type_id::create("req");

    for (int i = 0; i < 30; i++) begin
      start_item(req);
      if (!req.randomize())
        `uvm_error("RANDERR", "Randomization error")
      finish_item(req);
    end
  endtask
endclass

After running these tests for a while with different seeds we stumble onto a bug. It seems our device has problems when doing privileged data accesses. Addresses within 0x0 and 0x20 cause trouble when being accessed by single word bursts. We want to put more emphasis on these transfers to make sure that we're really stressing this part of the DUTs functionality. This is where "write once, tweak everywhere" comes along. We can just run the same tests as before, but add a new constraint to make the problematic bursts more likely.

This is best done by creating a new test that starts the same sequence, but sets a type override on the sequence item. This new sequence item would be defined in the same file as the test and would contain the extra constraint:

class write_read_corner_case_ahb_item extends vgm_ahb_item;
  constraint corner_case {
    mode dist { DATA := 3, INSTR := 1 };
    privilege dist { PRIVILEGED := 3, USER := 1 };
    (mode == DATA && privilege == PRIVILEGED) ->
      (addr inside { [32'h0:32'h20] } && size == WORD && burst == SINGLE);
  }
endclass

The new write_read test would just extend the previous one that already starts the sequence and just set a type override:

class test_write_read_corner_case extends test_write_read;
  function void end_of_elaboration_phase(uvm_phase phase);
    uvm_factory factory = uvm_factory::get();
    factory.set_type_override_by_type(vgm_ahb_item::get_type(),
      write_read_corner_case_ahb_item::get_type());
  endfunction
endclass

We'd want to do the same thing for the random_access test. If we define a similar sequence item in another test file it immediately becomes clear that we've doubled up information. The same constraint would exist in two files. At this point we could do a tradeoff between encapsulation and maintainability. We can declare the corner_case item outside of the tests, in some common location. This will make it fall under shared ownership (as all test writers would see it), with all the challenges that brings. At least we wouldn't need to maintain the same constraint in two (or potentially more) files.

With that settled, we run our regression longer, but we find another bug. This one has to do with reading words with 0 delay. As before, we want to guide our randomization efforts more on this one too. Adding a constraint to both of the tests is the same case that we looked at above. We can handle it in the same way. What we do notice, however, is that this bug, like the previous one, affects WORD transfers. It makes sense to try and combine this constraint with the one from above and make sure that we don't have any other bugs at the intersection of these two cases.

Before we proceed, let's summarize. We've currently defined a corner_case item and a fast_reads item that we can use to tweak the initial tests with:

class corner_case_ahb_item extends vgm_ahb_item;
  constraint corner_case {
    mode dist { DATA := 3, INSTR := 1 };
    privilege dist { PRIVILEGED := 3, USER := 1 };
    (mode == DATA && privilege == PRIVILEGED) ->
      (addr inside { [32'h0:32'h20] } && size == WORD && burst == SINGLE);
  }
endclass

class fast_reads_ahb_item extends vgm_ahb_item;
  constraint fast_reads {
    size dist { WORD := 3, BYTE := 1, HALFWORD := 1 };
    (direction == READ && size == WORD) -> delay == 0;
  }
endclass

Now we need an item that contains both constraints. This kind of gets us stumped. Which of these items should we extend from? Is our new item a corner_case item with an extra constraint? If so, then we should extend from corner_case_ahb_item:

class corner_case_fast_reads_ahb_item extends corner_case_ahb_item;
  constraint fast_reads {
    size dist { WORD := 3, BYTE := 1, HALFWORD := 1 };
    (direction == READ && size == WORD) -> delay == 0;
  }
endclass

Or is it a fast_reads item with an extra constraint? In that case we should extend from fast_reads_ahb_item:

class corner_case_fast_reads_ahb_item extends fast_reads_ahb_item;
  constraint corner_case {
    mode dist { DATA := 3, INSTR := 1 };
    privilege dist { PRIVILEGED := 3, USER := 1 };
    (mode == DATA && privilege == PRIVILEGED) ->
      (addr inside { [32'h0:32'h20] } && size == WORD && burst == SINGLE);
  }
endclass

No matter what we do, however, we're doubling up some code. The problem only gets worse if we want to add a third constraint and so on.

Our conceptual failure was that this new item is neither a corner_case_ahb_item nor a fast_reads_ahb_item with a little bit on top. It's actually both. We need to do multiple inheritance, but SystemVerilog only supports single inheritance. Bummer, huh?

Actually, no. We already talked about how to fake multiple inheritance using the mixin pattern in a previous post. Let's apply it here. Instead of having a corner_case item or a fast_reads item, let's have a mixin for each constraint:

class corner_case_mixin #(type T) extends T;
  constraint corner_case {
    mode dist { DATA := 3, INSTR := 1 };
    privilege dist { PRIVILEGED := 3, USER := 1 };
    (mode == DATA && privilege == PRIVILEGED) ->
      (addr inside { [32'h0:32'h20] } && size == WORD && burst == SINGLE);
  }
endclass

class fast_reads_mixin #(type T) extends T;
  constraint fast_reads {
    size dist { WORD := 3, BYTE := 1, HALFWORD := 1 };
    (direction == READ && size == WORD) -> delay == 0;
  }
endclass

Actually, we can still have those old items, but we should implement them using the mixins:

class corner_case_ahb_item extends corner_case_mixin #(vgm_ahb_item);
endclass

class fast_reads_ahb_item extends fast_reads_mixin #(vgm_ahb_item);
endclass

We can implement the new item with both constraints by applying the other mixin on top of a previously mixed in item:

class corner_case_fast_reads_ahb_item extends
  fast_reads_mixin #(corner_case_ahb_item);
endclass

It doesn't really matter what order we do it in. We'll get the same great flavor either way:

class fast_reads_corner_case_ahb_item extends
  corner_case_ahb_mixin #(fast_reads_ahb_item);
endclass

We can even apply the mixins successively starting from the base ahb_item:

class corner_case_fast_reads_ahb_item extends
  fast_reads_mixin #(corner_case_mixin #(vgm_ahb_item));
endclass

You get the idea. We can add as many as we want in whatever order we want.

As a bonus, we don't even need to have shared items anymore. We can only share mixins inside some central location in our package. We can shift the responsibility of defining items for the overrides back to the tests:

class test_write_read_corner_case_fast_reads extends test_write_read;

  // nested class
  class ovr_seq_item extends fast_reads_mixin #(corner_case_mixin #(
    vgm_ahb_item));
  endclass


  function void end_of_elaboration_phase(uvm_phase phase);
    uvm_factory factory = uvm_factory::get();
    factory.set_type_override_by_type(vgm_ahb_item::get_type(),
      ovr_seq_item::get_type());
  endfunction
endclass

By defining the override item inside the test as a nested class we make it clear that it's not supposed to be used anywhere else. We also make it impossible to accidentally reference items defined in other test files, because these items aren't declared in the package scope anymore. We just have to be careful not to use "by name" overrides, since that might get us into trouble (as items might share the same name).

What we've done here is traded up the value chain. We gained maintainability by doing away with doubled up constraints. Our approach also allows us to shift on the encapsulation scale (global override items vs. test encapsulated override items). We didn't create this from nothing, though. We added intelligence into our code by using the mixin patter.

I've taken some liberties with the code I posted by removing calls to UVM macros and constructor definitions, to keep it short and focus on the important topics. You can find the complete code on SourceForge. I've also added a third "bug" to investigate - "slow writes". Have a look at the commit history to see how the code base shrinks when using mixins, compared to a classical approach.

Patching a Leaky Boat - Handling UVM Bugs

This week I stumbled on an issue with the UVM base class library (BCL). I was using the register layer to access some memories and some things just didn't add up. I've posted a description in the forums, so let's see what the higher ups say.

I need that functionality now, though. I can't wait for UVM 1.1e (which will never come out) or UVM 1.2a. I also wouldn't want to switch to UVM 1.2 yet, even if the issue were fixed there. This got me thinking what the best way to handle such a situation is.

A bit of background on the UVM standard: just the API document is standardized, not the BCL. The Accellera UVM library is only a proof of concept. A major plus for the EDA vendors in increased UVM adoption is that they can develop debug extensions for it, which should make us more productive. Such a feature needs infrastructure, though. I've seen two implementation models up to now. In the first case, the BCL is left unchanged and vendor extensions are added on top, via a separate package. In the second case, the BCL itself is modified to include vendor extensions. Both approaches are "legal" according to the UVM philosophy, because as long as the API stays the same and stuff behaves as described in the standard, they get the UVM seal of approval.

In the first case, fixing a BCL bug is easy. We can just take the BCL and patch it and we won't get any problems with the vendor extensions. In the second case, things aren't as straightforward. Here, the UVM package comes bundled with the simulator and is installed in some read-only location. Also, because each simulator version comes with a (potentially) different version of UVM, editing the code directly isn't feasible.

In my current project I'm using a vendor of the second persuasion. A key requirement I have is that I want to be able to easily switch between simulator versions. This means I need a non-intrusive fix. This is only possible if I can replace instances of a specific class with my own extended class. This is where the UVM factory comes in, but to be able to use it, the offending objects have to be created using the factory.

In our case, we want to replace all instances of uvm_reg_map with an extended class we'll call vgm_reg_map. Luckily, uvm_reg_map is registered with the factory and is instantiated using create(...). We'll do our fixes in a separate package, vgm_uvm_patches. We'll need to import this package and set a type override inside our verification environment:

import vgm_uvm_fixes::vgm_reg_map;

class some_tb_env extends uvm_env;
  function void build_phase(uvm_phase phase);
    patch();

    // Build env
    // ...
  endfunction


  function void patch();
    uvm_factory factory = uvm_factory::get();
    factory.set_type_override_by_type(uvm_reg_map::get_type(),
      vgm_reg_map::get_type());
  endfunction
endclass

How do we go about fixing uvm_reg_map? We'll need to create an extended class and register it with the factory:

class vgm_reg_map extends uvm_reg_map;
  `uvm_object_utils(vgm_reg_map)

  function new(string name="vgm_reg_map");
    super.new(name);
  endfunction
endclass

Because we care about the quality of our work, we're going to create unit tests that expose the issue. Ideally we'd also create unit tests for the existing behavior, to make sure that we don't break anything else. Since this is going to be a small fix, we won't do it because it's not really worth it. Here's a test that fails due to this bug:

`SVTEST(get_physical_addresses__max_offset__returns_end_addr)
  uvm_reg_addr_t addrs[];
  map.get_physical_addresses(32'h0, 32'hffff, 4, addrs);

  `FAIL_IF(addrs.size() != 1)
  `FAIL_IF(addrs[0] != 32'hffff)
`SVTEST_END

When trying to get the physical address of offset 0xffff, we get 0x3_fffc, causing the test to fail. The only thing we can do in this case is to copy the code for the offending function from uvm_reg_map and paste it into our extension. When trying to compile, we'll get some errors that the method tries to use local fields. The first one occurs at the following line:

int multiplier = m_byte_addressing ? bus_width : 1;

Since m_byte_addressing is declared as local, we can't use it in the extended class. The only way to get it's value is by using the get_addr_unit_bytes(...) function:

function int unsigned uvm_reg_map::get_addr_unit_bytes();
  return (m_byte_addressing) ? 1 : m_n_bytes;
endfunction

What this function returns is suspiciously similar to what the original developer tried to assign to multiplier. Assigning it the return value of the function and fixing the other references to local fields will make our unit test pass.

This method of fixing the issue seems kind of clunky. I'm not very comfortable copy/pasting so much code, but we had to do this because the offending method was so big and poorly encapsulated. It could have been split into sub-methods, which would have made it easier to test and change. We'll talk more about this in a future post after I finish reading Refactoring: Improving the Design of Existing Code.

The fix we made is not-intrusive to the UVM package, but it's intrusive to our own testbench code. We need to compile the package in our run script, but we also have to add the necessary factory override to our environment class. If there were to be an official fix in the future, we'd need to go back and remove them from our code.

I can't resist making a comment as to how aspect oriented programming would have been so much better here. In e we'd just create a file, implement our patch there and import it after importing UVM. All instances of the affected class would get the fix. Since there wouldn't be any changes in our code, such a fix would be truly non-intrusive.

You can find the code for the package on SourceForge. This can be a good starting point for developing a similar package for your company/department/team. If there's interest from the public, I can create an own repository for this package and add to it. Let me know in the comment section.

Less Is More - Why I Favor Short Tests

We're not going to be looking at any code in this post. We are, however, going to examine the impact the length of the tests we write has on various aspects of the verification process. The "long vs. short tests" debate is something I often have with colleagues and every time I have to re-iterate the same points. Usually I can't touch on all of them because the discussion is cut short or because I just forget to bring some of them up. This post is my attempt at formalizing my point of view, for myself first of all, but also for others.

When we talk about simulation duration we have two things to consider:

1. simulation time - how much time has passed within the simulation; it's usually measured at the nano-/micro-/millisecond scale
2. processor time - how long it takes for the simulation to execute on the machine; values are typically measured in seconds, minutes or hours

The two are connected by the complexity of our DUT. For a bigger design it will take more processor time to simulate 50 microseconds. A short test is a test that can be simulated in a short amount of time. Assuming we can't do anything to influence our simulation speed (which is usually a function of the simulation tool and the machines we simulate on), to get shorter tests they need to simulate less.

 

Short tests are easier to develop

By testing less in one simulation run we don't have to write complex stimuli, which means that we'll finish building our test faster. We'll need more tests though, but this is what we have modern verification techniques for. Constrained random verification's most touted feature might be that it makes it easier to hit states in the design we wouldn't have dreamed of trying to hit, but to me its main use is as a test automation tool.

Even though I promised we won't look at code, let's just take a little sneak peak. Here's how a short test would look like. It just checks that the DUT can perform a certain operation of a specific kind and that's it:

<'
extend MAIN my_virtual_sequence {
  body() @driver.clock is only {
    do init_seq;
    do operation;
  };
};
'>

A longer test would do more than just test that a certain operation works. This test checks that all operations of that kind work and also tries to perform some other tasks afterwards:

<'
extend MAIN my_virtual_sequence {
  body() @driver.clock is only {
    do init_seq;
    
    for each (op) in [ OP1, OP2, OP3, OP4 ] {
      do operation keeping { .op == op };
      
      if oo == OP2 {
        do something_else;
        do even_more;
      };
      
      if op == OP4 {
        wait delay (100 ns);  // TODO ask designer what the appropriate delay is
        do some_other_operation;
      };
      
      // ...
    };
  };
};
'>

The example is pretty basic, but the second test would take longer to develop. There are more things to consider now: what values to loop over, what can we perform after a certain operation, what is an appropriate delay, etc. If there's a bug in the design when doing an OP2 operation, for example, it's going to make it all the more difficult for us. We'll get information overload when trying to do too much at once. Humans are constructed to break problems down: we split tasks into sub-task, which we then split into sub-tasks and so forth. Why not write our tests in such a way to mirror this?

More tests doesn't have to mean more code. Our first test has the possibility to check that any operation works and it does this using randomization. We will get a lot of redundant test runs, but what's more expensive, engineering time or compute time? I'd rather optimize the former first and then, only if required, the latter.

 

Short tests are easier to parallelize

Test length also has an impact on the duration of the regression suite. You're probably thinking "Duh! If I have more to simulate my regression will be longer." That's not what I mean. What I mean is that long tests impact our ability to efficiently run tests in parallel. Let's start with the obvious: if we're able to run 100 jobs in parallel, but we only have 50 tests we're making poor use of our compute resources. Assuming our tests are all the same length, our regression will run 50% slower than it potentially could.

The same thing happens if we have tests that are much longer than the others. At some point, it's only going to be these tests that are running, while the others are already done. We're now in the same situation as before, where we use less jobs that we potentially could.

I'll give you an example of how a long test ruined it for me while I was running the final regressions on my last project. I had a problem with the compute farm and had to restart the regression. Almost all of my tests were done in less than 8 hours, but someone wrote one that was taking about 12 hours. When I started the regression again this test probably got submitted to a slower machine, because it took 20 hours or more to complete. This caused me to miss a whole day. Now, what was that test doing? It was checking that all sectors in our non-volatile memory were writable. Immediately from the description you can ask "why not write a test per sector then?". This would have cut down the simulation time by a factor of the number of sectors and it would have sped up the regression significantly.

 

Short tests are easier to debug

Regressions are there to weed out failures in the DUT. Should a fail occur, short, focused tests are easier to debug. Imagine running a test that takes one hour and we find an issue at the 50 minute mark. Before we can even begin to analyze it, we'll need to first run up to that point in time with all debug knobs on maximum, which is going to make the simulation take even longer. After reaching that point we have to analyze it, possibly together with the designer, and make a change in either the DUT or in the testbench if it turns out the issue wasn't a bug. Regardless of what we need to change, there's a pretty good chance that the patch won't work on the first try, which means we'll need to repeat the cycle all over again. We can lie to ourselves all we want and say that we'll handle something else while this test is re-running, but modern science tells us that humans aren't as good at multitasking as we think, so we'll be wasting effort by not being fully focused on the task at hand. It's either that or we're going to start surfing the Internet.

Even if we do decide to go down this route, good luck running your simulation for a long time with full waves. We're going to say hello to our friend, the simulator crash. Then again, we can run up to a certain point without full debug, turn it on and run to the point of the failure. At least this way it won't crash, but what will we do if we have to trace the problem backwards and we run out of waves? We'll have to adjust the time when we turn on debugging over and over again until we reach an appropriate tradeoff. That sounds like wasted time to me...

If we're clever, we're going to try isolate the issue in a short test and do our debugging on that. But, if a short test could have found this issue, why didn't we write it like this in the first place?

 

Short tests are easier to maintain

I deliberately used the word "short" so I can misuses it in this section. We can also refer to length in terms of lines of code. Granted, there are multiple factors that affect maintainability, but less code is easier to maintain because there are less opportunities to go wrong. What's more likely to be buggy, a "Hello world" program or a big testbench containing hundreds of classes and methods?

 

Long tests aren't inherently evil, but...

This doesn't mean that long tests aren't useful. Some issues might still lurk in the deep dark crevices of the design and it might only be possible to hit these by doing a very complicated sequence of operations. Other issues can also only be found when the planets are in some special alignment. What I'm advocating is to write tests that are as long as necessary and not longer. Other times it might be very useful to have a test that simply stresses the design over a long period, but is this really the kind of test that you need to run in a nightly regression? Most probably not, since it's highly unlikely that it's find anything new.

I for one will stick to my short tests that are easy to develop, debug, parallelize and maintain. What about you? Don't hesitate to share your thoughts on the topic in the comments section.

Fun and Games with CRV: The N-Queens Problem

It's been quite a while since we've solved the zebra puzzle using SystemVerilog. In this post we'll look at another oldie, but a goldie called the n-queens problem. This problem first appeared in a more specific form as the eight queens puzzle, first published in 1848. In this puzzle, the player is asked to place eight queens on a chessboard in such a way that they don't threaten each other. It has fascinated mathematicians (including the great Carl Friedrich Gauss) ever since to find solutions to it. Edsger Dijkstra used it to illustrate the power of backtracking. More recently, Team Specman also solved this problem using constraint programming and published it in this post. The e code they employed is short and sweet, but it's not so easy to digest, though.

In pure "re-inventing the wheel" fashion that we engineers love, I'm going to do my own solution, but in SystemVerilog.

We'll model the chess board as an n by n array of bit values. A 1 will mean that a queen is present on that square, while a 0 will indicate that the square is empty.

class n_queens_solver #(int unsigned n = 8);
  rand bit board[n][n];
  
  // ...
endclass

Modeling the board like this will (hopefully) make it easier to solve the puzzle in a way closer to how a human might solve it on a real board. We'll want to set constraints on the positions of the queens based on the their ranges of motion. Concretely, we'll want to say that only one queen can occupy a row, column or diagonal.

Before we start, however, we'll want to make sure the language supports a couple of things. First, we want to make sure that we can constrain a vector (a one-dimensional array) to contain only a single 1. We can do this using the classical double-for approach:

class singular_on_line #(int unsigned len = 8);
  rand bit line[len];
  
  constraint double_for {
    // the '1' can only be in one place
    foreach (line[i])
      foreach (line[j])
        (i != j) -> ((line[i] == 1) -> (line[j] == 0));
      
    // the '1' must exist in the array
    1 inside { line };
  }
endclass

The two foreach loops say that if one location of the vector contains the 1, then no other location can hold it. This doesn't ensure, however, that the 1 exists inside the vector, hence the need for the inside constraint. This approach works, but it's pretty long and verbose.

Luckily, starting with the 2012 version of the standard we can use array reduction methods in constraints. A good candidate for this is the sum() method. We want the sum of all elements in the array to be 1:

class singular_on_line #(int unsigned len = 8);
  constraint sum {
    line.sum() == 1;
  }
endclass

When testing this constraint, something strange happens. In most cases we won't get a single 1 inside the array. We will, however, always get an odd number of 1s. What's happening here? Because the elements of line are bits, the result is also interpreted as a one bit value, leading to truncation when adding up all the elements. The proper way to do it is to use an explicit cast to force summation to an integer value:

class singular_on_line #(int unsigned len = 8);
  constraint sum {
    line.sum() with ( int'(item) ) == 1;
  }
endclass

It's a shame we can't use the array locator methods inside constraints, as that would have made everything even more expressive. Maybe in a future release of the standard...

The second thing we should look at before diving into the full problem is how to construct the diagonals. This is going to be a bit more funky, since not all diagonals have the same length. For an array of n x n elements we'll have 2*n - 1 diagonals. Since the diagonals are of different lengths, it makes the most sense to store them as dynamic arrays:

class array_of_diags #(int unsigned n = 8);
  rand bit[2:0] array[n][n];
  
  rand bit[2:0] diags[n*2 - 1][];
endclass

We need to establish a convention on how we'll number the diagonals. Let's look at a 3 x 3 array:

+-------+-------+-------+
|       |       |       |
| (0,0) | (0,1) | (0,2) |
|       |       |       |
+-------+-------+-------+
|       |       |       |
| (1,0) | (1,1) | (1,2) |
|       |       |       |
+-------+-------+-------+
|       |       |       |
| (2,0) | (2,1) | (2,2) |
|       |       |       |
+-------+-------+-------+

We'll number the diagonals going horizontally from left to right and vertically from top to bottom. We'll insert elements going also from left to right, but from bottom to top. This is a bit difficult to explain in words (and I'm not good enough yet with HTML to draw it for you), but it should be easy to understand by example. In our case, the diagonals will contain the following elements:

• diags[0] = { (0,0) }
• diags[1] = { (1,0), (0,1) }
• diags[2] = { (2,0), (1,1), (0,2) }
• diags[3] = { (2,1), (1,2) }
• diags[4] = { (2,2) }

With a little observation and mathematical induction, we can figure out that the constraint to create the diagonals looks like this:

class array_of_diags #(int unsigned n = 8);
  constraint create_diags {
    foreach (diags[i,j])
      if (i < n)
        diags[i][j] == array[i - j][j];
      else
        diags[i][j] == array[(n - 1) - j][i + j - (n - 1)];
  }
endclass

What's very important, though, when working with constraints on dynamic arrays is to make sure that their sizes are set up correctly. We can easily do this inside the pre_randomize() function:

class array_of_diags #(int unsigned n = 8);
  function void pre_randomize();
    foreach (diags[i])
      diags[i] = new[get_len_of_diag(i)];
  endfunction
  
  
  function int unsigned get_len_of_diag(int unsigned idx);
    if (idx < n)
      return idx + 1;
    
    return 2*n - (idx + 1);
  endfunction
endclass

The formula to get the length of a diagonal can be easily worked out by observation. In fact, that's how I figured out most of these array constraints. I just took an example array and tried to relate different things to an element's row/column index and the size of the array.

Just to be on the safe side, I've also made sure that any constraints we apply on the diagonals' elements will also propagate back to the initial array we've constructed them from. We don't want to get any issues with unidirectional constraints. For brevity, I won't show that code here.

With these topics sorted out we can get started. We'll use some helper variables to store our rows, columns and diagonals:

class n_queens_solver #(int unsigned n = 8);
  rand bit rows[n][n];
  rand bit cols[n][n];
  rand bit main_diags[2*n - 1][];
  rand bit anti_diags[2*n - 1][];
endclass

Unfortunately, SystemVerilog doesn't have the concept of pointers, so these extra arrays will use some extra memory, but this shouldn't decrease generation performance. Don't hold me to this last statement, but this is a hunch of mine, since the constraints we use to relate these variables to the board don't increase our randomization state space (they are 1:1 mappings).

It's not really necessary to use a separate variable for the rows (as rows are easily indexable from an array), but it makes the code more expressive (plus, I'm a bit of a sucker for symmetry and it would feel unbalanced to treat the rows differently). Here's the constraint to create the rows:

class n_queens_solver #(int unsigned n = 8);
  constraint create_rows {
    foreach (rows[i, j])
      rows[i][j] == board[i][j];
  }
endclass

And here's how to create the columns:

class n_queens_solver #(int unsigned n = 8);
  constraint create_cols {
    foreach (cols[i, j])
      cols[i][j] == board[j][i];
  }
endclass

The main diagonals are the diagonals that sweep the array from left to right and from top to bottom:

Here's the constraint to create them:

class n_queens_solver #(int unsigned n = 8);
  constraint create_main_diags {
    foreach (main_diags[i,j])
      if (i < n)
        main_diags[i][j] == board[j][(n - 1) - i + j];
      else
        main_diags[i][j] == board[i - (n - 1) + j][j];
  }
endclass

The anti diagonals sweep the array from right to left and from top to bottom:

And here's the constraint to create them too:

class n_queens_solver #(int unsigned n = 8);
  constraint create_anti_diags {
    foreach (anti_diags[i,j])
      if (i < n)
        anti_diags[i][j] == board[i - j][j];
      else
        anti_diags[i][j] == board[(n - 1) - j][i + j - (n - 1)];
  }
endclass

I would love to see a concept where these fields can get created without occupying extra memory, since they're basically just copies of other fields. Until then, we'll have to make the most of what we have.

After creating the lines of our chess board, it's time to finally start writing the constraints to solve the puzzle. Since a queen has an unlimited horizontal range of motion, it must occupy an entire row by itself:

class n_queens_solver #(int unsigned n = 8);
  constraint singular_on_row {
    foreach (rows[i])
      rows[i].sum() with ( int'(item) ) == 1;
  }
endclass

Similarly, a queen must occupy an entire column by itself:

class n_queens_solver #(int unsigned n = 8);
  constraint singular_on_col {
    foreach (cols[i])
      cols[i].sum() with ( int'(item) ) == 1;
  }
endclass

Queens also have unlimited range on any diagonals (both main and anti) they occupy. This means that no two queens can occupy the same diagonal. My first idea was to put a constraint similar to the ones above on each diagonal:

class n_queens_solver #(int unsigned n = 8);
  constraint singular_on_main_diag {
    foreach (main_diags[i])
      main_diags[i].sum() with ( int'(item) ) == 1;
  }
endclass

After adding this constraint the constraint solver started failing. I was scratching my head in wonder and was just about ready to cry foul on the solver, when I realized that I had been wrong all along. It's true that there can only be one queen on a certain diagonal, but the key thing to note is that there doesn't have to be a queen on each diagonal. Of course, this makes sense, since as we saw above there are 2*n - 1 diagonals and we can only place n queens.

What we can do instead is only constrain those diagonals that cross a position where a queen is located:

class n_queens_solver #(int unsigned n = 8);  
  constraint singular_on_main_diag {
    foreach (cols[j,i])
      if (cols[j][i] == 1)
        main_diags[(n - 1) - j + i].sum() with ( int'(item) ) == 1;
  }
endclass

Adding a similar constraint to the anti diagonals will solve the puzzle. The constraint doesn't look very nice, though. It's looks pretty complicated and it won't be easy to understand (even I'm having problems it while writing this post). It seems to me that we're doing too much work for the solver!

As we saw above, we can either have one queen or no queens on a diagonal. Why not write that as a constraint? This leads to much less code:

class n_queens_solver #(int unsigned n = 8);
  constraint singular_on_main_diag {
    foreach (main_diags[i])
      main_diags[i].sum() with ( int'(item) ) inside {0, 1};
  }
  
  constraint singular_on_anti_diag {
    foreach (anti_diags[i])
      anti_diags[i].sum() with ( int'(item) ) inside {0, 1};
  }
endclass

And that's all there is to it! We've written a lot of code just to set up our board's lines, but the constraints we wrote on them are pretty straightforward and easy to understand.

I've tried running the solution on my modest machine and it works pretty fast for an n equal to 8. It's a bit slower for 9 and even slower for 10. It kind of runs out of steam for greater values, as Vitaly predicted in his post. Intelligen might be faster for this particular problem (I haven't tried it out myself), but whether it's faster in all practical situations for usual constraints I can't say. Cadence might be stretching the truth here, or rather put its best foot forward, for marketing purposes. I mean, how often do you write this style of constraints in production code?

You can find the full code on SourceForge. Feel free to download it and see how large an n you can handle.

Also, while I was writing the post I had the idea that instead of using vectors for the rows, columns and diagonals, maybe we could use packed arrays. We might be able to set $onehot constraints on them, though I'm not sure if this is supported. If any of you try it out, please share your experience in the comments section.