Constrained Random Value Selection

Problem Statement

Given a set of variables and a set of constraints over these variables, the goal is to synthesise a circuit in hardware that deterministically generates pseudo-random valuations of these variables subject to the given constraints. The aim is to develop a tool that performs this synthesis from a given system of constraints.

Two notable features characterise the problem:

1. The constraints are known a priori, because they are hard-coded in the test bench.
2. The generated circuit must guarantee that all valuations satisfying the constraints have a non-zero probability of being selected.

Because the constraints are known a priori, the solution space can be precomputed in software and then carried into hardware as a set of simpler constraints that drive random value selection at runtime.

Motivation

Verification engineers routinely use constrained random test benches, but the general constraint satisfaction problem over real-valued variables is notoriously complex and difficult to implement efficiently in hardware. In practice, however, the constraints used in such test benches are usually simple:

• Range constraints, which specify the range of individual variables.
• Two-variable constraints, in which the value of one variable is constrained to be within a given range of another variable (for example, a randomly generated address constrained within some offset of a base address).

Constraints involving more than two variables are rare in practice. The authors report that across the full test-bench architectures for ARM AMBA, IBM CoreConnect (IBMCC), and PCI Bus, no single constraint involved more than two variables, even though many variables were constrained.

These practical observations justify targeting systems of linear constraints where each constraint involves at most two variables, and exploit the fact that the constraints are hard-coded so the constraint set can be simplified prior to hardware-accelerated simulation.

Two-Step Methodology

The methodology for hardware-accelerated constrained random value selection works in two steps:

Step 1 — Constraint Pre-processing in Software

A software step uses an integer linear programming (ILP) solver to deduce a set of regions covering the constraint-satisfying valuations. Because this step is executed only once in software before emulation begins, its complexity is not a major issue and sophisticated algorithms can be afforded.

The pre-computed solution region is stored in a well-defined data structure that the hardware step can consume.

Step 2 — Constrained Random Selection in Hardware

A constrained random test generator is synthesised in hardware. This circuit uses a pseudo-random generator based on a linear feedback shift register (LFSR) together with constraint-specific circuitry that constrains the generator to remain within the regions entailed by the first (software) step.

The main design challenge is that the entailed regions produced by the first step must be in a form that the second step can use efficiently, both in terms of:

• the number of clock cycles required to produce each random valuation, and
• the area overhead of the generating circuit.

Illustrative Example

Consider a bus connecting a Master device to two Slave devices. The address space of the slaves is [0, 1023], where Slave_1 occupies [0, 511] and Slave_2 occupies [512, 1023]. For slave-specific tests, a test bench modelling the Master must constrain the values of base and offset to produce addresses within the desired range.

A representative SystemVerilog constrained-random test-bench fragment is:

class MDriver;
    rand bit [9:0] base;
    rand bit [4:0] offset;
    ...
    task main_t ();
        ...
        case (MasterState)
            ...
            'AnySlave: begin
                ...
                success = TB.randomize() with {
                    base >= 0 && offset >= 0 &&
                    (base + offset)       <= 511  &&
                    (base + 2*offset)     <= 1023 &&
                    (base + 2*offset)     >= 512;
                };
            end
            ...
        endcase
    endtask
endclass

The first step computes the solution region for these constraints in software; the second step synthesises hardware that, using an LFSR-based pseudo-random generator, selects random (base, offset) valuations strictly within that region.

Relation to Hardware-Accelerated Constrained Random Test Generation

Constrained random value selection is the central piece of hardware-accelerated constrained random test generation: by moving the randomised selection of stimulus variables into synthesised hardware, test benches execute orders of magnitude faster than in pure-software simulation, while preserving the non-zero-probability requirement over all satisfying valuations.