EPSRC logo

Details of Grant 

EPSRC Reference: GR/J52310/01
Principal Investigator: Dagless, Professor EL
Other Investigators:
Milford, Dr D
Researcher Co-Investigators:
Project Partners:
Department: Electrical and Electronic Engineering
Organisation: University of Bristol
Scheme: Standard Research (Pre-FEC)
Starts: 01 February 1994 Ends: 31 March 1997 Value (£): 105,404
EPSRC Research Topic Classifications:
Design & Testing Technology
EPSRC Industrial Sector Classifications:
Related Grants:
Panel History:  
Summary on Grant Application Form
1. Improvements in Petri net abstraction, which plays an important part in reducing the complexity of the parallel state assignment and decomposition problems.2. Work on Petri net model analysis based on net unfoldings.3. More sophisticated algorithms for state assignment and the decomposition of parallel controllers4. Methods and algorithms for automatic generation and analysis of Signal Transition Graphs.5. Development of algorithms for the verification of parallel controller design;6. Links between a Petri net specifications and VHDL.7. Use of the work in the implementation of parallel controller designs in a variety of target techniques. Progress:1. A two-level design methodology based on labelled Petri nets has been developed. The higher level, abstract synthesis, is based on construction of a Petri net specification of a control circuit in a compositional and modularway. Each component of the high-level model is then refined as a Signal Transition Graph (STG) describing an associated subcircuit. STG-based synthesis techniques, both existing and being currently upgraded, are further applied to generate circuit implementations. This methodology allows a better abstraction of the synthesised control flow and exploits useful heuristics at a higher abstraction level.2. Three major techniques have been used in analysing the Petri net semantics: reduced reachability graphs (based on stubborn sets), partial order (based on net unfoldings), symbolic traversal (based on Boolean Decision Diagrams for set characteristic function representation). Our main emphasis has been on the unfolding technique as it appears to provide an efficient way for analysis of correctness of STG models of circuits. All three techniques have been used for the verification of asynchronous circuits.3. Petri net colouring and net unfolding methods have been studied to assist in both state assignment and net decomposition.4. We have investigated the necessary and sufficient conditions (called the monotonic cover condition)n for Signal Transition Graphs to produce hazard-free implementation of asynchronous circuits. Work is under way now on generation of STGs from State Graph descriptions.5. Algorithms have been implemented within the PARIS software system and initial results based on standard benchmarks have been produced.6. Some theoretical foundations for the link between VHDL and Petri nets have been laid, but the actual translation techniques will be determined in the final year of the project.7. We have defined an intermediate format for the exchange Petri nets, PNIF, which will enable easy transfer of data between the partners of this project, and in the long term may form the basis for a standard. Discussions are taking place with others to explore this possibility. The PNIF format has been used to transfer a set of Bristol benchmarks to Newcastle, and will be the medium for transfer of asynchronous descriptions developed at Newcastle. An EDIF interface has been produced at Bristol to take a PN design for full custom implementation into the Cadence design tools. A graphical front end has been developed for synchronous net design and this is now linked into these tools so that a design can be taken through two routes from graphical input to silicon either using customised cells or to FPGA. Work is progressing on making the tools robust and enhancing the capabilities of the tool set. Case studies are being evaluated which will allow the two groups to co-operate in the production of the single design comprising both synchronous and asynchronous parts.More than 10 papers have been written so far by the groups at Bristol and Newcastle on the work done in this project, and a a full list is available from the principal investigators.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:  
Further Information:  
Organisation Website: http://www.bris.ac.uk