university crest

Time-predictable hardware platforms (TIMBRE)

* Sponsor:


* 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:

* 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:

The authors of this project are very thankful to EPSRC for their financial support. They also wish to thank Matra BAe Systems and University of York for helpful advice.

* Further Information:

other projects of the VLSI research group:

Research Projects index
+ Computing Science Research
Time-predictable hardware platforms (TIMBRE), 22 April 2000