Skip to Main content Skip to Navigation
New interface
Journal articles

Explicit routing schemes for implementation of cellular automata on processor arrays

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 : Massively Parallel Processor Array (MPPA) architectures are becoming widely available computing platforms. Because of formal similarities, they are good candidates for implementing Cellular Automata (CA). An essential difference still remains regarding the freedom in communications. In MPPA there is a fixed on-chip network interconnection topology but every CA has its own definition of neighbourhood. While a cell in a CA can be considered as directly connected to its neighbours, these connections correspond to paths in the network of the MPPA. The communications need to be routed and scheduled to reach their proper destination. In previous work we introduced a formal Data-Flow Process Network model named KRG (for K-periodically Routed Graph). Its main feature is to allow regular switching directives. In the present paper we will use it to represent the proper local sequences of routing directives that will efficiently propagate values from cells to cells so as to implement the required CA neighbourhood. We present the Neighbourhood Broadcasting Algorithm (NBA) that computes these routing directives. One should note here that the problem is made more complex as data traffic between distinct source and target cells must be merged, while multicast may save a tremendous amount of communications when values are required in multiple locations. We demonstrate the expressive power of our formalism on the case of a 2D CA where the neighbourhood consists of all cells at Moore distance at most n. Further potential applications of our framework are hinted.
Document type :
Journal articles
Complete list of metadata
Contributor : Team Kairos Connect in order to contact the contributor
Submitted on : Wednesday, December 4, 2013 - 3:53:10 PM
Last modification on : Thursday, August 4, 2022 - 4:52:32 PM

Links full text




Jean-Vivien Millo, Robert de Simone. Explicit routing schemes for implementation of cellular automata on processor arrays. Natural Computing, 2013, 12 (3), pp.353-368. ⟨10.1007/s11047-013-9378-5⟩. ⟨hal-00913949⟩



Record views