Cellular Automata on the Micron Automata Processor

Authors:Wang, Ke, Department of Computer ScienceUniversity of Virginia Skadron, Kevin, Department of Computer ScienceUniversity of Virginia

A cellular automaton (CA) is a well-studied and widely used time-evolving discrete model. CAs are studied in many fields of science, such as computability theory, mathematics, physics, complexity science, theoretical biology and microstructure modeling. Some CA models have been proven to be Turing Complete, such as the elementary cellular automaton (ECA) of Rule-110 and Conways Game of Life. Micron's Automata Processor (AP) is a hardware implementation of non-deterministic finite automata (NFAs). The core feature of the AP, the state transition element (STE), was designed for highly parallel recognition of complex patterns in big data. The additional features of the AP, the on-chip Boolean and counter elements, theoretically expand the APs computation ability beyond those of traditional NFAs. However, the computational power of the AP remains undiscovered. To answer this question, we implement CAs on the AP, and use the successful implementations to demonstrate the AP's Turing Completeness. When mapping CAs on to the AP, one will face four major implementation diffculties: self-evolution, memory, communication, and computation of evolution rules. To handle these implementation challenges, this paper illustrates several novel primitives, including splitting the input symbol set into data symbols and instruction symbols, storing the live/dead states of a CA cell with activation/deactivation status of an STE, gathering the information of neighbor cells by a star structure or a ring structure, and translating evolution rules of CAs into Boolean logic or the combination of Boolean logic and counters. By using these primitives, we successfully implement and run the examples of ECA Rule 110 and Game of Life on the AP simulator. These results indicate that the AP chip implements a Turing-complete computational model. We also show several optimization strategies to improve performance and reduce the resource usage.

All rights reserved (no additional license for public reuse)
Source Citation:

Wang, Ke, and Kevin Skadron. "Cellular Automata on the Micron Automata Processor." University of Virginia Dept. of Computer Science Tech Report (2015).

University of Virginia, Department of Computer Science
Published Date: