About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
HPCS 2011
Conference paper
Determination of one-way bandwidth of cellular automata using Binary Decision Diagrams
Abstract
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 send 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. © 2011 IEEE.