Binary Decision Diagram (BDD) Solver

A Binary Decision Diagram (BDD) Solver is a constraint-solving backend discussed in the context of hardware-verification constrained randomization. In the provided evidence, BDD solvers appear primarily as an alternative or complement to SAT solvers for solving multi-variable constraints in verification test generators and constrained-random libraries.^[1]

Overview

BDD solvers are relevant to verification environments that need to generate randomized test stimuli subject to constraints. The evidence contrasts two approaches:

• SAT-only constraint solving, as used by PyVSC in Pygen.
• Integrated BDD/SAT solving, as exposed by the CRAVE constrained-random library used with SystemC.^[1]

The evidence links the absence of a BDD solver in PyVSC to poorer distributional behavior for generated solutions: PyVSC “relies completely on Satisfiability (SAT) solvers for solving multi-variable constraints,” and its solutions are described as having a “non-uniform spread” compared with SystemVerilog and eUVM flows.^[1]

Role in constrained random verification

In constrained random verification, a solver must choose values for random variables while satisfying user-defined constraints. This is used, for example, in instruction generators such as RISCV-DV and its Python port Pygen.^[1]

The evidence identifies solver choice as a performance and quality factor:

^[1]

PyVSC and Pygen

Pygen, the Python-based open-source port of RISCV-DV, uses PyVSC for constraint solving.^[1] According to the evidence, PyVSC does not deploy a BDD solver and instead depends entirely on SAT solvers for multi-variable constraints.^[1]

The reported consequences are:

• Pygen has poor runtime performance.
• Pygen is more than 100× slower than the SystemVerilog version of RISCV-DV.
• It generates fewer than 100 random RISC-V instructions per second.
• Its generated solutions have a less uniform spread than those from SystemVerilog and eUVM flows.^[1]

These claims are made in the broader context of Python’s performance limitations for verification workloads, where Python is described as an interpreted scripting language benchmarked as much slower than native C/C++ implementations.^[1]

CRAVE and SystemC

The CRAVE library, used by the SystemC port of UVM, provides an integrated interface to both BDD and SAT solvers for constrained randomization.^[1] This makes CRAVE an example of a library architecture where BDD solving is available alongside SAT solving.

However, the evidence also reports important limitations:

• CRAVE cannot currently handle complex RISCV-DV constraints.
• SystemC and CRAVE do not offer multicore parallelism support.
• CRAVE represents random variables using wrapper template types such as crv_variable<int>, so random variables do not retain their native memory footprint.^[1]

These limitations reduce CRAVE’s practical effectiveness for the complex constrained-random workloads described in the evidence.

Technical significance

Within the provided evidence, BDD solvers are significant because their presence or absence is associated with the quality and capability of constrained-random solving flows:

1. Solution distribution
   The absence of a BDD solver in PyVSC is associated with non-uniform solution spread compared with SystemVerilog and eUVM.^[1]

2. Solver integration strategy
   CRAVE demonstrates a hybrid architecture that exposes both BDD and SAT solvers through an integrated interface.^[1]

3. Constraint complexity limits
   Even with BDD/SAT integration, CRAVE is reported as unable to handle complex RISCV-DV constraints, showing that merely providing a BDD backend is not sufficient for all industrial verification workloads.^[1]

Limitations noted in the evidence

The evidence does not provide an internal algorithmic description of BDD solving. Instead, it discusses BDD solvers operationally, as constraint-solving backends in verification libraries. It also does not prove that BDD solving alone guarantees uniform randomization; it only reports that PyVSC’s lack of a BDD solver coincides with less-uniform results compared with SystemVerilog and eUVM.^[1]

References

^[1]: Evidence fee25bd9-f843-4d6f-8f5b-6a9e450d09bd.