Flat Arbiters

• Autorzy: Mokhov A. , Khomenko V. , Yakovlev A.
• Języki publikacji: EN

Abstrakty

EN

A new way of constructing N-way arbiters is proposed. The main idea is to perform arbitrations between all pairs of requests, and then make decision on what grant to issue based on their outcomes. Crucially, all the mutual exclusion elements in such an arbiter work in parallel. This ‘flat’ arbitration is prone to new threats such as formation of cycles (leading to deadlocks), but at the same time opens up new opportunities for designing arbitration structures with different decision policies due to the availability of the global order relation between requests. To facilitate resolution of such cycles and further developments in the context of flat arbitration, the paper presents new theoretical results, including a proof of correctness of a generic structure for the N-way arbiter decision logic. In particular, in some situations a request that lost some pairwise arbitrations has to be granted to avoid a deadlock.

Słowa kluczowe

EN

arbiters; speed independent circuits; asynchronous circuits; Signal Transition Graphs (STGs)

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 108, nr 1/2
• Strony: 63--90
• Opis fizyczny: Bibliogr. 22 poz., wykr.

Twórcy

autor

Mokhov A.

autor

Khomenko V.

autor

Yakovlev A.

• School of Electrical, Electronic and Computer Engineering, Newcastle University, Newcastle upon Tyne, NE1 7RU, United Kingdom,

Bibliografia

• [1] Beerel, P.,Myers, C., Meng, T.-Y.: Covering Conditions and Algorithms for the Synthesis of Speed-Independent Circuits, IEEE Trans. on CAD, 1998.
• [2] Chu, T.-A.: Synthesis of Self-Timed VLSI Circuits from Graph-Theoretic Specifications, Ph.D. Thesis, Lab. for Comp. Sci., MIT, 1987.
• [3] Cortadella, J., Kishinevsky,M., Kondratyev, A., Lavagno, L., Yakovlev, A.: Logic Synthesis of Asynchronous Controllers and Interfaces, Springer-Verlag, 2002.
• [4] DESIJ tool home page, URL: http://www.informatik.uni-augsburg.de/en/chairs/swt/ti/ research/tools/desij.
• [5] Dill, D.: Trace Theory for Automatic Hierarchical Verification of Speed-Independent Circuits, MIT Press, 1988.
• [6] Ebergen, J.: Arbiters: An Exercise in Specifying and Decomposing Asynchronously Communicating Components, Sci. of Comp. Prog., 18, 1992, 223-245.
• [7] International Technology Roadmap for Semiconductors: Design, 2007, URL: http://www.itrs.net/ Links/2007ITRS/2007 Chapters/2007 Design.pdf.
• [8] Josephs, M.: Gate-LevelModelling and Verification of Asynchronous Circuits Using CSPM and FDR, Proc. ASYNC'07, IEEE Comp. Soc. Press, 2007.
• [9] Josephs, M., Yantchev, J.: CMOS Design of the Tree Arbiter Element, IEEE Trans. on VLSI, 4(4), 1996, 472-476.
• [10] Khomenko, V.: A Usable Reachability Analyser, Proc. 21st UK Asynchronous Forum (A. Yakovlev, Ed.), 2009.
• [11] Khomenko, V., Koutny, M., Yakovlev, A.: Logic Synthesis for Asynchronous Circuits Based on Petri Net Unfoldings and Incremental SAT, Fund. Inf., 70(1-2), 2006, 49-73.
• [12] Kinniment, D.: Synchronization and Arbitration in Digital Systems, John Wiley & Sons Ltd, 2007.
• [13] Martin, A.: The Limitations to Delay-Insensitivity in Asynchronous Circuits, Proc. 6th MIT Conference on Advanced Research in VLSI, MIT Press, 1990.
• [14] Martin, A.: Programming in VLSI: From Communicating Processes to Delay-Insensitive Circuits, Developments in Concurrency and Communication (C. Hoare, Ed.), UT Year of Programming Series, Addison-Wesley, 1990.
• [15] Muller, D., Bartky, W.: A Theory of Asynchronous Circuits, Proc. Int. Symp. of the Theory of Switching, 1959.
• [16] Poliakov, I., Mokhov, A., Rafiev, A., Sokolov, D., Yakovlev, A.: Automated Verification of Asynchronous Circuits Using Circuit Petri Nets, Proc. ASYNC'08, IEEE Comp. Soc. Press, 2008.
• [17] PUNF tool home page, URL: http://homepages.cs.ncl.ac.uk/victor.khomenko/tools/punf. 90
• [18] Reisig, W.: Petri Nets: An Introduction, vol. 4 of EATCS Monographs on Theoretical Computer Science, Springer-Verlag, 1985.
• [19] Rosenblum, L., Yakovlev, A.: Signal Graphs: from Self-Timed to Timed Ones, Proc. Int.Workshop on Timed Petri Nets, IEEE Comp. Soc. Press, 1985.
• [20] Seitz, C.: Ideas about Arbiters, Lambda, 1, 1980, 10-14.
• [21] Varshavsky, V., Ed.: Self-Timed Control of Concurrent Processes: The Design of Aperiodic Logical Circuits in Computers and Discrete Systems, Kluwer Academic Publishers, 1990, Translated from Russian, published by Nauka, Moscow, 1986.
• [22] Vogler,W., Wollowski, R.: Decomposition in Asynchronous Circuit Design, in: Concurrency and Hardware Design (J. Cortadella, A. Yakovlev, G. Rozenberg, Eds.), vol. 2549 of LNCS, Springer-Verlag, 2002, 152-190.