Report Number: CSL-TR-94-652
Institution: Stanford University, Computer Systems Laboratory
Title: Automatic Synthesis and Verification of Gate-Level Timed
Author: Myers, Chris J.
Author: Rokicki, Tomas G.
Author: Meng, Teresa H.-Y.
Date: December 1994
Abstract: This paper presents a CAD system for the automatic synthesis
and verification of gate-level timed circuits. Timed circuits
are a class of asynchronous circuits which incorporate
explicit timing information in the specification which is
used throughout the synthesis procedure to optimize the
design. This system accepts a textual specification capable
of specifying general circuit behavior and timing
requirements. This specification is systematically
transformed to a graphical representation that can be
analyzed using an exact and efficient timing analysis
algorithm to find the reachable state space. From this state
space, our synthesis procedure derives a timed circuit that
is hazard-free using only basic gates to facilitate the
mapping to semi-custom components, such as standard-cells and
gate-arrays. The resulting gate-level timed circuit
implementations are up to 40 percent smaller and 50 percent
faster than those produced using other asynchronous design
methodologies. We also demonstrate that our timed designs can
be smaller and faster than their synchronous counterparts. To
address verification, we have applied our timing analysis
algorithm to verify efficiently not only our synthesized
circuits but also a wide collection of reasonable-sized,
highly concurrent timed circuits that could not previously be
verified using traditional techniques.