Asynchronism in a Joint Algorithm Architecture Perspective
AAAA: Asynchronisme et Adéquation Algorithme Architecture
OPEN ACCESS
Even if the design of asynchronous circuits reaches a certain level of maturity, they are still considered as a curiosity . However,some interesting industrial applications have been developed recently by Philips for pagers and by Sharp-Mitsubishi for set-top boxes. In this paper, the operating mode of asynchronouscircuits is first presented, and compared with its synchronous counter-part. The properties and potentials of asynchronous circuits are then described as an introduction to the last part of the paper which aims at showing that the asynchronous operating mode associated with a description formalism based on communicating processes is a powerful tool to jointly design algorithms and architectures.
Résumé
Bien que leurs techniques de conception gagnent en maturité avec notamment l'apparition d'outils automatiques, et que le nombre des réalisations augmente, les circuits asynchrones constituent aujourd'hui encore une curiosité. Toutefois, Philipsdans lespagerset Sharp-Mitsubishi dans les SetTop Boxsont les premiers à intégrer des circuits asynchrones dans des équipements pré-industriels. Cet article présente dans un premier temps le principe de fonctionnement des circuits asynchrones en le situant par rapport à celui des systèmes synchrones. Les propriétés et potentiels généraux ainsi que les coûts d'implémentation inhérents à ce type de réalisation sont ensuite abordés. Ces deux premières parties introductivesconstituent les bases du dernier chapitre de l'article qui s'attache à montrer que la combinaison du mode de fonctionnement asynchrone et d'un formalisme de description basé sur les processus séquentiels communicants constitue un outil puissant pour l'étude et la conception conjointe des algorithmes et des architectures. Nous introduisons en particulier la notion de convergence algorithme-architecture qui traduit l'idée qu'algorithme et architecture peuvent être confondus en un seul modèle, décrit sous la forme d'un programme unique qui rend compte à la fois des propriétésfonctionnelles et structurelles de la spécification.
Asynchronism, VLSI circuits.
Mots clés
Asynchronisme, circuits VLSI, adéquation algorithme-architecture.
[1] F. Robin, M. Renaudin, G. Privat, N. Van Den Bossche, «Un réseau cellulaire VLSI fonctionnellement asynchrone pour le filtrage morphologique d'images», TS,ce numéro.
[2] C.A.R. Hoare, «Communicating Sequential Processes», International series in computer science, Prentice Hall, 1985 .
[3] A.I. McAuley, «Four State Asynchronous Architectures», IEEE Transactions on Computers, vol. 41, n°2, February, 1992.
[4] C.D.Nielsen, «Evaluation of function blocks for Asynchronous design», EURODAC'94, Grenoble,France, pp. 454-459, Sept. 1994.
[5] B. ElHassan, «Architecture VLSI Asynchrone utilisant la logique différentielleà précharge : Application aux opérateurs arithmétiques», Thèse de l'Institut National Polytechnique de Grenoble(INPG),spécialité Microélectronique, soutenue le 26 septembre 1995 àGrenoble.
[6] I.E. Sutherland, «Micropipelines», Communications ACM, vol. 32, n°6, pp. 720-738, June, 1989.
[7] A. Martin, «Synthesis of Asynchronous VLSI Circuits», Caltech-CS-TR-9328.
[8] K. Van Berkel, «Handshake Circuits - An Asynchronous Architecture for VLSI Programming», Cambridge University Press, 1993.
[9] L. Kleeman, A. Cantoni, « Metastable behavior in digital systems», IEEE Design & Test of Computers, December 1987, pp. 4-19.
[10] F. Robin, M. Renaudin, G. Privat,N. Van Den Bossche, «A Functionally Asynchronous Array-Processor for Morphological Filtering of Greyscale Images», IEE Computers and Digital Techniques, speciiiai section on Asynchronous Architecture,vol. 143, n°5, September, 1996.
[11] K. Van Berkel, «Handshake Circuits -An Asynchronous Architecture for VLSI Programming», Cambridge University Press, 1993 .
[12] A. Marshall, B. Coates, P .Siegel,« Designing an Asynchronous Communications Chip», in IEEE Design and Test of Computers, volume 11, Number 2, Summer 1994, pp. 8-21.
[13] R .F Sproull, I. Sutherland, C. Molnar, «The Counterfow Pipeline Processor Architecture», in IEEE Design and Test of Computers, volume 11, Number 3, Fall 1994, pp. 48-59.
[14] S. Hauck, «Asynchronous Design Methodologies :An Overview», Proceeding of the IEEE, vol.83, n°1, pp. 69-93, January, 1995.
[15] «Asynchronous Digital Circuit Design», G. Birtwistle and A. Davis Editors, Springer, 1995.
[16] L. Lavagno, A. Sangiovanni-Vincentelli, «Algorithms for synthesis andtesting of asynchronous circuits», Kluwer Academic Publishers, 1993.
[17] Proceedings of the second working conference on asynchronous Design Methodologies, May 30-31, 1995, London, England.
[18] M. A. Kishinevsky, A. K. Kondratyev, A. R. Taubin, V. I. Varshavsky, «Concurrent Hardware, The Theory and Practice of Self-Timed Design», Wiley Series in Parallel Computing, Chichester, 1994.
[19] E. Dijkstra, «A discipline of programming», Prentice Hall, Englewood Cliffs NJ, 1976.
[20] E. Dijkstra, «Guarded Commands, Nondeterminancy and formal derivations of programs», Communications ACM,vol. 18, August, 1975.
[21] S.Y Kung, « VLSI Array Processors», Prentice Hall, Thomas Kailath, Series Editors, Eugleurood Cliffs, 1988.
[22] T.E. Williams, «Self timed rings and their application to division», Ph.D dissertation, Stanford university, May, 1991.
[23] T.E. Williams, «Performance of iterative computation in self timed rings», Journal of VLSI signal processing, n°7, pp. 17-31, Feb. 1994.
[24] T. E.Williams, M. Horowitz, «A zero overhead self-timed 160 ns 54 bits CMOS divider» IEEE Journal of solid state circuit,vol.26, pp. 1651-1661, November 1991.
[25] M. Renaudin, B. ElHassan, A. Guyot, «A New Asynchronous Pipeline Scheme :Application to the Design of a Self-Timed Ring Divider», in IEEE Journal of Solid-State Circuits, vol. 31, n°7, pp. 1001-1013, July, 1996.
[26] G. Matsubara, N. Ide, «A low power zero-overhead self-timed division and square root unit combining a single-rail circuit with a dual rail dynamic circuit», in Proceedings of the third international symposium on Advanced Research in Asynchronous Circuits and Systems, April 7-10, 1997, Eindhoven, The Netherlands.
[27] J. Sparo et J. Staunstup, «Delay insensitive multi-ring structures», Integration, the VLSI journal, pp. 313-340, 1993.
[28] U.V. Cummings, A.M. Lines, A.J. Martin, «An Asynchronous Pipelined Lattice Structure Filter», in Proceedings of the International Symposium on Advanced Research in Asynchronous Circuits and Systems, Salt Lake City, Utah, pp. 126-133, November 3-5, 1994.
[29] L.S. Nielsen, J. Sparso, «A low power asynchronous data-path for FIR filter bank», in Proceedings of the International Symposium on Advanced Research in Asynchronous Circuits and Systems, March 18-21, 1996, AizuWakamatsu, Japan.
[30] K. Van Berkel, «Beware the isochronic fork», Integration, the VLSI journal, n° 13, pp. 103-128, 1992.
[31] A.W. Buries, H.H. Goldstine, J. von Neumann, <<Preliminary discussion of the logical design of an electronic computing instrument», in Bell and Newell, Computer structures:readings and examples, Computer Science series, Me Graw-Hill, 1971.
[32] M. Renaudin, B. ElHassan, «The Design of Fast Asynchronous Adder Structures and Their Implementation Using D.C.V.S. Logic »,in Proceedings ISCAS, London, May, 1994.
[33] J.A. Tierno, A.J. Martin, «Low-Energy Asynchronous Memory Design», in Proceedings of the International Symposium on Advanced Research inAsynchronous Circuits and Systems, Salt Lake City, Utah, pp . 176-185,November 3-5, 1994.
[34] A. J. Martin, Steven M. Burns, T. K. Lee, Drazen Borkovic, and Pieter J. Hazewindus, «The Design of an Asynchronous Microprocessor», in Charles L. Seitz editor, Advanced Research in VLSI : Proceedings of the Decennial Caltech Conference in VLSI, pp. 351-373, MIT Press, 1989.
[35] L.S. Nielsen, C. Niessen, J. Sparso, J. Van Berkel, «Low Power Operation Using Self-Timed Circuits and Adaptive Scaling of the Supply Voltage», IEEE Transaction on Very Large Scale Integration (VLSI) Systems, vol. 2, n°4, December, 1994.
[36] K. Van Berkel et Al, «Asynchronous Circuits for Low Power : A DCC Error Corrector», IEEE Design & Test of Computers, Summer 1994, pp. 22-32.
[37] S.B. Furber, J.D. Garside, S. Temple, j. Liu, « AMULET2e : An Asynchronous Embedded Controller», in Proceedings of the third international symposium on Advanced Research in Asynchronous Circuits and Systems, April 7-10, 1997, Eindhoven, The Netherlands.
[38] T.A.Chu,«CLASS :a CAD system for automatic synthesis and verification of asynchronous finite state machines», in Integration, The VLSI Journal, vol. 15, n°3, October 1993, pp. 263-289.
[39] A.Tisserand, «Adéquation arithmétique architecture,problèmes etétudede cas», Thèsede l'EcoleNormale Supérieurede Lyon,spécialité Informatique, soutenueenSeptembre 1997 à Lyon.
[40] M. Renaudin, «AAAA : Asynchronisme et Adéquation Algorithme Architecture», conférence invitée 311édition Journées Adéquation AlgorithmeArchitecture en traitement du signal et des images, 17-19janvier 1996, CNES Toulouse, France.
[41] K. Kessels, P. Marston, «Designing Asynchronous Standby Circuits for Low-Power Pager», in Proceedings of the third international symposium on Advanced Research in Asynchronous Circuits and Systems, April 7-10, 1997, Eindhoven, The Netherlands.