Skip to content
STIMSMITH

BDD-based Constraint Solving

Technique WIKI v2 · 9/27/2026

BDD-based constraint solving is a constrained-random stimuli generation technique that builds a Binary Decision Diagram representing the feasible solution space of a set of constraints. It is valued because, once built, a BDD can produce solutions with a uniform distribution over that space. The cited evidence positions BDD-based solving as one tier of a multi-solver architecture (used in eUVM for medium-complexity multi-domain constraints and in CRAVE as part of a portfolio with SAT/SMT), and contrasts it with SAT-only approaches such as PyVSC.

Overview

BDD-based constraint solving is a constrained-random verification technique in which a Binary Decision Diagram (BDD) is constructed to represent the satisfying assignments of a set of constraints. The cited evidence frames it as one tier within multi-solver constrained-random verification flows rather than as a universal replacement for SAT or SMT solving.

Strengths and Limits

The evidence highlights a key property of BDD-based solving for constrained-random verification (CRV): if a BDD can be built for the overall constraint, a uniform distribution among all solutions can be guaranteed. This makes BDD-based solving attractive whenever predictable stimulus quality is required.

However, the same source notes that it is "in general not possible to know in advance which type of constraint-solver will show the best performance," and that alternative engines based on Boolean Satisfiability (SAT) or Satisfiability Modulo Theories (SMT) have shown "very good results for constraints which are hard to solve for BDDs." [1]

Role in eUVM

In the cited DVCon paper on eUVM, BDD-based solvers occupy a middle tier in a three-tier multi-solver strategy:

  1. Native constraint solver — handles elementary single-domain constraints.
  2. BDD-based solvers — handle multi-domain constraints of medium complexity.
  3. SMT/SAT solvers — handle convoluted constraints that cannot be handled by BDDs (Z3, Boolector, and CMSGen are named as examples in the paper).

The paper also states that eUVM uses D-language metaprogramming capabilities such as User-Defined Attributes, Compile-Time Function Evaluation, code introspection, and generative programming to implement a high-performance constraint processor, with compile-time parsing and analysis of constraints attributed to code introspection and CTFE. [2]

Portfolio Use in CRAVE

CRAVE applies BDD-based solving as part of a portfolio constraint-solving architecture that runs a BDD-based constraint-solver and an SMT-based constraint-solver in parallel on the same set of constraints, with the goal of "very fast generation of constraint solutions." [3]

In the 2012 SoC CRAVE paper, the integration is described as follows:

  • The metaSMT framework is used as a unified interface, so that "no algorithmic changes are necessary when switching to another solver." [1]
  • The BDD-based engine is connected through CUDD, and AIGER appears in the metaSMT backend; the SMT side includes SWORD, Z3, Boolector, MiniSAT, and PicoSAT. [1]
  • Rather than picking the fastest solver per case, CRAVE prefers the BDD because of the uniform-distribution guarantee: the SMT solver is "run only until the BDD is built," and from that point on "only the BDD is used and execution the SMT solver is stopped." [1]

The CRAVE public page additionally lists "Parallel constraint-solving" as a feature, noting that "BDD-based and SAT/SMT-based techniques have been integrated for constraint-solving. A portfolio approach is used to enable very fast generation of constraint solutions." [3]

Comparison with SAT-only Solving in PyVSC

The eUVM paper contrasts BDD-based solving with PyVSC, which is described as not deploying a BDD solver and instead relying completely on SAT solvers for multi-variable constraints. As a consequence, the paper reports that PyVSC's generated solutions tend to have a non-uniform spread compared with SystemVerilog and eUVM. [4]

Practical Boundary

The evidence does not present BDD-based constraint solving as a universal replacement for SMT/SAT solving. Instead, it describes a boundary:

  • BDD-based solvers are preferred when a BDD can be built for the overall constraint, because uniform distribution among solutions can be guaranteed.
  • Constraints that are hard for BDDs are delegated to SAT/SMT engines, either as a fallback tier (eUVM) or via a parallel portfolio (CRAVE).

The same source additionally notes that, at the time of the DVCon paper, CRAVE could not handle complex RISC-V-DV constraints. [4]

LINKED ENTITIES

1 links
CRAVE USES

CITATIONS

5 sources
5 citations
[1] CRAVE integrates BDD-based and SAT/SMT-based techniques for constraint-solving using a portfolio approach to enable very fast generation of constraint solutions. CRAVE - Institute for Computer Science, JKU Linz
[2] CRAVE uses a portfolio approach running an SMT-based and a BDD-based constraint-solver in parallel on the same constraints, and prefers the BDD once it is built because it guarantees a uniform distribution among all solutions; metaSMT is used as a unified engine-independent interface. CRAVE: An Advanced Constrained Random Verification Library (SoC 2012 paper)
[3] The CRAVE metaSMT backend exposes both BDD-related engines (CUDD, AIGER) and SAT/SMT engines (SWORD, Z3, Boolector, MiniSAT, PicoSAT), and CRAVE's constraint analyzer resolves contradictions formally. CRAVE: An Advanced Constrained Random Verification Library (SoC 2012 paper)
[4] In eUVM, BDD-based solvers handle multi-domain constraints of medium complexity, while a native solver handles elementary single-domain constraints and SMT/SAT solvers handle convoluted constraints that BDDs cannot handle (Z3, Boolector, CMSGen named as examples); compile-time parsing and analysis of constraints are attributed to D-language code introspection and CTFE. eUVM DVCon paper (previous article source chunks)
[5] PyVSC is described as not deploying a BDD solver and instead relying completely on SAT solvers for multi-variable constraints, resulting in a non-uniform spread of solutions compared with SystemVerilog and eUVM; at the time of the paper, CRAVE could not handle complex RISC-V-DV constraints. eUVM DVCon paper (previous article source chunks)

VERSION HISTORY

v2 · 9/27/2026 · minimax/minimax-m3 (current)
v1 · 5/26/2026 · gpt-5.5