Faculté informatique et communications IC, Section d'informatique, Institut des systèmes informatiques et multimédias ISIM (Laboratoire de systèmes logiques LSL)

Tissu numérique cellulaire à routage et configuration dynamiques

Thoma, Yann ; Sanchez, Eduardo (Dir.)

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2005 ; no 3226.

Add to personal list
    Summary
    In the design of new machines or in the development of new concepts, mankind has often observed nature, looking for useful ideas and sources of inspiration. The design of electronic circuits is no exception, and a considerable number of realizations have drawn inspiration from three aspects of natural systems : the evolution of species (Phylogenesis), the development of an organism starting from a single cell (Ontogenesis), and learning, as performed by our brain (Epigenesis). These three axes, grouped under the acronym POE, have for the most part been exploited separately : evolutionary principles allow to solve problems for which it is hard to find a solution with a deterministic method, while some electronic circuits draw inspiration from healing process in living beings to achieve self-repair, and artificial neural networks have the capability to efficiently execute a wide range of tasks. At this time, no electronic tissue capable of bringing them together seems to exist. The introduction of reconfigurable circuits called Field Programmable Gate Arrays (FPGAs), whose behavior can be redefined as often as desired, made prototyping such systems easier. FPGAs, by allowing a relatively simple implementation in hardware, can considerably increase the systems' performance and are thus extensively used by researchers. However, they lack plasticity, not being able to easily modify themselves without an external intervention. This PhD thesis, developed in the framework of the European POEtic project, proposes to define a new reconfigurable electronic circuit, with the goal of supplying a new substrate for bio-inspired applications that bring all three axes into play. This circuit is mainly composed of a microprocessor and an array of reconfigurable elements, the latter having been designed during this thesis. Evolutionary processes are executed by the microprocessor, while epigenetic and ontogenetic mechanisms are applied in the reconfigurable array, to entities seen as multicellular artificial organisms. Relatively similar to current commercial FPGAs, this subsystem offers however some unique features. First, the basic elements of the array have the capability to partially reconfigure other elements. Auto-replication and differentiation mechanisms can exploit this capability to let an organism grow or to modify its behavior. Second, a distributed routing layer allows to dynamically create connections between parts of the circuit at runtime. With this feature, cells (artificial neurons, for example) implemented in the reconfigurable array can initiate new connections in order to modify the global system behavior. This distributed routing mechanism, one of the major contributions of this thesis, induced the realization of several algorithms. Based on a parallel implementation of Lee's algorithm, these algorithms are totally distributed, no global control being necessary to create new data paths. Four algorithms have been defined implemented in hardware in the form of routing units connected to 3, 4, 6, or 8 neighbors. These units are all identical and are responsible for the routing processes. An analysis of their properties allows us to define the best algorithm, coupled with the most efficient neighborhood, in terms of congestion and of the number of transistors needed for a hardware realization. We finish the routing chapter by proposing a fifth algorithm that, unlike the previous ones, is constructed only through local interactions between routing units. It offers a better scalability, at the price of increased hardware overhead. Finally, the POEtic chip, in which one of our algorithms has been implemented, has been physically realized. We present different POE mechanisms that take advantage of its new features. Among these mechanisms, we can notably cite auto-replication, evolvable hardware, developmental systems, and self-repair. All of these mechanisms have been developed with the help of a circuit simulator, also designed in the framework of this thesis.
    Résumé
    A l'instar des premiers concepteurs d'avions, l'homme a toujours observé la nature, qui lui a fourni des pistes lors de la création de nouvelles machines ou de nouveaux concepts. Les circuits électroniques ne font pas exception, et les trois axes de la vie que sont l'évolution des espèces (Phylogenèse), le développement de l'organisme à partir d'une seule cellule (Ontogenèse), ainsi que l'apprentissage dont notre cerveau est capable (Epigenèse), ont vu nombre de réalisations s'en inspirer. Ces trois axes, qui forment l'acronyme POE, ont été, pour la plupart des réalisations, exploités séparément : les principes de l'évolution permettent de résoudre des problèmes pour lesquels il est difficile d'obtenir une solution de façon déterministe, des circuits électroniques tirent profit des concepts d'autoréparation du vivant, et les réseaux de neurones artificiels sont capables d'effectuer efficacement un grand nombre de tâches. Leur réunion en un seul tissu électronique n'a en revanche pas encore vu le jour. Concernant la réalisation matérielle de tels systèmes, l'avènement des circuits reconfigurables FPGAs, dont il est possible de redéfinir un nombre quasi infini de fois le comportement, en a facilité le prototypage. Ils permettent en effet d'accélérer l'exécution d'une tâche, par le parallélisme matériel qu'ils offrent, et ont été grandement exploités par les chercheurs. Toutefois, ils manquent de plasticité, leur comportement ne pouvant facilement se modifier lui-même sans une intervention extérieure. Cette thèse, qui s'insère dans le cadre du projet européen POEtic, se propose de définir un nouveau circuit électronique reconfigurable, dans l'optique de fournir un nouveau substrat aux applications bio-inspirées mettant en jeu ces trois axes. Ce circuit est composé d'un microprocesseur, et d'un tableau d'éléments reconfigurables, ce dernier ayant été réalisé par nos soins. Les processus évolutifs sont exécutés par le premier, alors que l'épigenèse et l'ontogenèse prennent place dans le deuxième, sous la forme d'organismes artificiels multicellulaires. Relativement semblable aux FPGAs commerciaux actuels, ce sous-système offre cependant de nouvelles caractéristiques intéressantes. Premièrement, les éléments de base du tableau ont la capacité de reconfigurer partiellement d'autres éléments. Des mécanismes d'auto-réplication et de différenciation peuvent alors l'exploiter pour laisser un organisme artificiel croître ou modifier son comportement. Deuxièmement, un niveau de routage distribué offre la possibilité de créer des connexions entre différentes parties du circuit pendant son fonctionnement. Les cellules qui y sont implémentées, notamment les neurones artificiels, peuvent alors initier de nouvelles connexions, de manière à modifier le comportement global du système. Ce routage distribué, qui constitue l'un des points importants de cette thèse, a vu la réalisation de plusieurs algorithmes. Basés sur une implémentation parallèle de l'algorithme de Lee, ils sont totalement distribués, c'est-à-dire qu'aucun contrôle global n'est nécessaire à la création de chemins de données. Quatre algorithmes sont ainsi définis et décrits matériellement sous la forme d'unités de routage reliées à leurs 3, 4, 6, ou 8 voisines, toutes identiques, qui gèrent les processus de routage. Une analyse de leurs propriétés nous permet de définir le meilleur algorithme à coupler au plus efficace des voisinages, en terme de congestion, par rapport au nombre de tranii sistors nécessaires à leur réalisation. Nous terminons sur le routage en proposant un cinquième algorithme, qui, contrairement aux quatre précédents, n'est construit que sur des communications locales entre unités de routage. Il offre ainsi, au prix d'un coût matériel supplémentaire, une meilleure scalabilité au système complet. Finalement, le circuit POEtic, sur lequel un de nos algorithmes de routage a été implémenté, a été physiquement réalisé. Nous présentons différents mécanismes POE qui tirent profit de ses caractéristiques nouvelles et qui peuvent y être embarqués. Parmi ces mécanismes, nous pouvons citer notamment l'auto-réplication, le matériel évolutif, les systèmes développementaux, et l'autoréparation, qui ont été développés grâce à un simulateur du circuit, également conçu durant cette thèse.