Explicit routing schemes for implementation of cellular automata on processor arrays

Jean-Vivien Millo 1, * Robert De Simone 1
* Auteur correspondant
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, 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.
Type de document :
Article dans une revue
Natural Computing, Springer Verlag, 2013, 12 (3), pp.353-368. <http://link.springer.com/article/10.1007%2Fs11047-013-9378-5>. <10.1007/s11047-013-9378-5>
Liste complète des métadonnées

https://hal.inria.fr/hal-00913949
Contributeur : Team Aoste <>
Soumis le : mercredi 4 décembre 2013 - 15:53:10
Dernière modification le : lundi 5 octobre 2015 - 16:56:20

Identifiants

Collections

Citation

Jean-Vivien Millo, Robert De Simone. Explicit routing schemes for implementation of cellular automata on processor arrays. Natural Computing, Springer Verlag, 2013, 12 (3), pp.353-368. <http://link.springer.com/article/10.1007%2Fs11047-013-9378-5>. <10.1007/s11047-013-9378-5>. <hal-00913949>

Partager

Métriques

Consultations de la notice

155