Thèse de doctorat

Tissu Numérique Cellulaire à Routage et Configuration Dynamiques

Ecole Polytechnique Fédérale de Lausanne
Thèse no 3226

Télécharger

Version abrégée

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

Téléchargez la thèse dans son entier

En trois formats:

Les chapitres à télécharger séparément

Table des matières .pdf .ps .ps.gz
Version abrégée .pdf .ps .ps.gz
Abstract .pdf .ps .ps.gz
Remerciements .pdf .ps .ps.gz

Introduction .pdf .ps .ps.gz

Présentation générale de la thèse, motivations et contributions.
De la configuration des circuits électroniques .pdf .ps .ps.gz
Le chapitre 2 présente les circuits reconfigurables (FPGAs, pour Field Programmable Gate Array) et leur évolution depuis les premiers circuits ne proposant que quelques portes logiques, jusqu'aux plus puissants FPGAs actuels qui exhibent des systèmes d'interconnexion des plus complexes. Leur limitation en terme de routage dynamique sera exposée, justifiant une partie de la présente thèse.
De la bio-inspiration .pdf .ps .ps.gz
Le chapitre 3 présente ce que sont les systèmes bio-inspirés, insistant sur les trois axes de la bio-inspiration, à savoir la phylogenèse, l'ontogenèse, et l'épigenèse. Il se termine par la présentation du projet POEtic, qui a pour but le développement d'un nouveau type de FPGA, un tissu POEtique, visant à faciliter l'implémentation d'applications bio-inspirées mettant en jeu des combinaisons des trois axes de la vie susmentionnés.
Le routage au fil des ans .pdf .ps .ps.gz
Le chapitre 4 enchaîne tout naturellement sur le routage, en présentant les travaux déjà effectués sur des problèmes tels que la recherche du plus court chemin entre deux points. Nous y introduisons les premières solutions logicielles, puis les systèmes matériels qui ont déjà été développés.
Le routage distribué .pdf .ps .ps.gz
En se basant sur les systèmes de routage présentés, le chapitre 5 introduit nos solutions. Les différentes architectures développées sont détaillées, et des tests de vitesse, de taille et de congestion sont effectués pour chaque algorithme, ainsi que pour les différents voisinages.
Le circuit POEtic .pdf .ps .ps.gz
Le chapitre 6 présente en détail l'architecture du circuit réalisé. Un accent particulier est mis sur la partie reconfigurable du circuit, qui fut développée dans le cadre de cette thèse. De plus, nous explicitons la manière dont certaines de ses caractéristiques peuvent efficacement implémenter certains composants de base tels que des registres à décalage ou des compteurs générateurs d'impulsions.
Mécanismes POE .pdf .ps .ps.gz
Ayant défini le circuit, nous nous penchons, dans le chapitre 7, sur son efficacité quant à l'implémentation de mécanismes phylogénétiques, ontogénétiques, et épigénétiques. Ce chapitre démontre notamment l'utilité du routage dynamique et de la reconfiguration partielle.
Conclusion .pdf .ps .ps.gz
Finalement, la conclusion résume nos travaux, explicite les limitations du routage distribué et du circuit POEtic, et propose des extensions aux systèmes développés, qui pourraient être utiles à une potentielle deuxième version du circuit.
Bibliographie .pdf .ps .ps.gz

Webmaster