Admin CliCours
Les automates cellulaires sont le fruit d’une collaboration entre J. von Neumann et S. Ulam dans le milieu des années 50 [vN66]. Initialement conçus dans le but d’étudier les mécanismes d’auto-reproduction, ils sont constitués d’une infinité d’éléments simples, appelés cellules, disposés régulièrement dans un espace qui peut être à une ou plusieurs dimensions. Les cellules ne disposent que d’une mémoire finie représentée par un état et évoluent de manière synchrone en fonction des états de leurs voisines selon une règle commune.
La simplicité mathématique des automates cellulaires, pourtant capables de produire des comportements complexes et difficiles à prévoir, en fait rapidement un modèle privilégié pour l’étude de nombreux phénomènes dans des disciplines aussi diverses que la physique [Den88, Tof84], la biologie [EE93], l’urbanisme [RNSL96] ou l’épidémiologie [Whi07].
C’est à la fin des années 60 que ce modèle commence à être plus formellement étudié grâce notamment à deux résultats majeurs. Le premier est dû à G. Hedlund [Hed69] qui donne une caractérisation purement topologique des automates cellulaires en tant que fonctions agissant sur l’espace des configurations, ouvrant ainsi la voie à une analyse mathématique des automates cellulaires en tant que systèmes dynamiques discrets. Le second résultat est dû à A. R. Smith III qui montre que les automates cellulaires en une dimension (les cellules étant disposées sur une ligne) sont capables de simuler le fonctionnement d’une machine de Turing [Smi71]. Ce résultat permet de démarrer une étude de la puissance de calcul des automates cellulaires, en les comparant notamment aux modèles existants (machines de Turing, machines RAM, circuits, etc.) dans le but de comprendre le gain apporté par le parallélisme massif.
C’est dans ce deuxième axe de recherche, qui s’intéresse aux automates cellulaires en tant que modèles de calcul parallèle, que s’inscrivent les travaux de cette thèse.
La plupart des travaux dans ce domaine s’intéressent aux automates cellulaires unidimensionnels d’une part parce que l’espace des cellules peut ainsi être immédiatement assimilé aux rubans des machines de Turing ce qui permet de comparer les deux modèles sur des entrées et sorties identiques et d’autre part parce que la théorie de la calculabilité passe en général par des codages à l’aide de mots finis unidimensionnels.
Les travaux de A. R. Smith III montrent que tout calcul effectué par une machine de Turing à un ou plusieurs rubans peut être réalisé par un automate cellulaire unidimensionnel en un temps identique et en utilisant le même espace de calcul. À l’inverse, on peut remarquer qu’un calcul effectué par un automate cellulaire en temps f et espace g peut être réalisé par une machine de Turing à un ruban en temps fg et espace g, par « balayages » de l’espace de calcul. Bien que ces remarques laissent penser qu’il existe de nombreux problèmes sur lesquels le parallélisme des automates cellulaires apporte un gain de temps important (d’un facteur égal à la taille de l’espace utilisé), il est très difficile d’obtenir de tels résultats qui reviennent à prouver des bornes inférieures de complexité. Une exception notable concerne les classes de langages reconnus en temps réel, c’est-à-dire le temps le plus court tel que le résultat du calcul ait pu dépendre de toutes les lettres du mot en entrée. F. Hennie a en effet montré que dans le cas des machines de Turing à un ruban les langages reconnus en temps réel sont les mêmes que ceux reconnus en temps linéaire et qu’ils sont rationnels [Hen65], tandis que A. Rosenberg a montré l’existence d’un langage reconnu en temps linéaire par une machine de Turing à plusieurs rubans qui n’était pas reconnu en temps réel sur ce même modèle [Ros67]. Ces deux résultats permettent de déterminer que les automates cellulaires reconnaissent strictement plus de langages que les machines de Turing en temps réel.
En dehors des comparaisons avec les autres modèles de calcul, plusieurs travaux s’intéressent aux relations entre les différentes classes de complexité purement cellulaires. Ici encore les classes correspondant au temps réel et au temps linéaire sont particulièrement étudiées, souvent dans le but d’avancer sur la résolution d’une question ouverte depuis 1972 consistant à déterminer si ces deux classes sont égales pour les automates cellulaires unidimensionnels [Smi72]. Un des résultats les plus significatifs dans cette direction, dû à O. Ibarra et T. Jiang, montre que ces classes sont égales si et seulement si la classe des langages reconnus en temps réel est close par retournement de l’entrée (miroir) [IJ88].
Toujours en une dimension, deux voisinages ont été particulièrement considérés : le voisinage bidirectionnel « usuel » permettant aux cellules de l’automate de tenir compte des états de leurs voisines dans chacune des deux directions lors des transitions, et le voisinage unidirectionnel selon lequel les cellules n’ont accès qu’à l’état de leur voisine dans une seule direction. O. Ibarra et T. Jiang ont par exemple montré que tout langage reconnu en temps linéaire par un automate cellulaire bidirectionnel était également reconnu par un automate cellulaire unidirectionnel [IJ88 tandis que C. Choffrut et K. Culik ont montré que tout langage reconnu en temps réel par un automate cellulaire bidimensionnel était reconnu en temps linéaire par un automate unidirectionnel mais que les automates unidirectionnels étaient strictement plus faibles que les automates bidirectionnels en temps réel [CC84]. V. Poupet a toutefois montré que la diversité des voisinages en une dimension se réduisait à ces seules deux classes [Pou05], tout voisinage étant équivalent au voisinage usuel s’il s’étend dans les deux directions et au voisinage unidirectionnel sinon.
Enfin, pour compléter l’étude des classes de complexité sur les automates cellulaires unidimensionnels, quelques techniques de nature algorithmique ont été développées. En particulier, comme pour les machines de Turing, des théorèmes d’accélération linéaire et constante ont été établis en reprenant les idées des constructions utilisées sur les autres modèles de calcul [MR92], mais également des techniques purement parallèles n’ayant pas d’équivalent sur les modèles séquentiels comme la synchronisation de cellules (ligne de fusiliers) [Maz86, Maz96].
En parallèle de ces travaux en une dimension, certaines études ont également été menées sur les automates cellulaires en deux dimensions ou plus. Si les automates cellulaires en deux dimensions pouvaient sembler irréalisables en pratique il y a quelques décennies, la miniaturisation et la baisse des coûts de production des processeurs ont permis le développement rapide du calcul parallèle. Bien qu’imaginés un demi-siècle plus tôt, les automates cellulaires bidimensionnels sont aujourd’hui un excellent modèle théorique pour l’analyse des possibilités d’objets tels que les Fieldprogrammable gate array (FPGA) [PG99, KMH01] ou les applications de calcul générique sur processeurs graphiques (GPGPU) [BC07, FNI17, PA08] qui disposent de milliers d’éléments de calcul disposés régulièrement sur une grille plane.
En deux dimensions la situation est toutefois sensiblement plus complexe. Au cours d’un calcul les informations peuvent se déplacer dans toutes les directions et il peut être difficile d’assurer que deux informations se rencontrent. Le choix du voisinage utilisé, qui définit directement le graphe de communication des cellules, influe donc fortement sur les possibilités algorithmiques de l’automate en ce qui concerne les classes de faible complexité où les déplacements d’information doivent être faits de manière optimale.
La plupart des travaux sur les automates cellulaires en deux dimensions concernent les automates fonctionnant sur les voisinages de von Neumann (quatre plus proches voisines) ou de Moore (huit plus proches voisines). Ces voisinages représentent tous les deux des extensions naturelles en deux dimensions du voisinage usuel unidimensionnel. Une grande partie des constructions employées en une dimension se généralise donc assez facilement aux automates fonctionnant sur ces voisinages, comme par exemple l’accélération constante et l’accélération linéaire [Ter04]. Il faut noter toutefois que l’accélération constante est obtenue de manière très différente sur ces deux voisinages, chaque technique pouvant être vue comme une extension de la technique utilisée en une dimension.
Il existe cependant aussi des résultats en deux dimensions qui dépassent ceux disponibles en une dimension. En effet V. Terrier est parvenue à montrer que les classes du temps linéaire et du temps réel sont différentes lorsqu’on considère les automates fonctionnant avec le voisinage de Moore [Ter99]. Elle a ensuite étendu ce résultat à une classe plus large de voisinages, mais sans toutefois réussir à inclure le voisinage de von Neumann [Ter04]. L’étude des autres voisinages reste très incomplète mais on peut néanmoins noter des résultats encourageants comme un théorème de M. Delacourt et V. Poupet [DP07] qui apporte une première notion d’équivalence entre certains voisinages en deux dimensions. Les théorèmes d’accélération constante et linéaire ont aussi été étendus à des familles de voisinages sans toutefois parvenir à une généralisation complète [Ter04].
1 Introduction |
Télécharger le document complet
