Embedding Universal Delay-Insensitive Circuits in Asynchronous Cellular Spaces

• Autorzy: Lee J. , Adachi S. , Peper F. , Morita K.
• Języki publikacji: EN

Abstrakty

EN

Asynchronous Cellular Automata (ACA) are cellular automata which allow cells to be updated at times that are random and independent of each other. Due to their unpredictable behavior, ACA are usually dealt with by simulating a timing mechanism that forces all cells into synchronicity. Though this allows the use of well-established synchronous methods to conduct computations, it comes at the price of an increased number of cell states. This paper presents a more effective approach based on a 5-state ACA with von Neumann neighborhood that uses rotation- and reflection-symmetric transition rules to describe the interactions between cells. We achieve efficient computation on this model by embedding so-called Delay-Insensitive circuits in it, a type of asynchronous circuits in which signals may be subject to arbitrary delays, without this being an obstacle to correct operation. Our constructions not only imply the computational universality of the proposed cellular automaton, but also allow the efficient use of its massive parallelism, in the sense that the circuits operate in parallel and there are no signals running around indefinitely in the circuits in the absence of input.

Słowa kluczowe

EN

cellular automata; asynchronous systems; delay-insensitive circuits

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2003
• Tom: Vol. 58, nr 3,4
• Strony: 295--320
• Opis fizyczny: Bibliogr. 31 poz., tab., wykr.

Twórcy

autor

Lee J.

• Communications Research Laboratory, Nanotechnology Group, 588-2 Iwaoka, Iwaoka-cho, Nishi-ku, Kobe 651-2492, Japan

autor

Adachi S.

• Communications Research Laboratory, Nanotechnology Group, 588-2 Iwaoka, Iwaoka-cho, Nishi-ku, Kobe 651-2492, Japan

autor

Peper F.

• Communications Research Laboratory, Nanotechnology Group, 588-2 Iwaoka, Iwaoka-cho, Nishi-ku, Kobe 651-2492, Japan

autor

Morita K.

• Department of Information Engineering, Higashi-Hiroshima 739-8527. Japan

Bibliografia

• [1] Adachi S., Lee J. and Peper F.: On signals in asynchronous cellular spaces, IEICE Trans. Information and Systems, 2003, accepted.
• [2] Adachi S., Peper F. and Lee J.: Computation by asynchronously updating cellular automata, J. Stat. Phy., 2003, accepted.
• [3] Banks E. R.: Universality in cellular automata. IEEE 11th Ann. Symp. on Switching and Automata Theory CA, 1970.
• [4] Bersini H. and Dectours V.: Asynchrony induces stability in cellular automata based models. Artificial Life IV, (R. A. Brooks R. A. and Maes P. Eds.). MIT Press. MA, 1994,382-387.
• [5] Blok H. J. and Bergersen B.: Synchronous versus asynchronous updating in the “game of life”, Phy. Rev. E, 59, 1999, 3876-3879.
• [6] Caër G. L.: Comparison between simultaneous and sequential updating in 2"+l -1 cellular automata. Physica A, 157, 1989, 669-687.
• [7] Capcarrère M.: Cellular Automata and other Cellular Systems: Design & Evolution. Ph. D. Thesis, Swiss Federal Institute of Technology Lausanne, 2002.
• [81 Choi M. Y. and Huberman B. A.: Digital dynamics and the simulation of magnetic systems, Phy. Rev. В, 28, 1983,2547-2554.
• [9] Codd E. F.: Cellular Automata, Academic Press, NY, 1968.
• [10] Cori R., Metivier Y. and Zielonka W.: Asynchronous mapping and asynchronous cellular automata. Information and Computation, 106, 1993, 159-202.
• [11] Golze U. and Priese L.: Petri net implementations by a universal cell space. Information and Control, 53, 1982, 121-138.
• [12] Hauck S.: Asynchronous design methodologies: an overview. Proc. IEEE, 83(1), 1995, 69-93.
• [13] Ingerson Т. E. and Buvel R. L.: Structures in asynchronous cellular automata, Physica D, 10. 1984, 59-68.
• [14] Keller R. M.: Towards a theory of universal speed-independent modules, IEEE Trans. Computers, C-23(l), 1974,21-33.
• [15] Lee J., Peper F., Adachi S. and Morita K.: Universal delay-insensitive circuits with bi-directional and buffering lines, IEEE Trans. Computers, 2003, accepted.
• [16] Lumer E. D. and Nicolis G.: Synchronous versus asynchronous dynamics in spatially distributed systems, Physica D, 71, 1994, 440-452.
• [17] Muller D. E. and Bartky W. S.: A theory of asynchronous circuits, Proc. Int. Symp. on the Theory of Switching, Harvard University Press, 1959, 204-243.
• [18] Nakamura K.: Asynchronous cellular automata and their computational ability, Systems, Computers, Controls, 5(5), 1974, 58-66.
• [19] Nakamura K.: Synchronous to asynchronous transformation of polyautomata, J. Computer and System Sciences, 23, 1981, 22-37.
• [20] Nehaniv C. L.: Evolution in asynchronous cellular automata, Artificial Life VIII, (Standish R. H., Bedau M. A. and Abbass H. A. Eds.), MIT Press, MA, 2003, p. 65.
• [21] Neumann J. von: Theory of Self-Reproducing Automata, (A.W. Burks Ed.), University of Illinois Press, 1966.
• [22] Patra P.: Approaches to Design of Circuits for Low-Power Computation, Ph.D. thesis, University of Texas at Austin, 1995.
• [23] Peper F., Lee J., Adachi S. and Mashiko S.: Laying out circuits on asynchronous cellular arrays: a step towards feasible nanocomputers? Nanotechnology, 14(4), 2003,469-485.
• [24] Priese L.: A note on asynchronous cellular automata, J. Computer and System Sciences, 17, 1978, 237-252.
• [25] Rajewsky N., Santen L., Schadschneider A. and Schreckenberg M.: The asymmetric exclusion process: comparison of update procedures, J Stat. Phy., 92, 1998, 151-194.
• [26] Schönfisch В. and de Roos A.: Synchronous and asynchronous updating in cellular automata, BioSystems, 51, 1999, 123-143.
• [27] Serizawa Т.: Three-state Neumann neighbor cellular automata capable of constructing self-reproducing machines, Systems and Computers in Japan, 18(4), 1987, 33-40.
• [28] Toffoli T. and Margolus N.: Cellular Automata Machines, MIT Press, MA, 1987.
• [29] Varshavsky V. and Marakhovsky V.: Global Synchronization of Asynchronous Arrays in Logical Time, 2nd AIZU Int. Symp. Parallel Algorithms/Architecture Synthesis, (Mirenkov N. et al. Eds.), IEEE Press, 1997, 207-215.
• [30] Wang W.: An asynchronous two-dimensional self-correcting cellular automaton. Ph. D. thesis, Boston University, 1991.
• [31] Wolfram S.: Cellular Automata and Complexity, Addison-Wesley, MA, 1994.