university crest

Department of Computing Science

University of Newcastle upon Tyne

"Behavioural Synthesis of Systems with Heterogeneous Timing" (BESST)

funded by EPSRC (GR/R16754) from 1st July 2001 for three years. Total amount of funding is approx. 325,000 pounds.

GRANT REVIEW RESULT (12/05/2005) - Overall assessment: Outstanding
In particular

Final IGR report (including the list of publications) can be found here

Tools developed in this project:

Presentation "Asynchronous system design flow based on Petri nets" (with demo) at the University Booth Exhibition , DATE 2005, Munich, March 2005:

This is a collaborative research project between the schools of Computing Science and Electrical, Electronic and Computer Engineering. The aim of the project is to develop theoretical and algorithmic techniques and tools for automated synthesis of concurrent systems and asynchronous control circuits from high-level specifications, where Petri nets will play a key role as the intermediate language.

The list of investigators:


The list of PhD students: Other colleagues actively involved in this project are:
Alex Bystrov, Fei Xia and Ian Clark (School of EECE),
Victor Khomenko, Jon Burton and Marta Pietkiewicz-Koutny (School of CS),
Eike Best (Karl von Ossietzky University of Oldenburg).

Colleagues with whom we collaborated in this research: Jordi Cortadella and Josep Carmona(UPC Barcelona), Michael Kishinevsky, Ken Stevens and Steve Burns (Intel Labs, Oregon), Alex Kondratyev (Cadence, Berkeley), Luciano Lavagno (Politecnico di Torino), Nikolay Starodoubtsev (Uni. Social Welfare, Tokyo), Steve Furber (Univ. Manchester), Rene Krenz (KTH, Stockholm), Mark Renaudin (TIMA, INPG, Grenoble), Jetty Kleijn (Univ. of Leiden), Raymond Devillers (Universite Libre de Bruxelles), Hanna Klaudel (Universite d'Evry, Paris), Franck Pommereau (Universite Paris 12), Walter Vogler (Univ. of Augsburg), Hiroshi Saito and Takashi Nanya (Univ. of Tokyo), Alexander Taubin (Boston University), Sue Tyerman (Uni. South Australia, Adelaide)

BESST Project Summary (from the project proposal):

Asynchronous circuit design is becoming a commercial reality as the first products with asynchronous ICs are approaching markets (see, eg. http://www-us.semiconductors.com/pip/PCA5007H)

As technology reaches the range of 100M to 1B transistors on a chip, it is increasingly difficult to design and validate Systems-on-Chip (SOCs), which will inevitably consist of many separately timed communicating domains, regardless of whether these components are internally clocked or not. SOCs are thus an artifact with the salient characteristics of Distribution, Concurrency and Asynchrony. These features come out both as a natural result of Moore's law in semiconductor technology (see SIA roadmap) and due to performance-driven factors of the development of an on-chip system architecture. The prime target of BESST is Distributed, Concurrent and Asynchronous (DCA) (hardware) communication and operation kernels of SOCs. Such kernels can be seen in two areas. Firstly, they are protocols and associated "glue logic", used to interface functional parts of SOCs, such as interface "wrappers" for existing IPs. Secondly, they are controllers for new components, which can themselves be seen as future IPs, whose designs are susceptible to the effects of greater interconnect dominance. Existing synthesis tools fall short of providing good support for designing sufficiently complex asynchronous controllers in an efficient and reliable way.

BESST proposes to synthesise behaviourally critical DCA parts of SOCs (semi-)automatically from their high-level specifications. The results of BESST will support the design of such systems by people with limited asynchronous design experience and at a much lower cost. We thus aim at a theoretical underpinning for self-timed systems synthesis, and a set of techniques and tools enabling the application of theory to designing interfaces and controllers of SOCs. With a large emphasis on automatic synthesis, including synthesis from HDLs, this approach will not diminish the role of verification and refinement in system design. It assumes, e.g. that the specification of a system must be validated against general consistency properties and other formally stated requirements.

In a more specialised scope of asynchronous circuit design, the proposed techniques will enable synthesis of complex control circuits built of specified implementation libraries, whose behaviour should be tolerant to critical component and wire delays and optimised to work with highest possible performance. Such circuits present a very challenging example of DCA systems of more generic nature. Thus, in a longer term, this approach, if successful, will lay a foundation for a new generation of design productivity tools that will assist behavioural synthesis of generic discrete-event systems which may be implemented as hardware or hardware-software kernels of embedded systems, mobile communication systems, machine intelligence systems etc. The general principles and techniques for synthesis of such systems will allow for efficient mapping of a system specification onto processors, FPGAs, ASICs etc.

The new tools will be integrated with the existing synthesis software (see, e.g., Petrify ) and practical case study experiments with interface controllers and asynchronous communication mechanisms, showing their effect on the productivity and quality of the design process will be performed.

The results of this research will benefit the designers of asynchronous circuits for SOCs in industrial and academic environments, circuits that can be used in low power and portable equipment such as pagers, smartcards, portable sensors and i-buttons. They will also be useful for designers of concurrent systems in general (e.g., embedded, real-time and reactive systems, distributed systems), seeking methods to avoid global synchronisation. With the growth of industrial interest in exploiting benefits of asynchronism in such systems, both in the UK and internationally, this project will create a methodological and experimental basis for design and implementation of systems based on fully or partially asynchronous operation.
Further details about the project may be obtained from Alex Yakovlev, Dept. of Computing Science, University of Newcastle upon Tyne, NE1 7RU, tel. +44-191-2228184, email:

Alex.Yakovlev@ncl.ac.uk