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.
The Multiple Representation Approach
The core innovation of FUNSTRUX lies in its ability to translate circuit descriptions through three distinct representations:
- Simulator Code: The initial LISP-based description of individual components.
- Abstract Events: A representation focusing on the event-driven core—triggers, variable changes, and delays—stripped of simulator-specific semantics.
- 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 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