An Intelligent Aid for Circuit Redesign

Tom M. Mitchell, Louis I. Steinberg, Smadar T. Kedar-Cabelli, Van E. Kelly, Jeffrey S. Shulman, Timothy WeinrichAAAI 1983

Abstract

In the early 1980s, the increasing complexity of digital circuits necessitated tools that could assist in modifying existing designs without compromising their integrity. This paper introduces REDESIGN, a knowledge-based system developed at Rutgers University. REDESIGN treats circuit modification as a reasoning problem by combining causal reasoning (how signals flow) with teleological reasoning (why components exist). By "replaying" a recorded design plan against new specifications, the system identifies necessary changes and predicts ripple effects, acting as an intelligent assistant for functional redesign.

Introduction

The primary challenge in digital circuit redesign is the loss of the original designer's intent. Traditional CAD tools often fail to capture the "why" behind a specific component's presence, making it difficult to alter a circuit to meet new requirements—such as changing the number of characters per line in a terminal—without inadvertently violating timing or signal constraints.

REDESIGN addresses this by maintaining a deep understanding of the interrelationships between a circuit’s structure, its function (what it does), and its purpose (the role it plays in the larger system).

Reasoning with Purpose and Causality

The REDESIGN system employs two distinct modes of reasoning to guide the user through the modification process:

  1. Causal Reasoning (The "How"): Utilizing the CRITTER subsystem, REDESIGN propagates signal behaviors and specifications. Unlike standard simulators, it represents "data-streams" as entire time histories, distinguishing between actual behavior and the specifications required for correct operation.
  2. Reasoning about Purpose (The "Why"): The system relies on a Design Plan, a hierarchical data structure that records how high-level goals were decomposed into subgoals and eventually mapped to hardware.
A Design Plan for the Character Generator Module, showing the decomposition of high-level goals into subgoals and hardware implementations.

The redesign process follows a five-step loop: focusing on logic failures, generating hardware changes via constraint propagation, ranking options using heuristics, implementation, and repairing side effects detected by CRITTER.

Case Study: The Character Generator Module

The system was evaluated using functional models of a Video Output Circuit (VOC) and a Character Generator Module (CGM). A key test case involved modifying a terminal to display an italics font.

The physical structure of the Character Generator Module, comprising a latch, ROM, and shift register.

In this scenario, REDESIGN correctly identified that the purpose of the ROM had changed. It suggested either replacing the ROM or adding a transformation module. The system ranked "replacing the ROM" higher as it directly addressed the changed purpose. Furthermore, it used causal reasoning to ensure that any new components met the timing constraints of the surrounding, unchanged circuitry.

Key Insights

A critical innovation in REDESIGN is the distinction between S-Specifications (range of behavior assuming other parts might change) and B-Specifications (behavior assuming the rest of the circuit is fixed). By focusing on B-specifications, the system effectively isolates changes. Additionally, by treating design as a planning problem, REDESIGN can "replay" implementation rules; if a rule fails under new specs, it pinpoints exactly where the redesign must begin.

Conclusion and Future Work

While pioneering, REDESIGN faced limitations regarding the scale of circuits it could handle and its reliance on pre-authored Design Plans. Future work aimed to expand the heuristic set for ranking options and automate the implementation of suggested changes through a "VLSI Design Consultant." Despite these constraints, REDESIGN established a vital framework for intelligent CAD tools by proving that understanding a design's "purpose" is as important as understanding its "structure."

Summary updated

BibTeX
@inproceedings{mitchell1983intelligent,
  author = {Tom M. Mitchell and Louis I. Steinberg and Smadar T. Kedar-Cabelli and Van E. Kelly and Jeffrey S. Shulman and Timothy Weinrich},
  title = {{An Intelligent Aid for Circuit Redesign}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1983},
}
Figure