Time-predictable hardware platforms (TIMBRE)

Sponsor:

EPSRC GR/L28098

Evaluation Results:

Scientific or technical merit - alpha 4 (top)
Management and use of resources - Excellent (top)

Principal Investigator:

Dr. A. Yakovlev

Other Investigators:

Dr. A.M. Koelmans

Research Associates:

Dr. F. Burns

Period:

01.04.97 - 31.03.00

Keywords:

asynchronous circuits, automated synthesis, hardware platforms, Petri nets, performance analysis, power consumption, real-time systems, system-on-chip, timing analysis, timing predictability, worst-case execution time

Summary:

Design of real-time systems involves a mapping between the logical and physical levels of a system specification. This mapping determines the quality of the timing information available at each level of abstraction. A crucial issue, which introduces a significant element of temporal uncertainty, is the way in which the system design is tied together with the use of specific hardware components. In designing systems for embedded applications realistic timing information about hardware often becomes available only during software development, which creates an additional adequacy problem. The TIMBRE project has tackled the problem of timing predictability of hardware platforms for developing real-time systems.

Aims and Approach:

(1) Advancement in modelling and analysis of timed behaviour for hierarchical hardware platforms of real-time systems.

(2) Development of methods and software for Worst Case Execution Time (WCET) analysis of hardware platforms, taking into account the effects of pipelining, buffering, out-of-order instruction execution, etc.

(3) Development of methods for assessing timing predictability of hardware platforms, tradeoffs between accuracy and efficiency of modelling and effects on the quality of executable code.

Main Technical Results:

• Most of the objectives (particularly 1 and 2) have been met successfully. The follwing methods and software tools have been developed:
  • A method for modelling temporal behaviour of complex processor architectures, based on (high-level) Coloured Petri Nets (CPN). It allows the designer to construct the behavioural model of a particular architecture in a modular way out of CPN models of specific issues, such as pipelining, buffering, out-of-order instruction execution, branch prediction, caching. The CPN model have been made executable through the use of Design/CPN tools, in which a set of ML software components has been built for performing simulation and evaluation of the constructed models. The result of using this method is an increased productivity of the overall system design, in which an executable model of the hardware platform could be constructed in a matter of hours. Ref. [1-4]
  • A WCET analysis method using the Design/CPN framework. The accuracy of the method compared to the existing WCET techniques, such as those based on close-formula and integer-linear programming approaches, has been estimated. Ref. [8]
  • A method for modelling and analysis of asynchronous hardware systems based on Petri nets with read arcs, using the unfolding prefix Ref. [5]
  • Methods for specification and design of embedded systems, and for modelling and symbolic analysis of coordinated systems. Ref. [6-7]
  • A method for modelling timing behaviour of asynchronous circuits and systems based on relative timing. It uses the idea of Lazy Transition Systems, in which the concept of enabling and execution (firing) are differentiated. Ref. [9]
  • Methods for performance and power consumption of asynchronous hardware using Petri net invariant analysis. Ref. [10-15]
  • A semi-automated technique for fast prototyping of asynchronous microprocessors from high-level Petri net specification to FPGA implementation. Ref. [16]
• Exploitation and dissemination
  • The results of the TIMBRE project have been reported in 19 papers, including journal and conference publications. The analysis methods and Petri net models developed in this project have been made available to our main industrial partners, Matra BAe Systems through the Centre for Software Reliability, and other UK and European partners (e.g., Real-time Systems group at York University , Design/CPN group at Aarhus, Denmark ) through the DeVa Project (EU/Framework 4, Design for Validation) and ACiD-WG (EU/Framework 4 Working Group on Asynchronous Circuit Design), and our active links with the asynchronous system design and Petri nets communities.
  • The TIMBRE project gave rise to a joint project with Brandenburg Technical University at Cottbus on dependable system design with Petri nets, sponsored by British Council and DAAD, and a collaborative work with the Real Time Systems group at the University of York on developing a methodology for verifying interaction mechanisms for high-integrity systems, a number of MSc and undergraduate research projects, and a new PhD project. One PhD thesis (by A. Semenov) has been successfuly defended and two more are in preparation.

Publications:

Petri net models of hardware platforms

1. F.B. Burns, A.M. Koelmans, A.V. Yakovlev. Analysing superscalar processor architectures with coloured Petri nets. Int. Journal on Software Tools for Technology Transfer, Vol.2, No.2, December 1998, Springer, pp. 182-191.

2. F. Burns, A. Yakovlev and A. Koelmans. Modelling of superscalar processor architectures with Design/CPN. Proc. Workshop on Practical Use of Coloured Petri Nets and Design/CPN. Aarhus (Ed. by K. Jensen), Denmark, 10-12 June 1998, DAIMI TR PB-532, May 1998, pp. 15-30.

3. F. Burns, A. Yakovlev, and A. Koelmans. Modelling Superscalar Processor Architectures with Coloured Petri Nets, Proc. ACiD-WG Workshop "Specification Models and Languages and Technology Effects on Asynchronous Design", Torino, Italy, January 1988.

4. F. Burns, A. Yakovlev and A. Koelmans. On the modelling of superscalar processor architectures with coloured Petri nets. Proc. 3rd UK Forum on Asynchronous Systems, Department of Computer Science, Edinburgh University, December 1997.

5. W. Vogler, A. Semenov and A. Yakovlev. Unfolding and Finite Prefix for Nets with Read Arcs. Proceedings of CONCUR'98, Nice, France, Sept. 1998, LNCS No. 1466, pp. 501-516.

6. J. Mirkowski and A. Yakovlev. A Petri net model for embedded systems. Workshop on Design and Diagnostics of Elctronic Circuits and Systems, Szczyrk, September 2-4, 1998, pp. 313-321, ISBN 83-908409-6-0.

7. E. Pastor, A. Yakovlev and J. Cortadella. Hierarchical communicating nets for the symbolic analysis of coordinated systems. Proc. of the Special Interest Workshop on Exploitation of STG-based Design Technology, St.Petersburg, 6-7 July 1998.

Analysis of Worst Case Execution Time

8. F. Burns, A. Koelmans and A. Yakovlev. WCET Analysis of Superscalar Processors Using Simulation With Coloured Petri Nets, Real-Time Systems: The International Journal of Time-Critical Computing Systems, Volume 18, Issue 2/3, May 2000, Kluwer Academic Publishers, pp. 267-280. ( Special issue on WCET analysis )

Timing-driven hardware optimisation

9. A. Kondratyev, J. Cortadella, M. Kishinevsky, L. Lavagno, A. Taubin, A. Yakovlev. Lazy Transition Systems: Application to Timing Optimization of Asynchronous Circuits. Proc. IEEE/ACM Int. Conference on CAD (ICCAD'98), November 1998, San Jose, IEEE Comp Soc. Press, pp. 324-331.

Timing and performance analysis

10. I. Mitrani, A. Yakovlev. Tree Arbiter with Nearest-Neighbour Scheduling. Proc. of the 13th International Symposium on Computer and Information Sciences (ISCIS'98), 26-28 October, Belek-Anatlya, Turkey. In: Advances in Computer and Information Sciences'98 (Eds. U. Gudukbay, T. Dayar, A. Gursoy, E. Gelenbe) Concurrent Systems Engineering Series Vol. 53, pp. 83-92, ISBN 90-5199-405-2 (IOS Press).

11. A. Madalinski, F. Xia and A. Yakovlev. Studying the data loss and data re-reading behaviour of a four-slot asynchronous communication mechanism using stochastic Petri nets techniques. 7th UK Asynchronous Forum, University of Newcastle upon Tyne, 20-21 December 1999.

12. A. Madalinski. MSc Dissertation, University of Liverpool, Jan. 2000.

13. A. Madalinksi, A. Bystrov and A. Yakovlev. Statistical fairness of ordered arbiters, Tech. Report Series CS-TR-703, Dept. of Computing Science, University of Newcastle upon Tyne, April 2000.

Analysis of power consumption

14. L. Lloyd, A. V. Yakovlev, E. Pastor, A.M. Koelmans Estimations of power consumption in asynchronous logic as derived from Graph Based Circuit Representations. International Workshop on Power and Timing Modeling, Optimization and Simulation (PATMOS'98), Technical University of Denmark - October 7-9, 1998, pp. 367-376, A.M. Trullemans-Anckaert, J. Sparsoe (eds).

15. L. Lloyd, A. Yakovlev, E. Pastor, A. Koelmans Estimations of Power Consumption in Asynchronous Logic 4th UK Async Forum, Imperial College, London, 13-14- July 1998.

Rapid prototyping

16. L. Lloyd, K. Heron, A. Yakovlev, and A.M. Koelmans. Asynchronous microprocessors: from high level model to FPGA implementation. Journal of Systems Architecture vol. 45 (1999), pp. 975-1000, Elsevier.

17. L. Lloyd, K. Heron, A. M. Koelmans, A.V. Yakovlev. Rapid design of asynchronous logic using reconfigurable architectures. Int. Conference on Microelectronics and Packaging (ICMP'98), Curitiba, Parana, Brazil, 12-14 August 1998.

Other TIMBRE-related publications

18. A.V. Yakovlev and A.M. Koelmans. Petri nets and Digital Hardware Design Lectures on Petri Nets II: Applications. Advances in Petri Nets, Lecture Notes in Computer Science, vol. 1492, Springer-Verlag, 1998, pp. 154-236. Contents and order info

19. A. Yakovlev, L. Gomes and L. Lavagno (Eds.) Hardware Design and Petri Nets. Kluwer Academic Publishers, Boston, ISBN 0-7923-7791-5, March 2000, 344 pp (selected papers from two int. workshops on Hardware Design and Petri nets, HWPN'98, Lisbon and HWPN'99, Williamsburg.) Contents and order info

20. A. Burns, A.J. Wellings, F.Burns, A.M. Koelmans, M. Koutny, A. Romanovsky and A. Yakovlev. Towards Modelling and Verification of Concurrent Ada Programs using Petri Nets, Tech. Report Series TR-CS-700, Computing Science, University of Newcastle upon Tyne, March 2000.

Acknowledgements:

Further Information:

other projects of the VLSI research group:

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