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.
As shown in the architecture above, the system relies on three distinct types of knowledge representation:
- 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.
- 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).
- 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.
Navigating the Jagged Search Space
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 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