Thursday, April 23, 2015

Fun and Games with CRV: Draw This Without Lifting Your Pencil

It's time for another installment in the "Fun and Games with CRV" series. I love doing these posts because there's something very engaging in modeling all sorts of problems as constraints. This time we're going to look at how to draw a barn without lifting our pencil from the paper and without doubling back. This wikiHow post shows us two ways how we could do that. Now lets see if we can write a solver that can find either of these solutions.

This problem is different from the other puzzle we've looked at before because it has a "time" component. We make moves one after the other and the order in which we make them limits what we can do in the next step. We know exactly how many moves we need to make; this is the number of edges the drawing has. This makes it easier to model, in comparison to more difficult problems where the number of steps is unknown.

While we are looking at how to draw a barn, this kind of puzzle is pretty widespread. Why not implement a more generic solver that can draw any type of figure? We can do this by splitting the solver part (the constraints) from the actual drawing we want to make. Such a drawing is merely a collection of edges, which connect two vertices each. These edges and vertices form a graph and what we want is to traverse it, by taking each edge exactly once. While for the drawing itself the direction of the edges doesn't matter (which is the start or the end vertex), it is important for how we draw the figure. We'll see how this impacts the solver later.

We'll encapsulate the task of modeling such a graph and the constraints needed to traverse it inside an own class. This drawer class (not the best of names, I admit) will provide a protected method that subclasses can call to define the edges of the drawing:

virtual class drawer;
  typedef struct {
    rand vertex_t v1;
    rand vertex_t v2;
  } edge_t;

  protected function void add_edge(vertex_t vertex1, vertex_t vertex2);
    // ...
  endfunction

  // ...
endclass

My first try was to store all of the edges inside an array and add a constraint to try and randomly select one from the list:

virtual class drawer;
  local edge_t edges[$];
  local edge_t dummy_edge;

  constraint choose_existing_edges {
    dummy_edge inside { edges };
  }
endclass

This would have been too easy and probably have made for too short a post. "Fortunately", the SystemVerilog LRM doesn't allow this kind of construct, restricting us to using only singular types with the inside operator (integers, bit vectors, enums, etc.). We'll need to store the connected vertices in some other way if we want to be able to solve this problem. The best way (I could think of) is an associative array of queues indexed by the vertex and containing a list of all other vertices it's connected to directly via edges:

virtual class drawer;
  typedef int unsigned vertex_t;
  typedef vertex_t connections_t[$];

  local connections_t connections[vertex_t];
endclass

Let's look at an example:

graph

In the drawing above, this is what the connections matrix would contain:

1 : { 2, 3, 4 }
2 : { 1 }
3 : { 1 }
4 : { 1, 5 }
5 : { 4 }

We can add to this data structure from the add_edge(...) function:

virtual class drawer;
  protected function void add_edge(vertex_t vertex1, vertex_t vertex2);
    if (connections.exists(vertex1) && vertex2 inside { connections[vertex1] })
      $fatal(0, "Connection %0d -> %0d already exists", vertex1, vertex2);

    connect_vertices(vertex1, vertex2);
    connect_vertices(vertex2, vertex1);

    begin
      edge_t e;
      e.v1 = vertex1;
      e.v2 = vertex2;
      edges.push_back(e);
    end
  endfunction


  local function void connect_vertices(vertex_t src, vertex_t dest);
    if (connections.exists(src))
      connections[src].push_back(dest);
    else
      connections[src] = '{ dest };
  endfunction
endclass
The connect_vertices(...) function handles updating the array of connections. Even though the edges can't be used in constraints directly, we can still store them. The number of edges we add will be the number of steps we need to draw.
It's also a good idea to store a list of all the vertices we have in our drawing. This list we could easily extract from the connections array by taking all of its keys:
virtual class drawer;
  local vertex_t vertices[$];

  function void pre_randomize();
    vertex_t v;
    void'(connections.first(v));
    do
      vertices.push_back(v);
    while (connections.next(v));
  endfunction
endclass

At this point, it makes sense to try again and write a constraint that can select an edge from the ones we've added to the list. I wanted to try something fancy here:

virtual class drawer;
  constraint choose_existing_edge {
    dummy_edge.v1 inside { vertices } &&
    dummy_edge.v2 inside { connections[dummy_edge.v1] };
  }
endclass

The idea was to choose the first vertex at random. The second vertex we could then choose from the list of vertices connected to the first one. In theory, this is great, but in practice, this constraint doesn't work because the index we are using for connections (dummy_edge.v1) is a random variable itself and this doesn't seem to be allowed. I'm not entirely sure if this is a simulator limitation or if the LRM forbids it.

We shouldn't give up on the idea just yet. With a bit of massaging, we can get it to compile. In the second constraint expression we can just loop over all entries inside connections and stop when we've reached the one corresponding to our chosen "starting" vertex:

virtual class drawer;
  constraint choose_existing_edges {
    dummy_edge.v1 inside { vertices };

    foreach (connections[v])
      if (dummy_edge.v1 == v)
        dummy_edge.v2 inside { connections[v] };
  }
endclass

It's a little more code, but it does the job perfectly. Now we have a solid base to really start building our solver. We'll need to keep track of what edges we've already drawn and when. We'll store them in an array, where index 0 will be the first edge we drawn, index 1 the second and so on:

virtual class drawer;
  local rand edge_t edge_being_drawn[];
endclass

The first constraint we'll write is that each edge we draw actually exists in the drawing. We've already written such a constraint for one edge, so we'll just extend it to cover all of them:

virtual class drawer;
  constraint choose_existing_edges {
    foreach (edge_being_drawn[i])
      edge_being_drawn[i].v1 inside { vertices };

    foreach (edge_being_drawn[i])
      foreach (connections[v])
        if (edge_being_drawn[i].v1 == v)
          edge_being_drawn[i].v2 inside { connections[v] };
  }
endclass

Just choosing edges that exist inside the figure isn't enough. We have to make sure that the edges are unique. Here I tried some more fanciness than the language affords. This constraint, though short and sweet, also doesn't compile:

virtual class drawer;
  constraint choose_unique_edges {
    unique { edge_being_drawn };
  }
endclass

As with the inside operator, the unique operator also only works on integral types. I tried to outsmart the compiler by declaring the struct as packed, but then it can't be declared as rand so that won't get us anywhere. As before, we're just going to have to throw some more code at the problem:

virtual class drawer;
  constraint choose_unique_edges {
    foreach (edge_being_drawn[i])
      foreach (edge_being_drawn[j])
        if (i != j)
          !(edge_being_drawn[i].v1 == edge_being_drawn[j].v1 &&
            edge_being_drawn[i].v2 == edge_being_drawn[j].v2);

    foreach (edge_being_drawn[i])
      foreach (edge_being_drawn[j])
        if (i != j)
          !(edge_being_drawn[i].v1 == edge_being_drawn[j].v2 &&
            edge_being_drawn[i].v2 == edge_being_drawn[j].v1);
  }
endclass

As we already know from the previous post on array constraints we can replace a unique constraint with a double foreach. It's not enough to say that the starting or ending vertices be different. We also need to make sure that we're not backtracking. Going from vertex 1 to vertex 3 is the same edge when going from vertex 3 to vertex 1 (it's just the direction that's different).

One more constraint is missing to make the solution complete. We have to make sure that when going from one edge to another, the end vertex of the previous edge is the start vertex of the current edge. If we don't, then we're lifting our pencil from the paper. This is very easy to express:

virtual class drawer;
  constraint choose_connected_edges {
    foreach (edge_being_drawn[i])
      if (i > 0)
        edge_being_drawn[i].v1 == edge_being_drawn[i - 1].v2;
  }
endclass

Let's test it out by trying to draw a barn. Here's how the vertices are numbered:

barn

The barn_drawer class only needs to define the edges using the add_edge(...) function:

class barn_drawer extends drawer;
  function new();
    add_edge(0, 1);
    add_edge(0, 2);
    add_edge(1, 2);
    add_edge(1, 3);
    add_edge(1, 4);
    add_edge(2, 3);
    add_edge(2, 4);
    add_edge(3, 4);
  endfunction
endclass

We just need to randomize an instance of barn_drawer and we should get the instructions we need to solve our puzzle. Sadly, things are never this easy. Immediately after putting all constraints together I got a constraint violation. After looking at the "choose" constraints over and over and hitting my head on the table, some time later I found what the problem was; it wasn't in my code. As in the first installment of the series, when solving Sudoku, a simulator bug reared its ugly head, but this time it wasn't as easy to pinpoint. I should probably consider moonlighting as a QA for an EDA company since I seem to draw such issues to me. Getting to the point, if we add this slight modification to the choose_unique_edges constraint it's going to make the clouds go away:

virtual class drawer;
  constraint choose_unique_edges {
    // ...

    foreach (edge_being_drawn[i])
      foreach (edge_being_drawn[j])
        // (Very) Possible bug in simulator
        if (i == j - 1)
          edge_being_drawn[i].v1 != edge_being_drawn[j].v2;
        else if (j == i - 1)
          edge_being_drawn[j].v1 != edge_being_drawn[i].v2;
        else

        // This condition should be enough by itself.
        if (i != j)
          !(edge_being_drawn[i].v1 == edge_being_drawn[j].v2 &&
            edge_being_drawn[i].v2 == edge_being_drawn[j].v1);
  }
endclass

And there we have it! Now we can solve any such "draw this without lifting your pencil" puzzle. We've also learned a bit more about the limitations of the SystemVerilog constraint language. I can't help thinking that the whole thing would have been much cleaner in e. I might try it out in the future just to see. If someone else does it, it would be nice to compare. In the meantime, you can find the code on SourceForge if you want to experiment drawing other figures.

Sunday, April 12, 2015

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.

Sunday, April 5, 2015

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.