Gianluca TEMPESTI
 PhD Thesis
 
Download a copy of my thesis:

"A Self-Repairing Multiplexer-Based FPGA Inspired by Biological Processes"
[Acrobat PDF file, 10512675 bytes, 166 pages (17 in color) in format A4]

and/or read the abstract in English ou le résumé en Français.


Abstract 
Special-purpose parallel systems, and in particular cellular SIMD (Single-Instruction Multiple-Data-Stream) and SPMD (Single-Program Multiple-Data-Stream) array processors are very interesting approaches for handling many computationally-intensive applications. These systems consist of an array of identical processing elements executing the same operations (at the instruction or at the program level, respectively) on different sets of data.

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:
  • They are designed to be used in single-chip systems: while it is possible to link multiple FPGAs, the connections between the chips become a major bottleneck for the configuration, making it impossible to treat a multi-chip system as a homogeneous surface of logic elements.
  • Neither their structure nor their configuration software allow to easily partition the chip(s) into an array of identical processing elements.
  • They are not currently capable of self-repair, a required feature for very large systems (such as a sizable array of processing elements), where the probability of faults increases to the point that they become impossible to ignore. One of the main sources of inspiration of the Embryonics project is the remarkable robustness of biological organisms.
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.

Résumé 
Les systèmes parallèles spécialisés, et en particulier les réseaux de processeurs cellulaires SIMD (Single Instruction Multiple Data) et SPMD (Single Program Multiple Data) sont des approches très intéressantes pour beaucoup d'applications gourmandes en calcul. Ces systèmes sont composés d'une matrice de processeurs exécutant les même opérations (au niveau des instructions ou du programme, respectivement) sur des données différentes.

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:
  • ils sont conçus pour être utilisés dans des systèmes qui contiennent une seule puce programmable; bien qu'il soit possible de relier plusieurs FPGAs entre eux, ces connexions deviennent vite des goulots d'étranglement, rendant impossible de les traiter comme une surface homogène d'unités logiques;
  • ni leur structure, ni leur logiciel de configuration ne permettent de partitionner facilement la(les) puce(s) en réseaux d'unités de traitement identiques;
  • ils ne sont pas encore capables d'autoréparation, une propriété nécessaire pour de très grands systèmes (tels que des réseaux de processeurs), où la probabilité de fautes augmente au point qu'il devient impossible de les ignorer; une des principales sources d'inspiration du projet Embryonique est précisément la remarquable robustesse des organismes biologiques.
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.