Skip to Main content Skip to Navigation

Refining cellular automata with routing constraints

Jean-Vivien Millo 1, * Robert de Simone 1
* Corresponding author
1 AOSTE - Models and methods of analysis and optimization for systems with real-time and embedding constraints
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Paris-Rocquencourt, Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : A cellular automaton (CA) is an infinite array of cells, each containing the same automaton. The dynamics of a CA is distributed over the cells where each computes its next state as a function of the previous states of its neighborhood. Thus, the transmission of such states between neighbors is considered as feasible directly, in no time. When considering the implementation of a cellular automaton on a many-cores System-on-Chip (SoC), this state transmission is no longer abstract and instantaneous, but has to follow the interconnection medium of the SoC. It is usually a grid or a mesh matching the underlying topology of the CA but finite. In order to consider such constraints at a higher level, we propose a refinement of the classical model of CA where the topology is considered as the communication medium. If the state of a cell depends on its neighbors up to a certain distance, then a given state must be broadcasted to all its neighbors at the same distance, as they all require it to compute their next state. It means routing and duplicating the state in the topology. We study the routing patterns needed to efficiently implement such state broadcasting algorithm. We provide a solution by which each router can locally predict where to redirect the states to correctly and efficiently implement this broadcasting algorithm.
Document type :
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download
Contributor : Team Kairos Connect in order to contact the contributor
Submitted on : Thursday, September 27, 2012 - 10:08:10 AM
Last modification on : Friday, January 21, 2022 - 3:15:51 AM
Long-term archiving on: : Friday, December 16, 2016 - 5:07:06 PM


Files produced by the author(s)


  • HAL Id : hal-00725878, version 2



Jean-Vivien Millo, Robert de Simone. Refining cellular automata with routing constraints. [Research Report] RR-8051, INRIA. 2012, pp.15. ⟨hal-00725878v2⟩



Les métriques sont temporairement indisponibles