Asynchronous circuit design and testing

Asynchronous circuits are a promising technology for low-power, high-performance, low-emission and highly modular digital circuits.

My research in this area has been first oriented at studying specification, synthesis and testing of asynchronous control circuits using a bounded delay model. This research (performed mainly together with Kurt Keutzer, Alberto Sangiovanni-Vincentelli, Narendra Shenoy, Alex Yakovlev) is described in detail in two publications:

• L. Lavagno. Synthesis and Testing of Bounded Wire Delay Asynchronous Circuits from Signal Transition Graphs. PhD thesis, U.C. Berkeley, November 1992. Technical report UCB/ERL M92/140.
• L. Lavagno and A. Sangiovanni-Vincentelli. Algorithms for synthesis and testing of asynchronous circuits. Kluwer Academic Publishers, 1993.

Most of the algorithms described there have been implemented in the sequential logic synthesis system SIS, developed at U.C. Berkeley and described in

• E. M. Sentovich, K. J. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P. R. Stephan, R. K. Brayton, and A. Sangiovanni-Vincentelli. SIS: A system for sequential circuit synthesis. Technical Report UCB/ERL M92/41, U.C. Berkeley, May 1992.

The complete source code of SIS can be found at the following ftp site. Please, send also e-mail to sis@ic.eecs.berkeley.edu, so that we know that you downloaded it and we can inform you about patches and new releases.

Mike Kishinevsky, Peter Vanbekbergen and I gave a tutorial at the International Conference on Computer-Aided Design (ICCAD) 1995 on The Systematic Design of Asynchronous Circuits.

After that, I started working on design of Speed-Independent asynchronous circuits, that is assuming unbounded gate delays. The results of this research, that has been carried out with a numerous team including Jordi Cortadella, Mike Kishinevsky, Alex Kondratyev, Alexander Taubin, Alex Yakovlev and others, are described in several publications, such as:

• J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, and A. Yakovlev A region-based theory for state assignment in asynchronous circuits. IEEE Transactions on Computer-Aided Design, 16(8):793--812, August 1997.
• J. Cortadella, M. Kishinevsky, L. Lavagno, and A. Yakovlev. Deriving petri nets from finite transition systems. IEEE Transactions on Computers, 47(8):859--882, August 1998.
• J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, E. Pastor, and A. Yakovlev. Decomposition and technology mapping of speed-independent circuits using boolean relations. IEEE Transactions on Computer-Aided Design, 18(9), September 1999.
• A. Kondratyev, J. Cortadella, M. Kishinevsky, L. Lavagno, and A. Yakovlev. Logic decomposition of speed-independent circuits. Proceedings of the IEEE, 87(2), February 1999.

In 2002 the Petrify team made it to the finals for the Descartes Award for European Cooperation in Research. It was a very exciting time indeed, since for the first time our work was recognized beyond specialized circles.

I am also working on translating Hardware Description Languages, in particular Verilog, to asynchronous circuits. The first results of that work can be found in the pipefitter WEB page.

The most recent work is about transforming a synthesized synchronous circuit, with any mix of flip-flops, latches and combinational logic, into an asynchronous circuit by de-synchronization. The technique is the cheapest and simplest known way to obtain an asynchronous design by deviating as little as possible from the standard synchronous flow. A DATE 2004 tutorial is devoted to it.

Using this technique we are working on an asynchronous open core microprocessor, as part of the ASPIDA IST FP5 project.

A good list of other references on asynchronous circuits can be found at the WEB site of the asynchronous group of the University of Manchester.