Living without a constraint solver

For a while I was hooked on constraint solvers, to the point I relied on them to solve even the most simplistic problem, paying a hefty price in simulation time. One of those simple problems is selecting values from a list. The typical wrong way to do this is with the constraint solver. You’d usually declare a constraint like this:

class A {
  rand integer thing;
  constraint my_con {
    thing in {7,8,34};
  }
}

Obviously, this is short and sweet, but picking a value for the “thing” variable invokes the constraint solver. It is much more efficient to approach the problem by randomly picking from a list:

integer things[] = [7,8,34];
thing = things[random()%things.length];

A variant of that is when we want to pick a sequence of things, without repetition. Once we’ve gone through the sequence, we want to shuffle it and start over. I coded the following in D, to demonstrate:


import tango.io.Stdout;
import tango.math.Random;

// The Knuth Shuffle (from wikipedia)
void shuffle(int [] list) {
  auto rand = new Random();
  int n = list.length;
  while (--n > 0) {
    int k = rand.next(n+1);
    int temp = list[n];
    list[n] = list[k];
    list[k] = temp;
  }
}

class Buffer {
  int size;
  byte [] data;
  this(int size) {
    this.size = size;
  }
}

void main() {
  // Some buffers with interesting sizes
  Buffer [] buffers;
  buffers.length = 3;
  buffers[0] = new Buffer(7);
  buffers[1] = new Buffer(8);
  buffers[2] = new Buffer(34);

  // A list of numbers
  int [] list;
  list.length = buffers.length;
  foreach(idx, ref value;list) value = idx;
  shuffle(list);

  // Use the shuffled list to traverse
  // the list of buffers in random order
  foreach(idx,value;list) {
    Stdout.formatln(
      "buffers[{0}].size = {1}",
      idx,
      buffers[value].size
    );
  }
}

Shuffling the list is a O(n) operation, and there is no need to invoke a constraint solver. Each time you need to go through a list of things in random order, you can use the shuffled list of integers to traverse it.

Scoreboards and discards

A common difficulty in ASIC Verification is how to scoreboard packet discards. Malformed packets, tail drops (or RED), and the impossible task of being cycle accurate with the internal state of the ASIC make it virtually impossible for a scoreboard to predict what the outcome will be in the presence of saturated queues, error injection and other DUT internal states: will the packet make it, or will it get dropped? Trying to predict the output response is a game you lose before it even starts. Instead try to realize the truth: there is no spoon… er… the scoreboard does not have to predict the outcome, it only has to do the accounting.

For all types of discards except RED, the packet generator is the VC that knows what will happen to the packet. When the packet generator inserts a bogus TCP checksum, it knows the packet will be discarded for this reason. So instead of relying on the scoreboard to parse the packet and re-discover what the packet generator already knew, the scoreboard simply has to look up the packet in a table to know how to account for the packet. And you guessed it, that lookup table has been filled out by the packet generator.

The mechanics of filling out the packet table is simple as hashing on a property of the packet or on the entire packet, and storing or retreiving any information you need regarding the packet: it’s final destination, how it should be routed, whether it is expected to be discarded, if it should be segmented, if it will be discarded and why, etc. All the scoreboard has to do it look up the packet in the table, retreive the associated information, and increment a counter. When the simulation ends, simply check if all the packets have been accounted for by comparing the scoreboard counts with the packet generator counts and the DUT’s internal counters. If the DUT says it discarded 10 packets because of RED, the scoreboard knows that it will be off by 10 when it tries to balance the counts.

Don’t ask the scoreboard to predict outcomes, it’s too hard and it’s not the right place.