Refining cellular automata with routing constraints

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