university crest

Hazard-free Arbiter Design (HADES)

* Sponsor:

EPSRC GR/K70175

* Evaluation Results:

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

* Principal Investigator:

Dr. A. Yakovlev

* Other Investigators:

Prof. D.J. Kinniment
Dr. G. Russell

* Research Associates:

Dr. A. Bystrov
Dr. F. Xia

* Period:

01.11.96 - 29.02.00

* Keywords:

analogue-to-digital converters, arbiters, asynchronous circuits, automated synthesis, circuit decomposition, distributed systems, hazard-free implementation, Petri nets, Petrify, self-timed circuits, signal transition graphs (STGs), speed-independent circuits, synchronisation, system-on-chip testing, VLSI design

* Summary:

The advent of submicron technologies allows construction of systems on chip with multiple clocking domains. Multi-processor buses, interrupt systems, multi-port memories and packet routers and switches are only some of the applications which require use of generic components such as synchronisers and arbiters, to resolve an inherent interprocess races and resource contention. These components are known to suffer from metastable behaviour, which is fundamental and its effects can only be mitigated but not completely avoided. The HADES project has addressed a number of problems concerned with the construction and testing of robust and efficient synchronisers, multi-way arbiters and analogue-to-digital converters. Particular emphasis has been on: (i) the advancement and development of models of arbiters and A/D converters and their analysis and measurement, including multi-way arbiters and flash converters; (ii) the development of automated synthesis methods, for circuits with conflict resolution and arbitration; (iii) the design, analysis and VLSI implementation of new arbitration and A/D convertion circuits.

* Aims and Approach:

(1) Advancement and development of modelling and synthesis techniques for asynchronous arbitration and resource allocation circuits.

(2) A Study into the effects of metastability and implementation of arbiters and A/D converters

(3) Development of verification, timing and performance analysis and testing techniques and tools for arbitration circuits

(4) Design examples (multi-way and priority arbiters, practically fair arbiters, resource control and allocation circuits, multi-pipeline synchronisation)

(5) Development of a demonstrator chip, comprising circuits from HADES and COMFORT (on asynchronous communication mechanisms for real-time systems, GR/L93775) projects

* Main Technical Results:

* Publications:

Specification models and synthesis techniques

1. M. Kishinevsky, J. Cortadella, A.Kondratyev, L. Lavagno, A. Taubin and A. Yakovlev. Coupling asynchrony and interrupts: place chart nets and their synthesis, Proc. Int. Conference on Application and Theory of Petri Nets (ed. R. Valette), Toulouse, June 1997, Lecture Notes in Computer Science, Vol. 1248, Springer, Berlin, 1997, pp. 328-347.

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

3. A. Kondratyev and 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.

4. A. Yakovlev. Designing Control Logic for Counterflow Pipeline Processor Using Petri nets, Formal Methods in Systems Design (Kluwer), Vol. 12, No.1 (January 1998), pp. 39-71.

5. 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.

6. J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno and A. Yakovlev, Petrify: a tool for manipulating concurrent specifications and synthesis of asynchronous controllers, IEICE Trans. Inf. and Syst., Vol. E80-D, No.3, March 1997, pp. 315-325.

7. 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.)

Modelling Metastable Behaviour

8. I.G. Clark, F. Xia, A.V. Yakovlev and A.C. Davies, Petri net models of latch metastability, Electronics Letters, 2nd April 1998, Vol. 34, No.7, pp. 635-636.

9. D.J. Kinniment, A. Yakovlev, B. Gao. Metastable behaviour and system performance. Proc. 2nd UK Forum on Asynchronous Systems, Department of Computing Science, University of Newcastle upon Tyne, July 1997.

10. D.J. Kinniment, A.V. Yakovlev and B. Gao. Metastable Behaviour in Arbiter Circuits, TR. no. 604, Department of Computing Science, University of Newcastle upon Tyne, December 1996.

11. F. Xia and A. Yakovlev. Overview of modelling and analysis techniques for arbiters. and related circuits, TR. no. 626, Department of Computing Science, University of Newcastle upon Tyne, January 1998.

12. F.Xia, I.G. Clark, A.V. Yakovlev and A.C. Davies Petri net models of metastable operations in latch circuits. Proc. 3rd UK Forum on Asynchronous Systems, Department of Computer Science, Edinburgh University, December 1997.

Asynchronous A/D converters

13. D. J. Kinniment, A. V. Yakovlev, and B. Gao. "Synchronous and Asynchronous A-D Conversion", IEEE Transactions on VLSI systems, Vol. 8 No. 2 Apr. 2000 pp217-219.

14. D.J. Kinniment, A.V. Yakovlev. Low power, low noise micropipelined flash A-D converter, IEE Proc. Circuits, Devices Systems, vol. 146, no.5, October 1999, pp 263-267.

15. D.J. Kinniment, B. Gao, A. Yakovlev, and F. Xia. Towards asynchronous A-D conversion, Proc. 4th Int. Symp. on Advanced Research in Asynchronous Circuits and Systems, March-April 1998, San Diego, CA, IEEE Computer Society Press, pp. 206-215.

Verification, testing and measuring arbiter circuits

16. 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.

17. D. Kinniment. Measurements on a high speed arbiter, Technical Report No. CS-TR-677, Department of Computing Science, University of Newcastle upon Tyne, Newcastle, UK. Februrary 2000.

Performance analysis of arbiters

18. 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).

19. 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.

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

21. 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.

Design of circuits with arbitration

22. A. Bystrov, D.J. Kinniment and A. Yakovlev. Priority arbiters, Proc. Sixth Int. Symp on Adv. Research in Async. Cir. and Syst. (ASYNC'2000), Eilat, Israel, April 2000, IEEE Comp. Soc. Press, pp. 128-137.

23. A. Bystrov and A. Yakovlev. Ordered arbiters. Electronics Letters, 27th May 1999, Vol. 35, No. 11, pp. 877-879.

24. A. Yakovlev, D.J. Kinniment, F. Xia and A.M. Koelmans. A FIFO buffer with non-blocking interface. IEEE Computer Society TCVLSI Technical Bulletin, Fall 1998, pp. 11-14.

25. A. Bystrov and A. Yakovlev. Revisiting the problem of fair arbitration. Proc. of 5th UK Asynchronous Forum, Computer Laboratory, University of Cambridge, December 1998.

26. A. Yakovlev, Solving ACiD-WG design problems with Petri net based methods. Proc. ESPRIT ACiD-WG Workshop on Asynchronous Circuit Design, Groningen, Sept. 9-10, 1996, TR CSN9602, Computer Science Notes Series, University of Groningen.

27. C. Carrion and A. Yakovlev. Design and Evaluation of two Asynchronous Token Ring Adapters. TR. no. 562, Department of Computing Science, University of Newcastle upon Tyne, October 1996.

28. K.S.Low and A. Yakovlev. Token Ring Arbiters: an exercise in asynchronous logic design with Petri nets, TR. no. 537, Department of Computing Science, University of Newcastle upon Tyne, November 1995.

29. A. Bystrov and A. Yakovlev. Fast four-phase tree FIFO. 7th UK Asynchronous Forum, University of Newcastle upon Tyne, 20-21 December 1999.

Other project-related publications

30. M. Pietkiewicz-Koutny. Transition systems of elementary net systems with inhibitor arcs. Proc. ICATPN'97, P. Azema and G. Balbo (Eds), LNCS 1248 (1997), Springer-Verlag, pp. 310-327.

31. M. Pietkiewicz-Koutny. Synthesis of ENI-systems using minimal regions. Proc. CONCUR'98, D. Sangiorgi and R. de Simone (Eds), LNCS 1466 (1998), Springer-Verlag, pp. 565-580.

32. M.Pietkiewicz-Koutny: The synthesis problem for Elementary Net Systems with Inhibitor Arcs. Fundamenta Informaticae, R.Janicki (ed.), Volume 40, Number 2-3, November-December 1999, 251-283.

33. A. Kondratyev, J. Cortadella, M. Kishinevsky, L. Lavagno, A. Yakovlev. Logic decomposition of speed-independent circuits (invited paper). Proceedings of IEEE, vol. 87, no.2, pp. 347-362, Feb. 1999.

34. J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, E. Pastor, and A. Yakovlev. Decomposition and technology mapping of speed-independent circuits usinf boolean relations. IEEE Trans. of CAD, Vol. 18, No. 9, Sep. 1999, pp. 1221-1236.

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.

* Acknowledgements:

The authors of this project are very thankful to EPSRC for their financial support. They also wish to thank Matra BAe Systems, RAL, SUN Microsystems, Intel Corp, Acorn Networks, Theseus Logic and ACiD-WG partners for fruitful interaction in the course of the project.
Hazard-free Arbiter Design (HADES), 20 April 2000
Alex.Yakovlev@ncl.ac.uk