A Multiple Representation Approach to Understanding the Time Behavior of Digital Circuits

Robert J. Hall, Richard H. Lathrop, Robert S. KirkAAAI 1987

Introduction

In digital circuit design, there exists a significant "abstraction gap" between the structural level (gates and connections) and the behavioral level (high-level functional descriptions). While gate-level simulation is accurate, it is computationally expensive for large-scale systems. Conversely, hand-written behavioral models are efficient but prone to human error. This paper introduces FUNSTRUX, a system designed to automatically derive optimized behavioral models from structural descriptions by navigating multiple levels of representation.

A sample circuit segment illustrating structural components and signals.

The Multiple Representation Approach

The core innovation of FUNSTRUX lies in its ability to translate circuit descriptions through three distinct representations:

  1. Simulator Code: The initial LISP-based description of individual components.
  2. Abstract Events: A representation focusing on the event-driven core—triggers, variable changes, and delays—stripped of simulator-specific semantics.
  3. Temporal Equations: A mathematical representation expressing output at time $t$ as a function of inputs at earlier times. This uses a specialized operator ($\Leftarrow$) to model state and memory by referring to the most recent time a predicate was true.
The FUNSTRUX transformation pipeline from component code to optimized circuit code.

The Transformation Pipeline

The system follows a structured pipeline to generate optimized code. First, it substitutes a component's inputs with the temporal equations of its drivers. Because this process can lead to expression explosion, FUNSTRUX interleaves substitution with simplification using approximately 50-75 symbolic "Pattern-Action" rules. These rules typically reduce expression size by 90%. Finally, the simplified temporal equations are converted back into optimized simulator code.

Key Insights

  • Locality of Reference: Temporal equations make dependencies explicit and local, facilitating automated algebraic substitution compared to standard program code.
  • Finite Time Points: By identifying a finite set of relevant time points within the equations, the system reduces complex temporal reasoning to propositional logic.
  • Interleaved Simplification: Maintaining manageable data structures requires simplifying expressions during the substitution phase rather than as a post-processing step.

Results and Performance

The system was evaluated using the AMD 2901 Bit-Slice ALU, a complex component with 370 gate-level elements. FUNSTRUX successfully generated a behavioral model in 7 hours on a Symbolics Lisp Machine. The resulting model demonstrated:

  • 3x Simulation Speedup: The derived behavioral model ran significantly faster than the original gate-level simulation.
  • 10x Event Reduction: The model scheduled an order of magnitude fewer events, drastically reducing the overhead associated with event-queue management in simulators.

Conclusion

FUNSTRUX demonstrates that automated abstraction is feasible for digital circuits. By pivoting through temporal equations, the system bridges the gap between structure and behavior, providing a path toward more efficient and reliable CAD tools. Future work aims to address limitations such as zero-delay feedback loops and the readability of the generated "machine-optimized" code.

Summary updated

BibTeX
@inproceedings{hall1987multiple,
  author = {Robert J. Hall and Richard H. Lathrop and Robert S. Kirk},
  title = {{A Multiple Representation Approach to Understanding the Time Behavior of Digital Circuits}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1987},
}
Figure