Constraint Pre-processing

Concept

Constraint pre-processing is the software-based first step of a two-step methodology for hardware-accelerated constrained random test generation. In this step, the constraints over a set of variables are analysed and decomposed, in software, into a finite collection of entailed regions (strips and their overlapping constraint sets, with associated weights), which are then used by a subsequent hardware stage to perform random value selection under the constraints.

First seen 7/7/2026

Last seen 7/7/2026

Evidence 4 chunks

Wiki v1

WIKI

Constraint Pre-processing

Overview

Constraint pre-processing is a software-based computation stage that lies at the heart of the two-step constrained random synthesis methodology introduced for hardware-accelerated constrained random test generation. Its purpose is to analyse the constraints imposed on a set of random variables and to decompose their joint solution space into a finite number of entailed regions. The pre-computed structure of these regions is then handed to a hardware stage that performs actual random value selection within very few cycles, with modest area overhead.

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

Hardware accelerated constrained random test generation ← uses 100% 2e

The paper uses constraint pre-processing in software as the first step of its methodology.

two-step constrained random synthesis ← uses 100% 1e

The two-step methodology uses constraint pre-processing as its first step.

LINKED ENTITIES

2 links

Hardware accelerated constrained random test generation USES Extracted graph relationship

two-step constrained random synthesis USES Extracted graph relationship

CITATIONS

7 sources

7 citations — click to expand

[1] Constraint pre-processing is the software first step of a two-step approach in which constraints are pre-processed in software to generate entailed regions, and random value selection is then performed in hardware using those pre-computed regions. Hardware accelerated constrained random test generation

[2] The pre-processing stage decomposes the solution space into a finite number of entailed regions (strips) by computing bounds (convex polygon vertices), computing strips and their overlapping constraint sets, and computing per-strip probability weights. Hardware accelerated constrained random test generation

[3] Vertices of the convex solution polygon are computed using standard methods together with the ILOG CPLEX ILP solver. Hardware accelerated constrained random test generation

[4] A strip is defined as the region bounded by [x_j, x_{j+1}] where x_j < x_{j+1} and no other vertex v has x-coordinate strictly between them, and its overlapping constraint set (OCS) consists of the constraints of the convex polygon that cross the strip. Hardware accelerated constrained random test generation

[5] The OCS of any strip produced by this procedure always has cardinality 2, which is exploited during the subsequent hardware synthesis step to generate solution points. Hardware accelerated constrained random test generation

[6] Each strip is assigned a weight proportional to an estimate of the total volume of the solution space projected onto that strip, because 2D strip area does not directly reflect solution-point density. Hardware accelerated constrained random test generation

[7] The two-step approach produces constraint-satisfying random valuations in hardware within very few cycles with modest area overhead, and has been demonstrated on test-bench architectures for the ARM AMBA Bus and IBM CoreConnect protocol suites. Hardware accelerated constrained random test generation