Asynchronous Circuit Synthesis and Testing (ASTI)

Final EPSRC assessment grades are:
Scientific or technical merit - alpha 5 (top)
Management and use of resources - Excellent (top)

Sponsor:

EPSRC (Visiting Fellowship) GR/L24038

Principal Investigator:

Dr. A. Yakovlev

Period:

01.04.97 - 01.10.98

Keywords:

asynchronous circuits, automated synthesis, circuit decomposition,hazard-free implementation, Petri nets, Petrify, signal transition graphs (STGs), speed-independent circuits, technology mapping, testing, timed circuits

Abstract:

This project provided funds (through the EPSRC Visting Fellowship scheme) for collaboration between the Newcastle VLSI design research group and two leading scientists in the area of asynchronous system design, Prof. Luciano Lavagno (Politecnico di Torino, Italy) and Prof. Alex Kondratyev (University of Aizu, Japan). It continued supporting our main activity in automated synthesis and testing of asynchronous control circuits started in the earlier ASAP Project (Automated Synthesis of Parallel and Asynchronous Controllers, GR/J52327), and assisted further collaboration within Petrify consortium.

Aims and Approach:

(a) Development of new methods for logic decomposition and technology mapping for speed-independent circuits

(b) Development of a new behavioural model and method for synthesis of asynchronous circuits with timing conditions, to allow greater flexibility in area and speed optimisation.

(c) Development of a new method for detecting delay faults in sequential asynchronous circuits using partial scan, and investigation of new approaches for built-in testing of asynchronous circuits based on behavioural models.

Main Results:

• New theoretical developements in synthesis and verification of asynchronous circuits based on Petri nets and Signal Transition Graphs (STGs):
  • Method for decomposition and technology mapping of speed-independent circuits.
  • Formal model, Lazy Transition Systems, and a method for efficient synthesis of controllers with relative timing conditions.
  • Method for automatic synthesis of asynchronous control circuits from high level (CSP-like) and/or partial STG specifications.
  • Method for identifying state coding conflicts in STGs using Petri net unfolding.
  • Method for detecting delay faults in a sequential asynchronous circuits.
  Methods 1 to 3 have been implemented in an asynchronous circuit synthesis tool, Petrify , built by Prof. Jordi Cortadella at the Polytechnic University of Catalonia.
• Further advancement in the exploitation of the synthesis methods and tool Petrify in a number of industrial (Intel Corp (US), Cogency Technology (UK), CSEM (Switzerland), FHG (Germany)) and academic (e.g., Amulet, Manchester) design groups.
• Seminars and discussions at Manchester (Amulet), South Bank (Centre for Concurrency and VLSI), Newcastle (Departments of Computing Science and EEEng, Engineering Design Centre, King's College London and BAe) on various aspects of asynchronous circuit, real-time and embedded systems design.
• Fruitful interaction with members of staff, RAs, PhD students and two visiting members of staff at Newcastle, including sharing extensive expertise in hardware-software codesign by Prof. Lavagno.
• New research topics for ongoing collaboration between the Universities of Aizu and Newcastle and Polytechnic of Turin (the latter two are members of the ESPRIT-funded Working group on asynchronous circuit design, ACiD-WG. Further joint publications are expected in the near future.

Main Publications:

J.Cortadella, M.Kishinevsky, L.Lavagno and A.Yakovlev, Deriving Petri Nets from Finite Transition Systems, IEEE Transactions on Computers, Vol. 47, No. 8, pp. 859--882, Aug. 1998.

A.Kondratyev, J.Cortadella, M.Kishinevsky, L.Lavagno and A.Yakovlev. Logic decomposition of speed-independent circuits. Proceedings of IEEE, vol. 87, no. 2, pp. 347--362, Feb. 1999 (Special Issue on Asynchronous Systems).

J.Cortadella, M.Kishinevsky, A.Kondratyev, L.Lavagno, E.Pastor and A.Yakovlev. Decomposition and technology mapping of speed-independent circuits using boolean relations. In Proc. IEEE/ACM Int. Conference on CAD (ICCAD'97), November 1997, IEEE Computer Society Press (also submitted to IEEE Trans. on CAD).

A.Kondratyev, M.Kishinevsky and A.Yakovlev. Hazard-free implementation of speed-independent circuits, IEEE Trans. on CAD, vol. 17, no. 9, pp. 749--771, Sept. 1998.

J.Cortadella, M.Kishinevsky, A.Kondratyev, L.Lavagno and A.Yakovlev, A region-based theory for state assignment in speed-independent circuits. IEEE Trans. on CAD , vol. 16, no. 8, August 1997, pp. 793--812.

J.Cortadella, M.Kishinevsky, A.Kondratyev, L.Lavagno, and A.Yakovlev. Automatic handshake expansion and reshuffling using concurrency reduction. In Proceedings of the ICATPN'98 Workshop on Hardware Design and Petri Nets (HWPN'98) , June 23, 1998, Lisbon, pp. 86--110.

J.Cortadella, M.Kishinevsky, A.Kondratyev, L.Lavagno, and A.Yakovlev. Automatic synthesis and optimization of partially specified asynchronous systems. Accepted for DAC'99 , October 1998.

A.Kondratyev, J.Cortadella, M.Kishinevsky, L.Lavagno, A.Taubin and A.Yakovlev. Identifying state coding conflicts in asynchronous system specifications using Petri net unfoldings, In Proceedings of Int. Conf. on Appl. of Concurrency to System Design (CSD'98) , March 1998, Aizu-Wakamatsu, Japan, IEEE Computer Society Press, pp. 152--163.

M.Kishinevsky, A.Kondratyev, L.Lavagno, A.Saldanha and A.Taubin. Partial Scan Delay Fault Testing of Asynchronous Circuits. In Proc. IEEE/ACM Int. Conference on CAD (ICCAD'97) , November 1997, IEEE Computer Society Press.

A.Kondratyev, J.Cortadella, M.Kishinevsky, L.Lavagno, A.Taubin and A.Yakovlev. Lazy transition systems: application to timing optimisation of asynchronous circuits. In Proc. IEEE/ACM Int. Conference on CAD (ICCAD'98) , November 1998, IEEE Computer Society Press.

Further Information:

about Prof. Alex Kondratyev

about Prof. Luciano Lavagno

other projects of the VLSI research group:

Design for Validation (DeVa)
Time-Predictable Hardware Platforms (TIMBRE)
Asynchronous Communication Mechanisms for Real-Time Systems (COMFORT)
Asynchronous Circuit Design
Hazard-free Arbiter Design
Design of Reliable Asynchronous Controllers and Interfaces
Design tools for synthesis of asynchronous systems and circuits