Refining cellular automata with routing constraints

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
Résumé : Un automate cellulaire (AC) est un tableau infini de cellules, chacune contenant le même automate. La dynamique d'un AC est distribuée entre les cellules, chacune calcule son prochain état comme une fonction des états de ses voisins. Donc, la transmission d'un état entre deux cellules est donc considérée comme faisable directement et instantanément. Quand on s'intéresse à l'implémentation d'un AC sur un système sur puce à plusieurs cores, on ne peut plus considérer la transmission d'un état comme une action abstraite et instantanée. Cette transmission doit suivre le medium d'interconnexion du système sur puce. Ce dernier est habituellement une grille ou un mesh (grille dans laquelle les extrémités opposées sont connectées) correspondant à la topologie logique de l'AC mais finie. Afin de prendre en compte la notion de medium d'interconnexion à un niveau d'abstraction supérieur, par rapport à l'implémentation, nous proposons un raffinement du modèle classique des AC dans lequel la topologie est considérée comme le medium d'interconnexion. Si l'état d'une cellule dépend de son entourage jusqu'à une certaine distance, alors cet état doit être diffusé à tous les voisins jusqu'à cette même distance puis ce que chacun d'eux en a besoin pour calculer son nouvel état. Cela signifie router et diffuser l'état en question dans la topologie. Nous étudions le schéma de routage nécessaire pour mettre en oeuvre efficacement cet algorithme de diffusion d'état. Dans cette solution, chaque router peut localement prédire où envoyer les états en transit afin de garantir la justesse de l'algorithme.
Type de document :
Rapport
[Research Report] RR-8051, INRIA. 2012, pp.15
Liste complète des métadonnées

https://hal.inria.fr/hal-00725878
Contributeur : Team Aoste <>
Soumis le : jeudi 27 septembre 2012 - 10:08:10
Dernière modification le : samedi 17 septembre 2016 - 01:36:43
Document(s) archivé(s) le : vendredi 16 décembre 2016 - 17:07:06

Fichiers

RR8051.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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>

Partager

Métriques

Consultations de
la notice

193

Téléchargements du document

137