Solve order and distribution bias

Count the legal combinations to predict how often each kind of transaction appears, change the mix with solve...before or dist, and measure the result.

Lesson: 5.3
Time: 25 min
Runs on: Verilator
Check: 5 questions

Writes were supposed to be half of the burst traffic, and every write is a single beat. The coverage report shows writes in only one burst in nine. The constraints are correct, and the solver is doing exactly what the standard asks. It picks evenly among all legal combinations of is_write and beats, and reads have eight legal lengths while writes have only one.

One write in nine bursts

One column per generated burst. Every burst is legal; the mix is the problem.

Count the legal combinations

Take the rules beats inside {[1:8]} and is_write -> beats == 1. They allow 9 combinations: one write, with 1 beat, and eight reads, with 1 to 8 beats.

The standard asks the solver to make every legal combination equally likely, unless a dist or a solve...before says otherwise. Each of the 9 pairs therefore has probability 1/9, so writes get 1/9 of the traffic and reads get 8/9.

Combination	Probability, no order	Probability, is_write chosen first
write, 1 beat	1/9 (11%)	1/2 (50%)
read, 1 beat	1/9	1/16
read, 2 beats	1/9	1/16
... each read length up to 8	1/9	1/16
all reads together	8/9 (89%)	1/2 (50%)

Expected probabilities for the nine legal combinations.

This bias appears whenever one value of a control field allows many more combinations than another. Real transactions make it larger: a read with 256 legal lengths and 64 legal IDs outweighs a write with one of each by a factor of 16,384.

For constraints too large to list, count per value of the control field: how many legal combinations does each value allow? The ratio of those counts is the ratio you will see in the traffic.

Choosing one field first with solve...before

solve is_write before beats; asks the solver to choose is_write first, as if beats did not exist yet, and only then to choose beats among the values that fit. Each value of is_write that has at least one legal partner is equally likely, so writes become half of the traffic.

Rules only

constraint legal {
  beats inside {[1:8]};
  is_write -> beats == 1;
}

Every legal pair is equally likely, so writes are 1/9 of the bursts.

Rules plus an order

constraint legal {
  beats inside {[1:8]};
  is_write -> beats == 1;
  solve is_write before beats;
}

The same nine legal pairs, but is_write is chosen first, so writes are 1/2.

An order changes probabilities only. The legal pairs stay the same nine, so solve...before can never make a failing call succeed or remove a legal pair.

Both fields named in solve...before must be rand; randc fields are not allowed there. An order gives only an even split between the values; for any other share, such as 30% writes, use a dist.

A dist on the control field lets you choose any share: is_write dist {1 := 1, 0 := 3}; asks for writes in one burst in four.

Measure the mix

Expected probabilities tell you what to look for; only counts show what your simulator produced. The example randomizes 300 bursts with no order and 300 with is_write chosen first, and tallies both.

Outcome	No order: expected	No order: measured	Write first: expected	Write first: measured
writes	33	33	150	150
reads, 1 beat	33	33	19	21
reads, 2 beats	33	34	19	15
reads, 3 beats	33	33	19	14
reads, 4 beats	33	33	19	21
reads, 5 beats	33	33	19	23
reads, 6 beats	33	34	19	24
reads, 7 beats	33	33	19	11
reads, 8 beats	33	34	19	21

Counts from the example on Verilator 5.052 with its default seed. Another simulator or seed gives different counts near the same expected values.

Both runs use the same class and the same rules. Only the way the kind of burst is chosen differs, so the change in the counts comes from the ordering alone.

Look at the right-hand column. The counts for single read lengths wander between 11 and 24 around an expected 19. That spread is normal for samples this small. So a test should check a share with room to spare, such as "writes are more than a quarter", never an exact count.

A few hundred calls are enough to tell 1 in 9 from 1 in 2, but not 50% from 45%. Decide how small a difference you need to see before you choose the number of calls.

What the standard fixes and what it leaves open

The standard fixes which values are legal, and it says how dist and solve...before shape the chances. It does not fix the random number generator, so the exact sequence of values and the exact counts differ between simulators, versions and seeds.

So write tests that depend on the rules, never on a particular random sequence. When you need an exact value, ask for it with randomize() with.

Bias of this kind is easy to miss, because every transaction is legal and no checker fires. A coverage count per kind of transaction, read early in the project, finds it: a kind that is rare or missing is the symptom.

Try it

With no order, writes are 33 of 300, almost exactly 1 in 9, and the eight read lengths share the rest evenly. With is_write chosen first, writes are 150 of 300 and each read length gets about 1/16 of the bursts.

Change n to 1000 and predict how the counts move. Then replace the second loop's with by with { is_write dist {1 := 1, 0 := 3}; } and predict the share of writes.

RUNVerilator · simulator service

Edit the code, then run it

Expected: no order: writes=33 reads=267 write first: writes=150 reads=150 reads by beats 1-8, no order: 33 34 33 33 33 34 33 34 reads by beats 1-8, write first: 21 15 14 21 23 24 11 21

Check yourself

Predict the outputEach number is 1 if writes made up less than a quarter of 200 bursts. Predict the exact output.

class burst_txn;
  rand bit          is_write;
  rand int unsigned beats;
  constraint legal { beats inside {[1:8]}; is_write -> beats == 1; }
endclass

module tb;
  burst_txn t = new;
  int n = 200;
  int w_free, w_first;
  bit w;
  initial begin
    repeat (n) begin
      if (!t.randomize()) $fatal(1, "randomize failed");
      w_free += t.is_write;
    end
    repeat (n) begin
      if (!std::randomize(w)) $fatal(1, "w failed");
      if (!t.randomize() with { is_write == w; }) $fatal(1, "randomize failed");
      w_first += t.is_write;
    end
    $display("%0d %0d", w_free * 4 < n, w_first * 4 < n);
  end
endmodule

Spot the bugAbout half of 200 bursts must be writes. Each option is the loop body that randomizes t, which has is_write -> beats == 1 and beats inside {[1:8]}. Which option gives far too few writes?

if (!std::randomize(w)) $fatal(1, "failed");
if (!t.randomize() with { is_write == w; }) $fatal(1, "failed");

if (!t.randomize()) $fatal(1, "failed");

if (!t.randomize() with { is_write dist {1 := 1, 0 := 1}; }) $fatal(1, "failed");

w = $urandom_range(1, 0);
if (!t.randomize() with { is_write == w; }) $fatal(1, "failed");

ConceptWith solve is_write before beats; added to the rules above, how likely is a read with exactly 3 beats?

1/2, because is_write is chosen first with even odds1/8, because reads have eight lengths to choose from1/16: reads get 1/2, shared among eight lengths1/9, the same as without the order

ConceptA call with certain inline constraints fails. Can adding solve is_write before beats; make it succeed?

Only if is_write is a randc fieldYes, if the order matches the order of the constraints in the classYes, because the solver tries more values when it follows an orderNo: an order changes probabilities, never which values are legal

ConceptA test with seed 42 gives 33 writes in 300 bursts on one simulator and 29 on another. What does that show?

Nothing wrong: the standard sets legality and odds, not the sequenceThe seed was ignored by one simulatorThe constraints are being solved in a different order on each simulatorOne simulator has a bug, because the same seed must give the same values

Remember

With no order and no dist, every legal combination of the random fields is equally likely.
A control value that allows more combinations appears more often; count the combinations to predict the mix.
solve a before b chooses a first, which changes probabilities but never which values are legal.
A dist on the control field sets its share directly.
Measure the mix and test shares with a margin; the exact counts belong to the simulator and seed.

Practice

Balance mode frequency Implement · Easy