Cellular Automata have their roots in von Neumann’s research on self-reproduction, but since their debut they have been used for a much wider variety of purposes. In recent years they have attracted attention as architectures for nanocomputers–computers to be realized by nanotechnology. Their highly regular structure is considered an important advantage in this context, because of the potential for fabrication by bottom-up techniques like molecular self-assembly. This article gives an overview of research on cellular automaton-based nanocomputers, and discusses their strong points and challenges.
TopIntroduction
Research into nanocomputer architectures have increasingly attracted attention in recent years, driven by the realization that improvements in integration densities can only be sustained at an unchanged pace if new approaches are adopted. As top-down fabrication methods like optical lithography are gradually facing their technological and economical limits, alternatives are called for. Bottom-up fabrication methods are still in their early stages of development, but, being based on the self-assembling properties inherent in molecules, they offer much promise for nanocomputers. With expected changes in fabrication method, there will also be changes in the architectures of the resulting computers: it is unlikely that the complicated structures of von Neumann computer architectures can be produced by top-down methods in the nanometer-scale regime. Rather, future computers are expected to have very regular, repetitive, structures, or–alternatively–random structures.
How can these structures be employed for meaningful computational tasks? It will require the allocation of hardware resources to tasks according to some directives or algorithm. When hardware needs to be (re)configured for a computation, regular structures offer a profound advantage over random structures, because regularity provides us with information about a structure, which translates into more control. Though random structures are easier to fabricate than regular structures, they are harder to reconfigure in a controlled way, as a result of which configuration will likely be limited to an initial phase, directly after fabrication (Stan, Franzon, Goldstein, Lach, and Ziegler, 2003). Since regular structures do better in this regard, this is a key motivation for the research on cellular automata for nanocomputer architectures.
This article gives an overview of such research. After giving an informal definition of cellular automata, we discuss the complexity of cells in such architectures–an important issue, because of its relation with the efficiency of physical implementations. This is followed by a short overview of cellular automata used for VLSI implementations of specific applications. General-purpose cellular automata take over the remainder of this article, claiming their place as architectures that have a significant potential for manufacturing by bottom-up techniques. After a short history on cellular automaton based nanocomputers, we describe our recent work on asynchronous cellular automata in this framework. These models carry the local character of cellular automata one step further by relaxing the need for all cells to be timed by a global clock signal. We discuss how the randomness of asynchronous updating is not necessarily an impediment to achieve a deterministic computation process, and how it can be efficiently used. Fault- and Defect-tolerance will also be discussed, before we finish with a future outlook on cellular automaton based nanocomputers.