Saving ressources on cellular automatates cellulaires

O HEEN

IBP-Litp 1996/Th/07: Rapport de Recherche Litp / Litp research reports
139 pages - Janvier/January 1997 - French document.

PostScript : Ko /Kb

Titre / Title: Saving ressources on cellular automatates cellulaires


Résumé : Un automate cellulaire est un assemblage régulier et potentiellement infini d'unités de calcul toutes semblables : les cellules. Il est étonnant de constater la complexité des phénomènes qu'une machine aussi simple permet de modéliser. De fait, les automates cellulaires trouvent des applications variées en informatique, mais aussi en physique et chimie théoriques et même en biologie.
Ce travail traite de l''aspect informatique des automates cellulaires unidimensionnels, qui forment un modèle intéressant du calcul parallèle. Nous reformulons des résultats de complexité dans une optique d'économie des ressources. Plus précisément, nous cherchons à caractériser la taille minimale des cellules pour réaliser certaines tâches et répondons à quelques questions :
- Dans quelles proportions faut-il accroître les ressources pour gagner k pas de calcul ? Pour calculer k fois plus vite ?
- Quel est le « prix » à payer pour envoyer de l'information de cellule en cellule ?
- Quels sont les temps de synchronisation autorisés ?

L'étude systématique de telles questions a conduit à la mise au point d'une nouvelle méthode de simulation d'automates cellulaires mettant en valeur le caractère intrinsèque de certaines propriétés : les résultats s'obtiennent « à l'intérieur » de la théorie des automates cellulaires en termes de produits relativement simple de machines (produit de regroupement).

Mots-clés
Automates Cellulaire Unidemensionnels, Complexité, Accélération Linéaire, Simulation, Géométrie Discrète, Parallélisme Massif, Synchronisation.

Abstract : A cellular automaton is an infinite collection of computing units : the cells. They are all similar and regularly interconnected; It is amazing to observe how such a simple device can modelize complex phenomena. An indeed cellular automata are of great interest in computer science, theoretical physics and chemistry, and even in biology.
In this work we focus on the computational aspects of one dimensional cellular automata. We restate important complexity results with special care to the amount of needed ressources. More precisely, we try to characterize the minimal size of cells in order to perform particular tasks, and give an answer to the following questions :

- What extra ressources are needed to save k steps of computation ? Or to compute k times faster ?
- What is the « price » for sending information from cells to cells ?
- What are the inauthorized synchronization times ?

The systematical study of such questions leads to a new method for simulating cellular automata. This method emphizes the intrinsic aspects of some properties : results can be obtained « from within » the theory of cellular automata thanks to a relatively simple product of machines (the so-called grouping product)

Key-Words
One-Dimensional Cellular Automata, Complexity, Linear Speed-Up, Simulation, Computational Geometry, Massive Parallelism, Synchronization.

Publications internes Litp 1996 / Litp research reports 1996