Definition

In the provided constraint-random verification context, a constraint solver solution space is the complete set of candidate solutions associated with a randomize call. When the VCS BDD solver is used, it elaborates the entire solution space of the randomize call before choosing a solution.

Role in solver behavior

The solution space directly affects solver runtime and memory use. Elaborating the entire solution space can consume large amounts of memory, and the solver must also spend time building that solution space before it can select a result. To reduce the cost of repeated calls, the solution space is cached so that later randomization calls can be faster.

This behavior makes the BDD solver useful for some architectures, especially when the randomize problem does not require excessive memory and the same randomize call is executed many times. The cited example notes CPU opcode generation as a case where repeated randomize calls commonly occur.

Performance implications

The size of the randomization problem is a major factor in solution-space cost. In the cited AMD microcode-stimulus article, a multiple-class architecture reduced the number of active variables and constraints compared with a single-class architecture. The newer implementation had 7x fewer constraints, allowing the solver to compute solutions more efficiently.

The same comparison reported improved runtime and memory behavior. For two opcode randomization tests, the multiple-class architecture was faster with both solvers: the default RACE solver showed a 4x speedup, while the BDD solver showed a 2x speedup. Memory requirements were also significantly better for the multiple-class architecture in the BDD-solver measurements.

Architectural guidance

The evidence suggests that reducing the number of constraints and variables visible to a randomize call can reduce the cost of elaborating and solving the solution space. One effective strategy in the cited opcode-generation case was to choose the opcode category first, so that only constraints specific to that category were present. This simplified the solver problem and improved speed and memory while preserving distribution and test-level control.

Practical profiling considerations

The cited VCS flow used constraint profiling to inspect CPU runtime and memory behavior for randomize calls and partitions. Profiling was used to identify slow randomize results for two opcodes, then isolate them in a smaller testbench for solver comparison. The VCS 2009.12 release also provided testcase extraction for automatically extracting the slowest partition from each randomize call.