Myers Research Group

University of Utah



People

Research

Tools

Publications

Book

Home Page

Synthesis and Technology Mapping of Timed Circuits

SUPPORTED BY

SRC-97-TJ-487.002: Synthesis and Technology Mapping of Timed Circuits

NSF CAREER award MIP-9625014

NSF Japan Program Award INT-0087281

Recently, many researchers have proposed utilizing asynchronous circuits to eliminate clock distribution problems, lower system power requirements, and produce higher performance circuits. Asynchronous circuits also provide a clean link to existing and evolving formal verification techniques. The PentiumPro processor used a total of 300 staff years for pre and post silicon validation. The modularity of asynchronous circuits enables a ``divide and conquer'' approach that simplifies this validation process. Unfortunately, traditional academic asynchronous design methods use unbounded delay assumptions, resulting in circuits that are verifiable but unnecessarily inefficient. In industry, performance is critical, so timing assumptions must be made. Due to the lack of formal methods to handle timing information correctly, circuits with timing constraints usually require extensive simulation to gain confidence in the design which limits their applicability to very small parts of the design. Timed circuits bridge this gap between academic research and industrial needs by allowing timing and communication to be explicitly specified, synthesized, analyzed, and verified.

Since existing commercial tools are not well-suited to asynchronous design and cannot analyze the timing assumptions and constraints that our designs rely on, the primary goal of this research project is to develop a variety of new tools for the design of timed circuits. Specifically, this task concentrates on developing a suite of tools for the synthesis and technology mapping of timed circuits. Our research will build on our prior work in the development of the synthesis tool ATACS. This new tool utilizes more general event/level-based specifications, implicit state representations (such as, binary decision diagrams, BDDs), and more efficient timing analysis algorithms. Our technology mapper targets a variety of technologies from standard-cells to custom cells, using fully complementary logic, precharged logic, and generalized C-elements. Our major research results in this area are listed below:

  • We developed a symbolic version of our synthesis methods which uses binary decision diagrams (BDDs) and multi-terminal BDDs (MTBDDs). These techniques can substantially improve our memory performance, and our synthesized result using this method is a BDD representation of all possible timed circuit implementations. This work was conducted by Robert Thacker.
  • In collaboration with Sung-tae Jung, a visiting researcher from Wonkwong University, we developed a new method to synthesize timed asynchronous circuits directly from the specification without generating a state graph. The synthesis procedure begins with a graph specification with timing constraints. A timing analysis extracts the timed concurrency and timed causality relations between any two signal transitions. Then, a hazard-free implementation of the specification is synthesized by analyzing precedence graphs which are constructed by using the timed concurrency and timed causality relations. The major result of this work is that the method does not suffer from the state explosion problem, achieves significant reductions in synthesis time for the specifications which have a large state space, and generates synthesized circuits that have nearly the same area as compared to previous timed circuit methods. This work is described in publications listed below.
  • We have also generalized our synthesis algorithms to fundamental-mode asynchronous circuits (also known as Huffman circuits). Not only does this allow us to synthesize more types of asynchronous circuits, but it also results in a substantial improvement in synthesis time compared to the state-of-the-art tools for Huffman circuits. This work was conducted by Hans Jacobson.
  • Chris Krieger developed a state assignment method for timed circuits which optimize for the performance of the resulting circuit implementation.
  • We have developed modular synthesis techniques which have greatly expanded our synthesis capacity. Hao Zheng developed modular synthesis methods based on automatic abstraction. Eric Mercer developed modular synthesis methods that used partial orders. This work has been in collaboration with Professor Tomohiro Yoneda of the National Institute of Informatics in Tokyo,
  • In the technology mapping area, Curt Nelson has developed an efficient incremental timed circuit verifier that can be utilized throughout the technology mapping process to search for area/delay efficient circuit implementations that are hazard-free.

Faculty:

Students:

Books:

PhD Theses:

Master's Theses:

Journal Papers:

Conference Papers:

Workshop Papers: