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.
This is an extended version of a paper that appeared in: Proc. 2011 Int'l Conf. on High Performance Computing and Simulation (HPCS), Istanbul, Turkey (IEEE, July 2011) 773-779.
A further extended version appeared in: Journal of Cellular Automata 8(1-2) (2013) 5-18.
By: Andreas C. Doering
Published in: RZ3810 in 2011
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .