Skip to content
STIMSMITH

Bi-variate Linear Constraints

Concept WIKI v1 · 7/7/2026

Bi-variate linear constraints are linear constraints that involve exactly two variables at a time. In the context of hardware-accelerated constrained random test generation, systems consisting solely of such bi-variate constraints (together with single-variable range constraints) have been shown to be relevant and often adequate for modeling the environment of on-chip bus protocols such as IBM CoreConnect and AMBA AHB. Their tractable structure enables efficient geometric decomposition (into planes and strips) and the synthesis of modest-area hardware generators that emit random satisfying valuations within a few clock cycles. Synthesis of more general constraints involving an arbitrary number of variables remains an open problem.

Bi-variate Linear Constraints

Definition

A bi-variate linear constraint is a linear constraint (an inequality or equation) whose coefficients reference exactly two variables. In the test-generation literature, systems that mix bi-variate linear constraints with single-variable range constraints arise frequently when describing the environment of a design under test (DUT).

Motivation and Relevance

Investigations of complex test benches for on-chip bus protocols (e.g., AMBA AHB, IBM CoreConnect) found that test-bench constraints typically take one of two forms:

  1. Range constraints over a single variable, and
  2. Linear constraints involving two variables — i.e., bi-variate linear constraints.

Because of this pattern, systems of constraints restricted to bi-variate linear forms (plus univariate ranges) are argued to be both relevant and often adequate in practice for modeling the verification environment of industry-standard bus designs [bec47706-0e84-494c-9ef6-696f6697e13e, 9c77d530-9607-4d23-8443-9f7d4f9ceb09].

Geometric Decomposition

The bi-variate structure permits a convenient geometric decomposition used by the constraint-synthesis tool:

  • Each pair of variables induces a plane.
  • Within a plane, individual bi-variate constraints correspond to strips (the feasible region between two parallel lines).
  • For n variables, the number of planes is ({}^nC_2).

For example, a constraint with six variables (widths 32, 3, 3, 2, 2, 2 bits) yields ({}^6C_2 = 15) planes [1]. The variable widths strongly affect the memory needed in the synthesized hardware because each plane is partitioned into strips sized according to bit widths.

Synthesis Implications

Because bi-variate constraints can be processed as strips inside independent variable-pair planes, the synthesis procedure can:

  • Decompose the system into a small number of independent sub-problems (one per variable pair).
  • Generate circuits with modest area overhead (measured in bit count and gate count after Synopsys Design Compiler) [1].
  • Produce random valuations satisfying the constraints within a few clock cycles using LFSR-driven hardware [1].

The area complexity scales with variable widths: components whose environments involve address-bus variables incur larger area, while components with mostly narrow control variables (e.g., IBM CC OPB and AHB Master) have comparatively smaller area overheads [1].

Example (AMBA AHB)

A typical AHB arbiter verification scenario models a master (#4) receiving a Split or Retry response for a half-word (16-bit) read transfer to a slave (#1) with address range [128:255]. The relevant variables and their widths are:

Variable Role Width (bits)
addr transfer span 32
burst burst type 3
size byte-lane size 3
fracad byte-lane selection 2
trans transfer mode 2
resp response type 2

The combined constraint over these six variables involves 11 input constraints and decomposes into 15 planes, illustrating the bi-variate decomposition [1].

Open Problem

While the bi-variate restriction plus univariate ranges is sufficient for many practical bus-protocol test benches, the synthesis of general constraints involving an arbitrary number of variables is explicitly identified as an open problem [2].

Related Concepts

  • Hardware accelerated constrained random test generation — the paper that introduces and validates the use of bi-variate constraints for synthesis.
  • Two-step constrained random synthesis — a synthesis technique that operates on constraint systems expressed with bi-variate linear constraints.

LINKED ENTITIES

2 links
Hardware accelerated constrained random test generation USES
two-step constrained random synthesis USES

CITATIONS

6 sources
6 citations
[1] Systems of constraints involving only bi-variate constraints are both relevant and often adequate in practice for modeling on-chip bus verification environments. Hardware accelerated constrained random test
[2] On-chip bus test-bench constraints generally consist of ranges over individual variables or linear constraints involving two variables. Hardware accelerated constrained random test
[3] A six-variable AHB Master constraint with widths (32,3,3,2,2,2) yields 15 planes via the C(6,2) decomposition and uses 11 input constraints. Hardware accelerated constrained random test
[4] Synthesized circuits for bi-variate constraint systems have modest area overhead and produce random satisfying valuations within a few clock cycles. Hardware accelerated constrained random test
[5] Synthesis of general constraints involving any number of variables (beyond the bi-variate plus univariate-range case) remains an open problem. Hardware accelerated constrained random test
[6] The bi-variate structure enables a plane/strip decomposition: each pair of variables forms a plane and each bi-variate constraint is realized as a strip within that plane, with the number of planes equal to C(n,2). Hardware accelerated constrained random test