Introduction
As VLSI (Very Large Scale Integration) components grow in complexity, traditional test generation methods—relying on gate-level structural analysis and constraint propagation—face a computational explosion. Human experts, however, bypass this by reasoning about a device's intended function (e.g., "this is an ADD instruction"). This paper proposes automating this "teleological" reasoning to generate tests for complex datapaths efficiently.
The Designed-Behavior Hypothesis
The core of this approach is the Designed-Behavior Hypothesis: the state space of what a circuit can do (potential behavior) is massive, but the space of what it was designed to do is relatively small and manageable. By restricting the search to intended operational modes, test generation becomes tractable.
System Architecture
The proposed system automates test generation through three primary stages:
- Preprocessing: Using symbolic simulation, the system generates behavior graphs. Variables (e.g.,
?Addend) represent data, creating a database of information flow during standard operations like a CPU's instruction set. - Micro-planning: This stage matches specific testing goals (e.g., exercising an ALU function) against behavior graphs to identify high-level instructions that provide the necessary controllability and observability.
- Macro-planning: A best-first search identifies the sequence of operations required to set up register states and move results to observable output pins.
Evaluation: The MARK-2 Microprocessor
The system was evaluated using the MARK-2, a 16-bit horizontally microprogrammed processor. The circuit consists of 16 components and 91 nodes, featuring a sequencer with 80 lines of microcode and 23 instructions.
Key Results and Insights
The system generated prototype tests for the MARK-2 datapath in approximately one minute on a Symbolics 3640. While it successfully covered the entire datapath, it failed on the controller (sequencer and FSM). The authors argue this failure is a "feature," highlighting areas where the Designed-Behavior Hypothesis does not hold and signaling a need for "Design for Testability" (DFT) modifications.
Teleology as a Constraint
Knowing the "purpose" of a circuit provides a natural abstraction. If an input sequence doesn't correspond to a valid command, the planner ignores it, drastically reducing the search space. This "failing fast" allows engineers to identify untestable areas early in the design cycle.
Limitations and Future Work
The method currently struggles with the non-linear logic of control units and assumes a complete list of operations is provided. Furthermore, it relies on symbolic inversion of functions; extremely complex data transformations may still pose challenges. Future work suggests applying this method to other complex building blocks like UARTs and graphics controllers.
Conclusion
By exploiting designed behavior, this approach offers a powerful alternative to gate-level algorithms for complex VLSI datapaths. It provides a path toward faster test generation and early identification of untestable design regions, bridging the gap between human expertise and automated tools.
Summary updated