Overview
Maintaining arc consistency (MAC) is described as a family of algorithms that uses arc consistency as its filtering mechanism. An arc is arc-consistent when, for any value in the domain of any variable in the arc, there is a valid assignment to the other variables in the arc that satisfies the constraint. The procedure for reaching arc consistency removes from variable domains the values that cannot participate in any solution. [C1]
Role in constraint-satisfaction problems
The cited source presents MAC in the context of constraint-satisfaction problems (CSPs). A CSP consists of a finite set of variables and a set of constraints between those variables. Each variable has a domain of possible values, and each constraint denotes valid combinations of values over some subset of the variables. A CSP solution assigns each variable a value from its domain such that all constraints are satisfied. A constraint graph represents variables as nodes and constraints as arcs. [C2]
The test-program generation setting discussed in the source can involve very large domains; for example, a 32-bit register data attribute and a 32-bit machine address attribute each have domain size 2^32. The source states that CSP techniques with strong filtering mechanisms are well suited to such large search spaces. [C3]
MAC procedure in Genesys-Pro
Genesys-Pro uses an external generic solver implementing a customized MAC algorithm for pseudorandom test-program generation. The algorithm is described as producing uniformly distributed random solutions that satisfy all mandatory constraints and as many nonmandatory constraints as possible. [C4]
The solution process described in the source is:
- Apply arc consistency over all mandatory constraints. If any mandatory constraint fails to reach arc consistency, the solution process fails; otherwise, the process repeatedly reduces the domains of variables in the relevant arcs. [C5]
- Apply arc consistency over all nonmandatory constraints. These constraints are invoked in priority order, and failures are ignored. The algorithm then reconsiders the mandatory constraints and repeats until it reaches a fixed point, meaning no variable domain is reduced further. [C6]
- Randomly select one variable and reduce its domain to a single element. This retriggers the arc-consistency procedure over mandatory and nonmandatory constraints. [C7]
- After every variable domain has been reduced to a single element, the algorithm has reached a solution. [C8]
Example: instruction generation
In the Genesys-Pro instruction-generation flow, a single instruction request is formulated as a CSP; the solver then finds a solution and produces an instruction instance satisfying the constraints. The architecture reference model is invoked afterward to simulate the generated instruction. [C9]
To formulate the CSP, the architectural model is transformed into a CSP graph by associating a CSP variable with each instruction attribute, such as base.address and target.address. Architectural and testing-knowledge constraints become CSP arcs; for example, base.address != target.address is converted into an arc between those attributes. Constraints from the test template are superimposed on the graph, such as reducing a target address to the single element 5 for a request involving R5. [C10]
In the Load-instruction example, after the first fixed point, the solver eliminates the value 5 from base.address by applying base.address != target.address. The same example shows the source operand address reduced to quad-word-aligned addresses, represented by the hexadecimal mask 0xXXXXXXX0, where each X is a 4-bit don't-care. [C11]
Reported advantages in the cited domain
The source states that MAC-based algorithms are well suited for test-program generation because they postpone heuristic decisions until after considering all architectural and testing-knowledge constraints. This lets them find solutions satisfying all architectural constraints and as many nonmandatory constraints as possible. [C12]
The source contrasts this with CSP algorithms that rely on local heuristic methods for early pruning of the search space, stating that such pruning weakens their ability to solve several constraints simultaneously and to allow uniform exploration of the search space. [C13]