A System Which Uses Examples to Learn VLSI Structure Manipulation

AAAI 1986

TL;DR

This paper introduces CONSTELLATION, a system that learns VLSI design "precedents" from examples provided by a human designer. It allows for the automatic inference of local hierarchy and the application of clever design tricks, aiming to improve the efficiency and clarity of complex VLSI designs, especially in the late stages of the design process.

What Problem Does This Paper Address?

Designing complex Very Large Scale Integration (VLSI) circuits, particularly in the later stages of optimization and physical layout, presents significant challenges. Two main issues complicate this process:

  1. Obscured Designer Intent: As designs progress, the detailed, low-level descriptions can obscure the original intent of the designer, making it difficult for both humans and machines to understand and manipulate the circuit coherently.
  2. "Clever" Local Optimizations: Designers often employ situation-specific sub-circuits or "tricks" to optimize performance or area. While effective, these can further obscure the overall design intent and are hard to systematically apply across a large design.

Existing tools often discard hierarchical information early in the design process, hindering the exploitation of regularities. This makes it difficult for designers to ensure that all known optimization techniques are applied everywhere they are applicable, leading to potentially less efficient designs. The paper aims to address the need for tools that can capture and apply local structural knowledge to analyze and refine nearly complete designs.

Methods

CONSTELLATION employs a learning apprentice approach, inspired by systems like LEAP, but focused on structural analysis and refinement of late-stage designs. The core idea is the "design precedent," defined as "a situation I have seen before, and what to do when I see it again." These precedents are captured as pattern/action pairs.

The knowledge acquisition process is interactive:

  1. Example Selection: A designer highlights a specific sub-circuit within an existing design using a graphical interface.
  2. Precedent Creation: The system automatically isolates this sub-circuit, inverts it into a Y-language module definition (representing a higher-level abstraction), and creates a precedent rule.
  3. Default Action: The default action associated with the precedent is to replace future occurrences of the recognized pattern with the newly defined higher-level module, effectively inferring local hierarchy.
  4. Custom Actions: Designers can also specify alternative actions, described in the system's native Y hardware description language, to be performed when the pattern is matched.

The system's components include a database for design representation, an isolator to extract sub-circuits, an inverter to generate Y-language descriptions, a precedent builder, a simulation model builder, a matcher to find precedent patterns in new designs, and an action evaluator to execute the learned actions.

Datasets

The paper mentions using a "COMET Chip" for experimental use, which is described as having approximately 30,000 transistors, comprising about 3,000 cells (logic gates and flip-flops) and 3,000 connecting busses. This chip serves as an example design for demonstrating the system's capabilities. No other specific datasets or benchmarks are mentioned.

Key Insights and Ideas

  • Precedents as "Local Expertise": The concept of precedents effectively captures granular, situation-specific design knowledge that is difficult to encode in traditional rule-based systems or global heuristics.
  • Learning from Examples: Allowing designers to point and click to define precedents significantly lowers the barrier to knowledge acquisition, making it more intuitive and less labor-intensive than manual rule creation.
  • Automatic Hierarchy Inference: By replacing low-level sub-circuits with higher-level module definitions, CONSTELLATION can automatically reconstruct or infer hierarchical structure, improving design clarity.
  • Bridging the Gap Between Low-Level Detail and High-Level Intent: The system helps to re-introduce meaningful abstractions into designs that have become overly detailed, making them more understandable and manageable.
  • Potential for Design Criticism and Optimization: The pattern-matching capability can be extended beyond hierarchy inference to identify and correct design flaws or apply specific optimizations, acting as a form of automated design criticism.

Key Results

The paper demonstrates the system's functionality through an example: a precedent is created from a simple INVERTER/NOR combination. When this precedent is applied to the original circuit (Figure 2), the two components are replaced by a single, higher-level module (INVNOR), simplifying the representation (Figure 4). The system is described as operating at approximately 1-2 seconds per match-and-replace cycle on the COMET chip, making it suitable for interactive use. The authors state that the system is in experimental use in a production environment.

Limitations and Future Work

The authors acknowledge that CONSTELLATION is primarily focused on local structural knowledge and the late stages of design. They suggest that more powerful reasoners will be necessary for guiding major design decisions and handling special cases not covered by precedents. Future work is planned to focus on generalizing the precedent pattern/action processor and incorporating information from the functional and physical arms of the Y-diagram (beyond just the structural level). They also envision future applications in optimizing silicon compiler outputs.

Summary updated

BibTeX
@inproceedings{1986system,
  title = {{A System Which Uses Examples to Learn VLSI Structure Manipulation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure