Saturn: An Automatic Test Generation System for Digital Circuits

Narinder SinghAAAI 1986

Saturn is a pioneering test generation system that moves beyond flat, gate-level logic to reason about digital circuits at multiple levels of abstraction. By using logic-based representation and hierarchical reasoning, it dramatically reduces the search space for test vectors, making the testing of complex VLSI systems computationally feasible.

The Complexity Wall in Digital Circuit Testing

In the mid-1980s, the manufacturing of digital devices was reaching unprecedented levels of complexity. To ensure these devices worked correctly, engineers needed to generate "test vectors"—sequences of inputs that could reveal manufacturing defects, such as "stuck-at" faults where a gate is permanently fixed at 0 or 1.

The primary challenge was a "complexity wall." Traditional algorithms, such as the D-algorithm, operated strictly at the boolean gate level. As circuits grew, the computational cost of generating these tests increased exponentially with the depth of the circuit. Because these systems lacked a way to represent higher-level design intent (e.g., recognizing a group of gates as an adder), they spent massive amounts of time calculating irrelevant low-level details. Saturn was designed to bridge this gap by allowing designers to specify behavior at various abstraction levels that mirror the actual design process.

Hierarchical Reasoning and Methods

Saturn utilizes a declarative approach based on logic programming. The system supports arbitrary levels of abstraction, moving from structural groupings to functional behaviors.

Hierarchical structure of an adder circuit in Saturn.

Key components of the Saturn methodology include:

  • Corona Language: A prefix form of predicate calculus used to describe the structure and behavior of a design.
  • Resolution Residue Planning: An automated deduction procedure that propagates values forward and backward through the design to find the necessary inputs to observe a specific fault.
  • Multi-Level Abstraction: Saturn supports structural grouping (e.g., gates into full-adders), functional descriptions (using operators like +), and value abstraction (using domains like "positive/negative") to prune the search tree.
  • Search Control: The system employs incremental consistency checking, cost-based heuristics to select efficient ports, and caching to reuse solutions for identical sub-components.

Key Insights: Abstraction and Caching

The power of Saturn lies in its ability to ignore irrelevant details. By reasoning at a high level—for example, treating an adder output as simply the sum of its inputs—Saturn can ignore internal gate-level transitions if they do not affect the final test goal. This significantly reduces the "branching factor" of the search space.

Furthermore, Saturn leverages the repetitive nature of hardware design through caching. In hierarchical designs, many components are identical. Saturn caches the test solutions for a single "full-adder" and reuses them across the entire circuit. This turns a problem that scales with the number of modules into one that scales with the number of module types. Finally, functional abstraction allows the system to treat test goals as mathematical constraints, converting exponential search problems into polynomial constraint problems.

Key Results and Scaling

Evaluation on circuit benchmarks, including N-bit adders and real-world hardware like the IBM PC Printer Adapter Card, demonstrated that abstraction pays off significantly.

Performance comparison between flat and refined test generation across adder sizes.

As shown in the performance data, the "flat" gate-level approach often failed to find solutions or took an impractical amount of time for larger circuits. In contrast, the "refined" hierarchical approach kept the number of tests roughly constant while time grew quadratically rather than exponentially. For a 4-bit adder, using cost-based heuristics generated tests in 272 seconds, while a standard generation order took over 2 hours—a 26x speedup. Caching sub-goals further improved generation time by a factor of 2.2x for the same circuit.

In real-world applications, the system successfully generated 40 tests for the IBM PC printer adapter card in approximately 30 minutes, proving its viability for complex industrial designs.

Limitations and Future Work

While Saturn represents a major leap forward, challenges remain. Sequential circuits, which require "unfolding" finite state machines, are still computationally expensive. Functional abstraction is most effective for linear constraints; non-linear constraints still necessitate significant search. Additionally, while hierarchical abstraction provides smaller initial sets of test vectors, the authors noted that their test minimization algorithms were not yet optimal. Future work at the time focused on modeling even more complex systems, such as the IBM PC-AT motherboard and its associated microprocessors.

Summary updated

BibTeX
@inproceedings{singh1986saturn,
  author = {Narinder Singh},
  title = {{Saturn: An Automatic Test Generation System for Digital Circuits}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure