Skip to content
STIMSMITH

Maintain-Arc-Consistency (MAC)

Concept WIKI v1 · 5/24/2026

**Maintain-Arc-Consistency (MAC)** is a well-known algorithmic framework for solving **constraint satisfaction problems (CSPs)**, associated in the cited material with Mackworth’s 1977 work on arc consistency. In the hardware-verification context described by the evidence, MAC is used as the core search-and-propagation framework of a specialized CSP engine for **simulation-based functional verification** and **stimuli generation**.[16928ea6-1df8-4bcb-b7f0-fb72a0fc99b8]

Maintain-Arc-Consistency (MAC)

Maintain-Arc-Consistency (MAC) is a well-known algorithmic framework for solving constraint satisfaction problems (CSPs), associated in the cited material with Mackworth’s 1977 work on arc consistency. In the hardware-verification context described by the evidence, MAC is used as the core search-and-propagation framework of a specialized CSP engine for simulation-based functional verification and stimuli generation.[1]

Overview

In a CSP-based verification workflow, a functional model, verification expertise, and scenario descriptions are translated into constraints. A dedicated solving engine then generates test stimuli by solving those constraints. The cited system specifically states that its engine “adapts a maintain-arc-consistency scheme” to the special requirements of stimuli generation.[2]

The broader verification setting is simulation-based functional verification, where test cases are driven into a hardware design simulation and the resulting behavior is compared with the expected behavior from the specification.[2]

Role in CSP Solving

The evidence identifies MAC as the overall algorithmic framework of the customized constraint solver, with constraint propagation described as the fundamental building block of MAC.[1]

In this setting, MAC is used to repeatedly prune inconsistent values from variable domains while searching for assignments that satisfy the constraints of a test-generation problem. When propagation becomes computationally hard in rare cases, the described system supplements MAC with stochastic search.[1]

Use in Hardware Stimuli Generation

The cited verification system uses CSP solving to generate tests from several sources of constraints, including:

  • User requests, such as requiring particular instruction patterns.
  • Architectural validity rules, such as address-computation and exception behavior.
  • Expert knowledge, such as desired distributions of instruction outcomes or contention patterns.[2]

Because these rules are translated into constraints, MAC provides the underlying mechanism for finding valid assignments that correspond to legal and useful verification stimuli.[2][1]

Specialized Requirements

The evidence emphasizes that CSPs arising from hardware stimuli generation differ from more typical CSP applications such as job-shop scheduling or rostering. As a result, the system uses a customized MAC-based solver rather than relying directly on a general-purpose solver.[1]

Random Sampling of the Solution Space

A single design model and test template define one soft CSP, but verification requires many different tests from the same template. The solver is therefore expected to produce solutions that are distributed as uniformly as possible among the valid tests.[1]

To support this, the described MAC implementation randomizes decisions along the search path. This encourages diverse solutions across repeated solver runs, but it also means that conventional variable-ordering and value-ordering heuristics cannot be used, because choices must remain randomized.[1]

Soft Constraints and Expert Priorities

The system also handles expert-knowledge rules as soft constraints. It uses a generic soft-CSP approach to account for prioritization, but relaxes the requirement of satisfying a globally maximal number of soft constraints over the entire search space. Instead, if a partial solution can be extended to satisfy additional soft constraints, it should be extended in that way.[1]

Huge Domains

Many variables in hardware stimuli generation have extremely large domains. Examples include address and data variables with domains on the order of (2^{32}) or larger.[1]

The cited solver addresses this by using a generic library for efficient set operations over sets with huge cardinality. This enables propagation algorithms to operate even when input domains are exponentially large. The implementation uses a DNF mask representation of sets; a BDD representation was also tried but was not found useful for the reported problems.[1]

Conditional CSPs

Many of the verification problems are conditional: depending on the value assigned to some variables, large parts of the CSP may become irrelevant. The evidence gives an example from multicast verification, where the number of end-stations is itself a CSP variable and can determine how many weakly coupled CSP components are involved.[1]

To handle this efficiently, the described solver extends MAC with assumption-based pruning, which is reported to greatly improve efficiency for such conditional problems.[1]

Significance

In the cited hardware-verification application, Maintain-Arc-Consistency is not presented merely as a generic CSP technique, but as the central framework adapted for industrial-scale stimuli generation. Its adaptations address random test diversity, soft expert preferences, very large domains, and conditional problem structure—features that make verification CSPs distinct from many standard CSP benchmarks.[1]

References

  • [2] Evidence excerpt on a CSP-based hardware-verification system whose engine adapts a maintain-arc-consistency scheme for stimuli generation.
  • [1] Evidence excerpt describing the specialized MAC-based solver, random sampling, soft constraints, huge domains, and conditional CSP extensions.