Knowledge Engineering Issues in VLSI Synthesis

Wayne H. Wolf, Thaddeus J. Kowalski, Michael C. McFarlandAAAI 1986

Introduction: The Silicon Compiler Wall

In the mid-1980s, the field of computer-aided design (CAD) faced a significant challenge. The promise of "silicon compilers"—tools capable of automatically transforming high-level algorithmic descriptions into physical chip layouts—was hindered by the inherent complexity of VLSI design. This 1986 paper from the AAAI proceedings argues that VLSI synthesis is fundamentally a search problem that requires a departure from traditional design paradigms. The authors propose a "vertical" organization of knowledge to handle the tightly coupled constraints that span multiple levels of abstraction.

The Limitations of Horizontal Models

Traditional models of computer design typically utilize a "horizontal" abstraction approach. In this model, knowledge is partitioned into isolated layers: the Processor-Memory-Switch (PMS) level, the program level, the logic level, and the circuit level. While this separation simplifies individual design tasks, it creates a significant barrier for automated synthesis.

VLSI design is an NP-hard problem where high-level architectural choices (such as selecting a specific adder type) are constrained by low-level physical realities (such as pin counts or parasitic capacitance). Horizontal models prevent synthesis tools from "looking ahead" to evaluate how a high-level decision will impact the final physical implementation. To overcome this, the authors advocate for the "Tall Thin Man" paradigm: a system capable of reasoning across all levels of abstraction simultaneously.

A Vertical Architecture for Synthesis

The core of the authors' proposal is a vertical categorization of knowledge. Rather than grouping all logic-level information together, they suggest grouping all knowledge related to a specific module (e.g., a latch, an adder, or a multiplier) across every level of abstraction—from functional behavior down to physical geometry and timing characteristics.

The proposed system architecture categorizes knowledge into module-specific data, selection rules, and composition heuristics.

As shown in the architecture above, the system relies on three distinct types of knowledge representation:

  1. Knowledge about Modules (Procedural): Specific module designs and measurement methods (calculating area, delay, and power) are implemented as procedural code. The authors argue that well-understood algorithms, such as timing analysis, should not be recast into declarative rules.
  2. Module Selection (Declarative): To prune the massive search space, an associative database is used. This allows the system to filter candidates based on static criteria like functionality or technology family (e.g., CMOS).
  3. Module Composition (Hybrid): This layer combines compiled functions for general connectivity with production systems (like the OPS family) for local pattern-matching optimizations, such as replacing a weak gate with a high-power version.

A key insight of the paper is that synthesis is a generative search problem, distinct from the diagnostic expert systems common in the 1980s. The system must build a "good" implementation from a specification, similar to the Dendral project's approach to molecular structures.

The design space for a floating-point algorithm shows a 'jagged' nature, indicating that simple hill-climbing is insufficient for global optimization.

The search space for VLSI design is notoriously unpredictable. As illustrated in the figure above, the design space for even a simple floating-point algorithm is "jagged." This unpredictability suggests that simple, local hill-climbing rules are insufficient for global optimization. Instead, the authors argue for a pragmatic balance: using rules for heuristics and local transformations, while maintaining procedural control for global strategy and mathematical evaluations.

Results and Future Directions

The paper provides a qualitative framework based on the development of three CAD tools: Fred (a chip planning database), DAA (Design Automation Assistant), and BUD (an intelligent partitioner). This framework demonstrates a path toward the automatic design of large-scale systems (exceeding 100,000 transistors) that remain competitive with human designs.

However, several challenges remain. The authors identify "planning" as a major open problem, specifically the need for systems to recover or reformulate a plan when a design path leads to an unsatisfactory layout. Furthermore, identifying the minimal knowledge required for early error detection and balancing expert-system heuristics with efficient algorithmic search continue to be central issues in the evolution of VLSI synthesis tools.

Summary updated

BibTeX
@inproceedings{wolf1986knowledge,
  author = {Wayne H. Wolf and Thaddeus J. Kowalski and Michael C. McFarland},
  title = {{Knowledge Engineering Issues in VLSI Synthesis}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}

Loading related content...

Figure