Explicit routing schemes for implementation of cellular automata on processor arrays - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Natural Computing Année : 2013

Explicit routing schemes for implementation of cellular automata on processor arrays

Résumé

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.

Dates et versions

hal-00913949 , version 1 (04-12-2013)

Identifiants

Citer

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⟩
100 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More