Overview
Maintain-arc-consistency (MAC) is a constraint-solving technique referenced as a well-known scheme for constraint satisfaction problems (CSPs). In the cited IBM hardware-verification work, MAC is the overall algorithmic framework of a specialized constraint solver for random stimuli generation. The paper identifies constraint propagation as the fundamental building block of MAC and notes that stochastic search is used in rare cases where constraint propagation is computationally hard.
Role in constraint-based random stimuli generation
In IBM's constraint-based random stimuli generation system for hardware verification, a functional model, expert knowledge, and verification scenarios are translated into constraints and solved by a dedicated engine. That engine adapts a maintain-arc-consistency scheme to the special needs of stimuli generation.
The system uses CSPs because they provide a declarative way to state rules and let the solver enforce them. The same CSP-based approach also supports prioritization of expert-knowledge rules through a Soft-CSP algorithm.
Adaptations described in the evidence
Random sampling of the solution space
The cited stimuli-generation setting requires many different tests from a single design model and test template, with tests distributed as uniformly as possible among conforming tests. The described approach randomizes all decisions in the MAC search path to obtain reasonably disperse solutions. This requirement prevents the use of variable-ordering and value-ordering heuristics, because variables and values must be chosen randomly. The authors describe this as a major deviation from regular MAC-based techniques, which may rely heavily on such heuristics for efficient search.
Soft-constraint hierarchy
The evidence also describes expert knowledge as soft constraints arranged in a multi-tiered hierarchy according to importance. This hierarchy can conflict with uniformly distributed solution generation: if only one assignment satisfies the maximum number of soft constraints, always returning that assignment would undermine test diversity. The described solver resolves this by using a local metric: if a partial solution can be extended to satisfy additional soft constraints, it must be extended that way, but the solver does not require satisfying a globally maximal number of soft constraints over the entire search space.
Large domains
The same application includes CSP variables with exponentially large domains. The cited examples are address and data variables with domains on the order of 2^32 or larger. This is one of the reasons the authors distinguish their solver from general-purpose constraint solvers.
Reported application context
The evidence comes from a paper on IBM's use of AI technologies for hardware verification. The system is used to generate tests, or stimuli, for simulating hardware designs before fabrication in silicon, with the goal of checking conformance of hardware implementation to specification. The paper reports that IBM estimated savings of more than $100 million over the prior decade through this AI-based verification technology.