Design as Refinement Plus Constraint Propagation: The VEXED Experience

Louis I. SteinbergAAAI 1987

Introduction

Designing complex systems, such as VLSI (Very Large Scale Integration) circuits, presents a significant intellectual challenge. Engineers must manage vast amounts of domain knowledge while ensuring that local design decisions do not violate global requirements. Historically, AI design tools have struggled to find a balance, often being either fully automated—leaving the user disconnected from the process—or purely manual, forcing the user to perform tedious consistency checks.

Introduced in 1987, VEXED (Vlsi Expert EDitor) addresses this "interface problem" by acting as an interactive design aid. It explores a fundamental model of engineering: design as a process of top-down refinement paired with automated constraint propagation. In this model, the human designer provides the high-level strategy, while the machine ensures logical consistency and handles the complex "bookkeeping" of circuit constraints.

The VEXED Methodology

The core philosophy of VEXED is summarized by the equation: DESIGN = TOP-DOWN REFINEMENT + CONSTRAINT PROPAGATION.

Top-Down Refinement

In VEXED, the design process begins with a high-level functional specification. The user selects a module and chooses a "refinement rule" from a library to decompose it into smaller, more concrete sub-modules. For example, a "Content-Addressable Memory (CAM) cell" might be refined into a storage element and a comparator.

Figure 3: Conceptual refinement tree for a CAM cell, illustrating the decomposition from high-level functional blocks to transistor-level implementations.

Constraint Propagation

As the user makes refinement choices, the system uses the CRITTER subsystem to maintain design consistency through two primary techniques:

  • Goal Regression: Determining the necessary input specifications for a module to ensure a desired output is achieved.
  • Symbolic Evaluation: Inferring the behavior of a module's outputs based on its current inputs.

This division of labor allows the user to act as the strategist, while the system acts as a clerk, tracking pending tasks and simplifying the logical expressions resulting from propagation.

System Implementation and Interface

The VEXED interface provides a workspace where users can interactively evolve their designs. The system maintains an "agenda" of modules that require further refinement. When a user selects a module, VEXED suggests applicable rules from its knowledge base.

Figure 2: The VEXED interface showing the refinement of a CAM-CELL into its constituent MEM (memory) and GMOD (logic) modules.

Evaluation of the system involved student teams in VLSI design classes and benchmark circuits like full adders. The experiments proved that users with minimal AI background could successfully design functional circuits using VEXED's specification language. The system effectively caught consistency errors that human designers might have overlooked.

Key Insights and Limitations

While VEXED successfully ensures "legal" and functional designs, the authors identified several critical insights:

  • Legal vs. Optimal: The refinement rules define what can be built (legal moves) rather than what should be built (optimal moves). VEXED ensures the circuit works, but not necessarily that it is efficient in terms of area or power.
  • The Strategy Gap: The system lacks a global strategy. Users often made locally valid choices that led to sub-optimal final designs because they could not foresee how a current choice would limit future options.
  • Computational Cost: Constraint propagation is computationally expensive. In the 1980s hardware environment, propagating constraints for a small circuit could take several minutes, highlighting a significant performance bottleneck.

Conclusion

VEXED demonstrates the power of combining human strategic guidance with machine-led consistency checking. While it successfully offloads the burden of logical verification, the "VEXED experience" suggests that future AI design aids must incorporate more sophisticated strategic knowledge to guide users toward truly optimal engineering solutions.

Summary updated

BibTeX
@inproceedings{steinberg1987design,
  author = {Louis I. Steinberg},
  title = {{Design as Refinement Plus Constraint Propagation: The VEXED Experience}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1987},
}
Figure