Skip to content
STIMSMITH

VCS BDD Solver

Tool WIKI v1 · 5/25/2026

The VCS BDD Solver is a VCS constraint-solver mode described for constrained-random stimulus generation. In this mode, the solver elaborates the entire solution space of a randomize call before selecting a solution, which can improve repeated randomization performance through caching but can require substantial memory. Evidence from an AMD microcode stimulus-generation study indicates that the BDD solver is best suited to constrained-random architectures where the randomize problem fits in memory and the same randomize call is executed many times, such as CPU opcode generation.

Overview

The VCS BDD Solver is a constraint-solver mode used in VCS constrained-random randomization flows. In BDD mode, the solver elaborates the entire solution space for a randomize call before choosing a solution. This full elaboration can consume large amounts of memory and also requires time up front, but the resulting solution space is cached to accelerate later calls to the same randomization problem. [C1]

Operating model

The solver’s key behavior is whole-solution-space elaboration before selection. This makes the approach sensitive to the size of the randomize problem: if the problem is too large, memory and elaboration time can become limiting factors. If the same randomize call is repeated many times, however, the cached solution space can make the BDD solver effective. The cited study specifically notes that this pattern often occurs in CPU opcode generation. [C1]

Profiling and diagnostics

The evidence describes VCS constraint-profile data for CPU runtime and memory, including cumulative randomize CPU runtime, individual randomize CPU runtime, individual partition CPU runtime, and memory data. These profiles were highlighted as especially useful for the BDD solver because its solution-space elaboration can require substantial memory. [C2]

The VCS 2009.12 release also provided a testcase extraction feature that could automatically extract the slowest partition from each randomize call, supporting focused analysis of expensive constraint-solving partitions. [C3]

Performance characteristics

In the AMD microcode stimulus-generation study, researchers compared a single-class architecture with a multiple-class architecture by using profile data to identify randomize results for two opcodes, then building a small testbench that randomized those opcodes repeatedly. This isolated solver CPU-time measurements from other testbench effects. [C4]

The multiple-class architecture was faster with both the default RACE solver and the BDD solver. In the reported runtime comparison, the default RACE solver showed a 4x speedup, while the BDD solver showed a 2x speedup. [C5]

Memory behavior

The same study reported significantly improved memory requirements for the multiple-class architecture. Memory measurements were reported for the BDD solver only because RACE memory use was typically smaller and not the limiting factor. [C6]

The main reason for the speed and memory improvement was a smaller set of variables and constraints in the revised implementation. Profile data showed that the new implementation had 7x fewer constraints than the original, allowing the solver to calculate solutions more efficiently. [C7]

Recommended usage pattern

Based on the evidence, the BDD solver is most appropriate when:

  • the randomize problem does not require excessive memory;
  • the same randomize call occurs many times;
  • solution-space caching can amortize elaboration cost across repeated calls; and
  • the stimulus architecture reduces the active variable and constraint set, such as by first choosing an opcode category so that only category-specific constraints are present. [C1][C7][C8]

Architectural implication

For x86 opcode stimulus generation, serial randomization achieved speed and memory goals but produced skewed distribution because it generated each opcode portion serially and could not control the overall distribution. A simple constrained-random approach corrected the distribution issue but ran into speed and memory limits due to the complexity of the x86 instruction set. The study found that first choosing the opcode category simplified the constraint problem because the solver only had to consider constraints specific to that category, improving memory and speed without sacrificing distribution or test-level control. [C8]

CITATIONS

8 sources
8 citations
[1] In BDD mode, the solver elaborates the entire solution space of a randomize call before selecting a solution; this can use large amounts of memory and time, and the solution space is cached for subsequent randomization calls. Generating AMD microcode stimuli using VCS constraint solver
[2] VCS constraint-profile outputs described in the evidence include CPU runtime and memory views, and memory profiling is particularly useful for BDD mode because of solution-space elaboration. Generating AMD microcode stimuli using VCS constraint solver
[3] The VCS 2009.12 release provided testcase extraction to automatically extract the slowest partition from each randomize call. Generating AMD microcode stimuli using VCS constraint solver
[4] The performance comparison used profile data to identify randomize results for two opcodes and a small testbench that randomized the opcodes repeatedly to isolate solver CPU time. Generating AMD microcode stimuli using VCS constraint solver
[5] The multiple-class architecture was faster with both solvers; RACE showed a 4x speedup and the BDD solver showed a 2x speedup. Generating AMD microcode stimuli using VCS constraint solver
[6] Memory requirements were significantly better with the multiple-class architecture, and memory was measured only for BDD because RACE memory was typically smaller and not limiting. Generating AMD microcode stimuli using VCS constraint solver
[7] The acceleration and memory decrease came mainly from fewer variables and constraints; the new implementation had 7x fewer constraints than the original. Generating AMD microcode stimuli using VCS constraint solver
[8] For x86 opcode generation, serial randomization had distribution problems, simple constrained randomization hit speed and memory limits, and choosing the opcode category first reduced the active constraints and improved memory and speed without sacrificing distribution or test-level control. Generating AMD microcode stimuli using VCS constraint solver