Constrained random simulation
Constrained random simulation is a technique used in hardware verification. It requires the random generation of input stimuli that obey a set of declaratively specified input constraints; the resulting stimuli are then applied in simulation to validate given design properties.[1]
The cited source describes constrained random simulation as the main workhorse of today's hardware verification flows.[1] In this workflow, two factors are highlighted as especially important to overall efficiency:[1]
- the performance of the constraint solver
- the distribution of the generated solutions
The same source frames the problem as one of efficient constraint solving for stimulus generation over mixed Boolean/integer variable domains, and proposes a hybrid solver based on Markov-chain Monte Carlo methods as one approach with good performance and distribution.[1]
Key aspects
- Randomized stimulus generation: stimuli are generated randomly rather than enumerated manually.[1]
- Constraint-driven inputs: generated stimuli must obey declaratively specified input constraints.[1]
- Simulation-based validation: the generated inputs are used to validate design properties by simulation.[1]
- Solver and distribution quality matter: effectiveness depends not only on the performance of the constraint solver, but also on how the generated solutions are distributed across the solution space.[1]
- Mixed Boolean/integer domains: the underlying constraint-solving problem can involve both Boolean and integer variables, motivating hybrid solution techniques such as Markov-chain Monte Carlo methods.[1]
Related Work context (EWDTS 2018)
Random stimuli generation is described as an important process for checking the correct behavior of various circuits, where stimuli may range from binary values on simple circuit pins to a complex program in the data memory of a processor.[2] The related-work section notes that the current trend in stimulus generation focuses primarily on more complex circuits (such as processors), for which it is nontrivial to construct a valid stimulus; simpler stimuli, including test vectors, can be generated directly in the simulation environment (e.g., Modelsim from Mentor Graphics) or via an external tool.[2]
The same source observes that a number of specific stimuli generators exist for application-specific integrated circuits (ASICs), digital signal processors (DSPs), protocol interfaces, FPGA converters, and similar targets, but these tools and their approaches are complex and limited to a particular system.[2] It positions a universal stimuli generator (e.g., the MicroGP tool) as one alternative that not only generates stimuli but also finds the most optimal solution of hard problems.[2]
That work introduces a framework based on a probabilistic constrained grammar (PCG), built on a probabilistic (stochastic) context-free grammar extended with restrictive conditions (constraints) that dynamically change the probabilities of production rules during generation, and uses the arithmetic-logic unit (ALU) as a test case for generating both input stimuli and expected output.[2]
Scope of the evidence
The available evidence characterizes constrained random simulation primarily through its role in hardware verification and stimulus generation, the importance of constraint-solver performance and solution distribution, and its applicability to mixed Boolean/integer domains. Supporting evidence also situates it within broader random stimuli generation research for circuits ranging from simple test vectors to processors and ALUs.