BDD Constraint Solver

Concept

A constraint solving mode available in the Synopsys VCS constraint solver that elaborates the entire solution space of a SystemVerilog randomize() call before selecting a value, then caches that solution space to accelerate subsequent calls. It is best suited to constrained-random problems of moderate size that are invoked many times, such as CPU opcode generation, and is one of two solver modes exercised by the VCS Constraint Profiler and by Hierarchical Constrained-Random Stimulus Generation flows.

First seen 6/5/2026

Last seen 6/5/2026

Evidence 1 chunks

Wiki v1

WIKI

Overview

The BDD Constraint Solver is a solving mode within the Synopsys VCS constraint solver that uses a Binary Decision Diagram (BDD) representation of a randomize() call's constraint system. It is the alternative to the default RACE solver mode and is exposed to users through the VCS constrained-random verification flow. Its defining behavior, performance profile, and applicability are documented in case studies of CPU/microcode stimulus generation, most notably the AMD microcode stimuli work published on Design & Reuse.

How It Works

READ FULL ARTICLE →

NEIGHBORHOOD

No graph connections found for this entity yet. It may appear in future ingestion runs.

explore full graph →

RELATIONSHIPS

2 connections

VCS Constraint Profiler ← uses 88% 1e

The profiler provides details about BDD solver memory usage.

hierarchical constrained-random stimulus generation ← uses 88% 1e

The hierarchical approach can use the BDD solver for constraint solving.

LINKED ENTITIES

2 links

VCS Constraint Profiler USES Extracted graph relationship

hierarchical constrained-random stimulus generation USES Extracted graph relationship

CITATIONS

10 sources

10 citations — click to expand

[1] The BDD solver elaborates the entire solution space of the randomize call before selecting a solution. Generating AMD microcode stimuli using VCS constraint solver

[2] Elaborating the entire solution space can take large amounts of memory, and the solver must spend some time elaborating the entire solution space. Generating AMD microcode stimuli using VCS constraint solver

[3] The solution space is cached to speed up subsequent randomization calls. Generating AMD microcode stimuli using VCS constraint solver

[4] The BDD solver works well for specific architectures, particularly if the randomize problem does not take excessive memory and the same randomize call occurs many times, as is often the case with CPU opcode generation. Generating AMD microcode stimuli using VCS constraint solver

[5] The VCS 2009.12 release provided a testcase extraction feature to extract the slowest partition from each randomize call automatically. Generating AMD microcode stimuli using VCS constraint solver

[6] The default RACE solver shows a 4x speedup, while the BDD solver shows a 2x speedup when moving from a single-class to a multiple-class architecture. Generating AMD microcode stimuli using VCS constraint solver

[7] Memory requirements were significantly better with the multiple-class architecture, and memory results were measured for the BDD solver only because RACE memory use is typically smaller and not a limiting factor. Generating AMD microcode stimuli using VCS constraint solver

[8] The multiple-class implementation had 7x fewer constraints than the original, allowing the solver to calculate solutions more efficiently. Generating AMD microcode stimuli using VCS constraint solver

[9] Randomizing instructions by first choosing the opcode category significantly simplified the problem; the constraint solver had a smaller problem to consider because only constraints specific to the opcode category were present. Generating AMD microcode stimuli using VCS constraint solver

[10] VCS Constraint Profile reports cumulative randomize CPU runtime, individual randomize CPU runtime, individual partition CPU runtime, and memory data; the memory data is particularly useful when the BDD solver is used. Generating AMD microcode stimuli using VCS constraint solver