Skip to content
STIMSMITH

Solution Space Elaboration

Concept WIKI v1 · 5/24/2026

**Solution space elaboration** is a constraint-solving behavior in which a solver constructs the full set of legal solutions for a `randomize` call before choosing one solution. In the cited VCS/SystemVerilog constraint-random context, this behavior is specifically associated with the **BDD solver**, which “elaborates the entire solution space of the randomize call before selecting a solution.” [9dce017b-1bb8-4e8e-8b45-0d14653a98c1]

Solution Space Elaboration

Solution space elaboration is a constraint-solving behavior in which a solver constructs the full set of legal solutions for a randomize call before choosing one solution. In the cited VCS/SystemVerilog constraint-random context, this behavior is specifically associated with the BDD solver, which “elaborates the entire solution space of the randomize call before selecting a solution.” [1]

Context

In constrained-random verification, a randomize call is governed by variables and constraints. The solver must find values that satisfy the active constraints. With the BDD solver mode described in the evidence, the solver first builds the entire solution space, then selects a valid solution from that space. [1]

This differs from approaches that do not necessarily materialize the full solution space up front. The evidence contrasts the BDD solver with the default RACE solver in runtime and memory measurements, noting that RACE memory consumption is typically smaller and was not the limiting factor in the reported comparison. [1]

Performance Characteristics

Solution space elaboration has two major performance implications:

  1. Memory cost — Elaborating the entire solution space can require large amounts of memory. [1]
  2. Initial runtime cost — The solver must spend time constructing the full solution space before selecting a result. [1]

However, the elaborated solution space may be cached, which can speed up later calls to the same randomization problem. [1]

When It Works Well

The BDD solver approach is described as effective for specific architectures, especially when:

  • the randomize problem does not consume excessive memory, and
  • the same randomize call is executed many times. [1]

The evidence identifies CPU opcode generation as a common case where repeated randomization calls may make this approach useful. [1]

Profiling and Diagnostics

The cited material discusses VCS constraint profiling data for CPU runtime and memory. The profiling views include:

  • cumulative randomize CPU runtime,
  • individual randomize CPU runtime,
  • individual partition CPU runtime, and
  • memory data. [1]

Memory profiling is especially important when using the BDD solver, because full solution space elaboration can become memory-intensive. [1]

The VCS 2009.12 release also provided a testcase extraction feature that could automatically extract the slowest partition from each randomize call, helping isolate expensive constraint-solving cases. [1]

Optimization Strategy: Reduce the Active Constraint Set

The evidence describes an x86 opcode generation case where architecture choices strongly affected solver performance. A single-class constrained-random implementation solved distribution problems but reached speed and memory limits because of the complexity of the x86 instruction set. [1]

A revised implementation first selected the opcode category, then randomized using only the constraints relevant to that category. This reduced the size of the solver problem because only category-specific constraints were active. [1]

The reported benefits included:

  • faster runtime,
  • lower memory usage,
  • preserved distribution control, and
  • preserved test-level control. [1]

The new implementation had 7× fewer constraints than the original, enabling the solver to compute solutions more efficiently. [1]

Reported Results

In the opcode-generation comparison, the multiple-class architecture was faster than the single-class architecture with both solvers and for both tested opcodes. The default RACE solver showed a 4× speedup, while the BDD solver showed a 2× speedup. [1]

Memory requirements were also significantly better for the multiple-class architecture. The evidence reports memory results for the BDD solver only, because RACE memory use was typically smaller and not the limiting factor. [1]

Practical Guidance

For designs using solution space elaboration:

  • Keep each randomize problem as small as practical.
  • Avoid presenting the solver with irrelevant variables and constraints.
  • Partition randomization by category when only a subset of constraints is applicable.
  • Use profiling to identify expensive randomize calls and partitions.
  • Prefer BDD-style elaboration when repeated calls can benefit from cached solution spaces and memory use remains acceptable. [1]

References

  • [1] Evidence excerpt discussing VCS constraint profiling, BDD solver solution space elaboration, memory/runtime behavior, and opcode-generation performance results.