Determination of One-Way Bandwidth of Cellular Automata Using Binary Decision Diagrams
Andreas C. Doering
Cellular Automata are an inherently parallel computing architecture and can be scaled close to the physical limits due to the local-only data exchange. For economical and technical reasons application of cellular automata as computer architecture requires the use of partitions that are assembled into larger units, similar to memory in current systems (memory chips, Dual-In-line Memory Modules, etc.). This requires the exchange of the cell state at the chip boundaries. In this paper we consider the analysis of the required bandwidth over a chip boundary when a one-way protocol is used. The analysis algorithm counts the number of equivalence classes with respect to the cell states on the sending side. When the states along the chip boundary are combined, a closed form solution for the number of equivalence classes is derived. The algorithm can be implemented using Binary Decision Diagrams, and we give results for several example cellular automata.
Keywords: Spatial partitioning, binary decision diagram, equivalence relation, finite function factorization