1.1.1 Von Neumann's Universal Constructor
2.1 Biological Inspiration in Embryonics
2.1.2 Bio-Inspired Systems and the POE Model
2.1.3 The POE Model: Phylogeny
3.2 Von Neumann's Universal Constructor
3.2.1 Von Neumann's Self-Replicating Machines
3.4 Self-Replicating Cellular Automata in Embryonics
3.4.1 The Requirements of the Embryonics Project
3.4.2 A Self-Replicating Turing Machine: Perrier's Loop
3.4.3 A Novel Self-Replicating Loop: Description
3.5 Towards a Digital Hardware Implementation
4.1 A New Multiplexer-Based FPGA: MuxTree
4.1.1 The Programmable Function
4.1.2 The Programmable Connections
4.2.1 Testing Digital Circuits
4.2.3 The Programmable Function
4.2.4 The Programmable Connections
4.3.1 Repairing Digital Circuits
4.3.3 Self-Replication Revisited
5.3 MuxTreeSR outside of Embryonics
The main obstacles to the widespread use of application-specific arrays of processors are, of course, development time and price: the time required for the design of such systems is usually measured in months, if not years, while the cost of custom VLSI circuits makes such designs too expensive for most situations.
A major goal of the Embryonics project, the research project which provides the framework for this thesis, is the development of such an array of processors, or cells, inspired by biological cellular processes, and in particular by the embryological processes of living beings. These processors, relatively simple binary decision machines, are remarkable in that they are easily parametrizable in both size and functionality. This property derives from the use of a relatively new type of high-complexity reprogrammable circuits, commonly referred to as Field-Programmable Gate Arrays (FPGAs). These circuits provide a homogeneous surface of general-purpose logic elements which can be configured as often as desired to implement any combinational or sequential circuit (within the limits imposed by the number of available elements).
Unfortunately, commercial FPGAs are not well adapted to the implementation of arrays of processors, for the following main reasons:
The main goal of the thesis was therefore to design a novel type of FPGA, known as MuxTree, drawing inspiration from the world of biological organism so as to render it capable of built-in self-test and self-repair, as well as of being easily configured as an array of identical processors (the cells).
The configuration of large arrays of programmable logic elements of variable size and shape with a repetitive pattern of identical processing elements bears a strong resemblance to the problem of self-replication in cellular automata. We thus exploited the knowledge base provided by the latter domain to develop an approach which could be applied to the former. The first result of this research was the development of a novel self-replicating cellular automaton, loosely based on existing solutions. The self-replication scheme used in the automaton to perform self-replication was then simplified so as to be easily implemented in hardware and, appropriately modified, was used to direct the configuration of the array of MuxTree elements, allowing an easy partitioning into blocks of elements. The size of these blocks, and thus the size of the processors, can thus be programmed by the user to fit a particular application.
The second main research topic in this thesis concerns the development of self-test and self-repair logic for the MuxTree element. The main challenge in this area was implementing the desired features with a minimal amount of logic, while respecting a set of rigid constraints imposed by our desire to follow a biological inspiration. In the design of the self-test mechanism, we adopted a hybrid approach which operates partly on-line (i.e., while the circuit is functioning) and partly off-line (while the circuit is being configured), but always transparently to the user. To achieve self-repair, we implemented a relatively simple reconfiguration mechanism which automatically replaces the faulty elements and reroutes the array's connections. While the reconfiguration process is not always completely transparent, our mechanism does allow the circuit to resume operation without losing its internal state.
The initial goals were, for the most part, met and the circuit was implemented in the form of a set of demonstration modules (the Biodules 603). Using these modules, we were able to construct a small prototype and demonstrate our FPGA's ability to self-replicate its configuration and to self-repair in the presence of faults.
Les obstacles principaux à une généralisation de l'usage des réseaux de ce type sont, évidemment, le temps de développement et le prix: le temps nécessaire pour concevoir de tels systèmes se mesure en général en mois, voire en année, tandis que les coûts de circuits VLSI spécialisés les rendent trop coûteux pour la plupart des applications.
Un des buts principaux du projet Embryonique, le cadre dans lequel cette thèse s'inscrit, est le développement de tels réseaux de processeurs, ou cellules, inspiré par les principes de la biologie moléculaire, et en particulier par ceux de l'embryologie des êtres vivants. Tant la taille que la fonctionnalité de ces processeurs, des machines de décision binaire relativement simples, peuvent être dimensionnées de manière remarquablement simple. Cette propriété vient de l'utilisation d'un type relativement nouveau de réseaux logiques reprogrammables à haute complexité, appelés FPGAs (Field-Programmable Gate Arrays). Ces réseaux offrent une surface homogène d'unités logiques universelles qui peuvent être reconfigurées à volonté de manière à implémenter n'importe quel circuit combinatoire ou séquentiel (dans la limite du nombre d'unités disponibles).
Malheureusement, les FPGAs commerciaux ne sont pas bien adaptés à l'implémentation de réseaux de processeurs pour les raisons suivantes:
Le principal objectif de cette thèse peut donc se résumer à la conception d'un nouveau type de FPGA, appelé MuxTree, inspiré par la biologie. Plus particulièrement, ce sont les qualités d'autoréparation et d'autotest, inspirées par les organismes vivants, ainsi que la capacité à être facilement décomposé en réseaux de processeurs (les cellules) qui ont motivé la conception de ce nouveau FPGA.
Dans ce travail, nous avons exploité les connaissances existantes dans le domaine des automates cellulaires autoréplicateurs pour développer des techniques applicables aux grands réseaux logiques reprogrammables. En effet, la configuration de ceux-ci, structurés en éléments de forme et de taille régulières, ressemble beaucoup au problème de l'autoréplication dans les réseaux cellulaires.
Ce premier axe de recherche a conduit au développement d'un nouveau type d'automates cellulaires autoréplicateurs partiellement inspirés de solutions déjà existantes. La stratégie d'implémentation de l'autoréplication sur cet automate a été simplifiée au maximum de manière à l'adapter aisément sur le matériel. Cette stratégie a été ensuite appliquée aux FPGAs pour permettre la configuration de réseaux cellulaires matériels. Ce processus, appliqué sur une structure régulière composées d'éléments MuxTree, permet de partitionner très simplement cette dernière en blocs. La taille de ceux-ci et, par conséquent, la taille des processeurs réalisés, est ajustable en fonction de l'application visée.
Le deuxième axe de recherche dans cette thèse est le développement d'une logique embarquée pour l'autotest et l'autoréparation d'éléments MuxTree. Un défi important a été imposé par le désir de minimiser la quantité de logique nécessaire pour ces fonctions tout en respectant les contraintes de l'inspiration biologique. Le mécanisme d'autotest que nous avons mis au point repose sur une approche hybride, invisible pour l'utilisateur, qui combine le test en ligne (pendant le fonctionnement de l'application) et le test hors ligne (pendant le chargement de l'application). Quant au mécanisme d'autoréparation, nous avons conçu et implémenté une stratégie simple basée sur le remplacement des éléments fautifs et le reroutage de signaux du réseau. Bien que cette méthode ne soit pas complètement transparente, elle permet néanmoins de reprendre l'exécution normale de l'application sans perdre l'état interne.
Les objectifs initiaux ont été en grande partie atteints et le circuit a été implémenté sous la forme de modules de démonstration (Biodule 603). Ces derniers nous ont permis de construire un prototype réduit et de démontrer les capacités de notre FPGA à s'autorépliquer et à s'autoréparer.
First, of course, my parents and family, who have always supported me and have been willing to make considerable sacrifices in order to give me all possible advantages in life. Needless to say, without them I would not be where I am today.
Daniel Mange, much more than a thesis director: a mentor and a friend. He is the true driving force of the Embryonics project, and he has taught me much, both directly and by providing a shining example.
The group of experts who shouldered the (hopefully not too heavy) burden of reading and appraising my work: Miron Abramovici, Giovanni Coray, Pierre Kuonen, and Mariagiovanna Sami, as well as Jean-Daniel Nicoud, head of the department. My heartfelt thanks for their precious feedback and for their favorable evaluation.
The "ontogenetic team", the exceptional group of people with whom I had the extreme pleasure to work: André Stauffer, Jacques Zahnd, and our colleagues at CSEM, Pierre Marchal, Pascal Nussbaum, and Christian Piguet. If this thesis is worth something, it is also thanks to them.
Marlyse Taric, our secretary, always there for us all. It remains a mystery to me how she manages to do all she does while working in our lab only part-time.
I will take this opportunity to thank all those members of the laboratory who have contributed to make my stay so pleasant. I dislike unnecessary seriousness and thus my remarks will be (hopefully) humorous. But do not let my glibness mislead you: I am sincerely grateful to all these people for making the past few years a thoroughly enjoyable and rewarding experience.
To begin with, those with whom I kindly condescend to share my office: Emeka Mosanya, beer-guzzler extraordinaire, to whom I owe the redoubtable experience of tasting a mitraillette (trust me, you don't want to know...); Dominik Madon, resident political activist, office DJ, and yearly winner of the lab's "best-looking hair" competition; Mathieu Capcarrère, whose low resistance to alcohol is more than compensated by his willingness to retrieve lake-bound volleyballs. I can now proudly claim that, all their efforts notwithstanding, I still managed to finish my thesis.
André "Chico" Badertscher, wizard of the soldering iron, heroic glider pilot, and unchallenged champion of the truly execrable pun. His contributions to this thesis are extensive: to his outstanding technical skills and ability to work under stress goes the credit for assembling the prototype, and, more importantly, to his punctual restocking of the lab's cafeteria I owe the caffeine required for any successful thesis.
The Colombian armada, from its lider maximo , Eduardo Sanchez, to its brave lieutenants, Carlos Andrés Peña, Andrés Perez-Uribe, and Héctor Fabio Restrepo, not to forget its honorary member, Jean-Michel Puiatti (who, Italian origins notwithstanding, is probably the greatest hispanophile of them all). Through their influence, Spanish (well... Colombian) will soon become the official language of the LSL.
The boys from Valais: Jacques-Olivier "Jacko" Haenni, the omnipotent (if far-from-omniscient) sysadmin, and Jean-Luc Beuchat, he of the doubtful musical taste.
Moshe Sipper, keeper of the list of references (which has now reached such gargantuan proportions that it is likely to soon achieve critical mass) and official lab trekkie.
Finally, some oldies but goodies: Serge Durand, who introduced me to the joys of Embryonics, before leaving our beautiful ivory tower for the crass and material world of industrial R&D; Christian Iseli, the much-missed ex-sysadmin, and his family, whose presence brought considerable surges of random noise and frantic activity; Marco Tomassini, who single-handedly doubled the lab's Italian contingent during his all-too-brief stay.
This work was partially sponsored by grants 20-39391.93 and 20-42270.94 from the Swiss National Science Foundation. In a time when funding is more and more often granted only to projects with immediate industrial applications, it is heartening to know that long-term research is still possible.