Skip to Main content Skip to Navigation
Reports

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 :
Reports
Complete list of metadatas

Cited literature [7 references]  Display  Hide  Download

https://hal.inria.fr/hal-00725878
Contributor : Team Kairos <>
Submitted on : Thursday, September 27, 2012 - 10:08:10 AM
Last modification on : Tuesday, May 26, 2020 - 6:50:21 PM
Document(s) archivé(s) le : Friday, December 16, 2016 - 5:07:06 PM

Files

RR8051.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00725878, version 2

Collections

Citation

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

Share

Metrics

Record views

316

Files downloads

243