Chapter 5 Conclusion

In this conclusion, we will try to consider to what extent the system we have presented fulfills the initial goals of the project (section 5.1 ), as outlined in the introduction to this thesis, and specify the original contributions we had to bring to the state of the art in order to accomplish these tasks (section 5.2 ). We will then analyze our self-repairing FPGA in the light of a possible utilization outside the Embryonics project (section 5.3 ), and we will conclude by discussing possible future developments both for MuxTree in particular and for the Embryonics project in general (section 5.4 ).

5.1 Analysis of the Results

Our goal in this thesis was to design an FPGA capable of self-replication and self-repair. The particular requirements of such features were introduced in section 1.2. In this section, we want to compare our results with the original requirements.

As far as self-replication is concerned, our goal was met in most respects. Our self-replication mechanism is indeed capable of generating multiple copies of our artificial cells from the description of a single such cell. The mechanism allows for cells of any given size, and thus capable of executing any given task. The only compromise we had to accept was the use of an external source for the configuration of the cells. As we mentioned in the introduction, ideally it should be the cells themselves which generate and control the replication process. In our case, the replication process is indeed controlled by the dedicated hardware integrated in our FPGA, but the configuration bitstream is generated outside the circuit itself and not by the cells. The development of such an "ideal" system remains a future research goal for the Embryonics project.

As far as the self-repair mechanism is concerned, the results are not quite as close to optimum. Notably, the self-test mechanism falls somewhat short of the ideal outlined in the introduction. The constraints of biological inspiration, coupled with the need to minimize the hardware overhead, proved too strong to allow on-line self-test of more than a relatively small part of the circuit. However, our system is indeed able to transparently detect faults on a large part of the circuit 36 through off-line self-test at configuration.

On the other hand, the self-repair mechanism itself fits our requirements remarkably well: it allows for the repair of a considerable number of faults (the exact coverage depends, of course, on the number of spare elements allotted to the array) and is indeed capable of activating the self-repair at the cellular level through its global KILL signal. While the self-repair process is not guaranteed to occur transparently to the user, an effort was made to minimize the time it requires. In addition, our system actually surpasses our requirements by introducing the very useful feature of programmable redundancy, which allows the user to determine the amount of logic to be "sacrificed" for additional self-repair capabilities.

As a final consideration, we will mention that the hardware overhead required by the introduction of self-repair and self-replication is of approximately 50-70% 37 compared to the basic version of MuxTree. Considering the extremely fine grain of our FPGA, we are very satisfied by this figure, which includes all the additional logic necessary for self-replication, self-test, and self-repair, as well as the control logic required to handle these processes.

5.2 Original Contributions

When faced with a thesis such as this one, describing a research effort which is closely integrated within a larger project, it is sometimes difficult to precisely identify the original contributions of the author. In this section I will try to point out my personal contributions to the project within each of the main chapters.

Chapter 2 is meant to provide some background material for the Embryonics project in general. As such, I obviously cannot claim sole credit for its development: in particular, the epigenetic and phylogenetic axes are not really within the scope of my research. As far as the ontogenetic axis is concerned, its development was a collective effort on the part of a small group of people, including myself. I feel I have contributed in a substantial way to its development, and in particular to the definition of the 3-layer system (organism, cell, molecule) which is the core of our vision of ontogenetic hardware. Obviously, my contribution was mostly centered on the definition of the requirements and constraints of the molecular layer.

Chapter 3 contains what is probably my most original contribution, at least from a conceptual standpoint: the self-replication mechanism. When I first approached the problem, the state of the art for self-replicating machines was represented by Langton's loop, a structure obviously ill-suited to a hardware realization. In a first phase, I therefore had to improve the state of the art by designing a novel self-replicating loop which, while not directly designed for hardware implementation, represented an important step forward in the development of computationally-useful self-replicating structures 38. The need to design new self-replicating structures also led to the development of a novel software tool (see Appendix A) which provides a novel approach to the design of complex cellular automata. In a second phase, I had to develop an hardware mechanism capable of implementing self-replication in our FPGA. This process, which led to the integration of the cellular automaton in the MuxTree array, required considerable original thought since, to the best of my knowledge, such a mechanism is quite unique.

Chapter 4 deals with the hardware implementation of the self-test and self-repair mechanisms on the MuxTree FPGA. The actual implementation, in the form of a digital logic circuit programmed into a Xilinx FPGA (see Appendix B), was entirely my own work. As far as the architecture of the system is concerned, determining the original features of the design is less straightforward. The programmable function and the switch block of the MuxTree element predate my arrival in the laboratory, and while I was forced to introduce some minor modifications, I cannot claim authorship. On the other hand, the configuration mechanism is entirely my own work. For self-test and self-repair, I was forced to rely on standard techniques, mostly because the size of the elements did not allow complex mechanisms. However, while the test and repair strategies are not original (comparison, test patterns, spare columns, etc., are all "standard" techniques), it was, to the best of my knowledge, the first attempt to integrate on-line self-repair in a circuit as fine-grained as MuxTree. An important effort was thus required in order to select which approaches were viable given our constraints. I also had to integrate the mechanisms into the existing hardware with a major effort towards minimizing the additional silicon. This effort was remarkably successful in the case of the self-repair mechanism (which exploits much of the logic already in place). A notable original achievement was also the idea of exploiting the cellular automaton to configure the degree of fault tolerance (to the best of my knowledge, this feature is also unique, at least where FPGAs are concerned).

5.3 MuxTreeSR outside of Embryonics

When considering possible applications for our FPGA outside of the Embryonics project, we must remember that MuxTreeSR was conceived as part of a larger academic research project. As such, several factors which would be crucial in the development of a commercial circuit (such as, for example, hardware overhead or speed of operation) were, if not ignored, at least given a lower priority with respect to other constraints related to the overall inspiration of the Embryonics project.

The net result of this approach is that MuxTreeSR, as a whole, would probably not be a commercially viable product. However, this consideration does not preclude the possibility of adapting the particular mechanisms we developed in this project to commercial systems. In this section, we will analyze the strength and weaknesses from a commercial standpoint of three separate parts of our system: the MuxTree FPGA, the self-replication mechanism, and the self-repair approach.

5.3.1 MuxTree

The most recent developments in the design of FPGAs seem to indicate a transition from general-purpose programmable logic arrays towards circuits which are adapted to certain specific applications [66, 72]: digital signal processing (DSP), control tasks, mathematical coprocessing, etc. This is somewhat of an advantage when considering possible commercial applications for MuxTree, an FPGA which is not well suited for certain tasks. In particular, its extremely fine grain and its homogeneity (which prevents the use of wide long-distance busses) is a weakness for applications which handle large (32 or 64 bits) data. Also, MuxTree is at a disadvantage in implementing complex mathematical operators compared to many existing commercial FPGAs which integrate support for such operators in the structure itself of their elements.

On the other hand, the structure of MuxTree, designed to efficiently implement binary decision trees and diagrams, could be an interesting advantage for applications which can be easily described as logic functions (e.g., many state machines and control applications). A considerable number of software packages, both commercial and academic, are capable of deriving minimized binary decision diagrams from a given logic function, and such diagrams can then be used to trivially generate the configuration for a MuxTree array. Since many such control-applications are not usually speed-critical, MuxTree's shortcomings in this respect become less important.

These considerations, however interesting and, in a sense, useful, should not be given too much emphasis: MuxTree was not designed to be and is not likely to become a commercial product in the foreseeable future. Even if it has the potential to become an useful programmable logic device outside of the Embryonics project, it does not, by itself, provide enough unique advantages to be able to compete with the latest generation of FPGAs. Moreover, adapting it for a commercial release would require a major effort on the part of a team of developers, a task outside the competence of our laboratory. In particular, the development of the software tools which would be indispensable to achieve commercial success, and which are basically non-existing at this stage, is an effort beyond our possibilities (and, to a large extent, outside of our interests).

5.3.2 Self-Replication

If MuxTree is not likely to be of interest to FPGA manufacturers in the foreseeable future, we feel this might not be the case for our self-replication mechanism.

At first sight, self-replication is the feature of our system which is most closely related to the particular requirements of the Embryonics project, and consequently the least likely to be of use outside of our project. However, if we look at our mechanism without considering the biologically-inspired cellular level, we can see that self-replication is an extremely efficient approach to the implementation of arrays of identical elements of any given structure.

We have mentioned that FPGAs appear to become more and more application-specific, and it is therefore not difficult to imagine FPGAs designed specifically to implement arrays of identical processing elements, structures which are very well-suited for a wide number of applications: SIMD (Single-Instruction Multiple-Data) parallel processing, bit-slice architectures, etc. Considering the complexity of such applications, and consequently the difficulty of configuring FPGAs to implement them, the possibility of automatically obtaining two-dimensional arrays of processing elements from the configuration bitstream of a single such element could become a very powerful advantage.

5.3.3 Self-Repair

We have already mentioned the interest of self-repair in the development of complex FPGAs [7, 8, 25, 35, 40, 51, 85] in the previous chapter. Applying such a mechanism to a commercial system is, of course, a complex task.

From a manufacturer's point of view, our system is probably too powerful: on-line self-test and self-repair are not yet enough of a priority to warrant the hardware overhead required by such systems. On the other hand, there is no reason why our mechanism might not be simplified in order to more closely fit the requirements of the commercial world. In particular, we feel that a simplified version of our system might very well be adapted to achieve self-repair at fabrication (a more likely requirement for FPGA manufacturers) with a more than acceptable overhead.

In the design of such a system, several modifications would be needed. In the first place, the self-test mechanism would have to be completely redesigned, both to be adapted to the new architecture of the elements and to take advantage of the possibility of operating off-line. While the test of the configuration register would easily be adapted to most new architectures, the test of the functional part and of the connections would have to be modified depending on the layout of the element.

As for the self-repair mechanism, very little modification would be required, as it already supports static reconfiguration (rerouting of the connections before configuration in case of permanent faults). In order to adapt it to a new architecture for repair at fabrication, the only major alteration would be a simplification: the removal of the logic required for dynamic reconfiguration (rerouting of the connections and shift of the configuration whenever a fault is detected during operation).

Of course, the programmable redundancy of our system depends on the homogeneity of the array and on the self-replication mechanism, and would therefore be lost in a commercial system which is not likely to implement these two features. Nevertheless, the simplicity of the system, coupled with its versatility, could be of interest to FPGA manufacturers, even in a simplified form.

5.4 Embryonics: the Future

This thesis represents a step forward in the realization of the Embryonics project. However, it does not by any means represent a closure for the project as a whole, or even for the development of the ontogenetic axis. Research is continuing along all three axes of the POE model.

In the phylogenetic axis, where the design of Firefly [33] demonstrated the feasibility of hardware evolution, we are currently studying the application of evolutionary strategies to the design of hardware systems such as, for example, fuzzy controllers. As for future developments of evolutive hardware systems, we are investigating the feasibility of open-ended undirected evolutionary strategies, that is, systems which evolve not towards a precise, user-defined goal, but independently. Such an approach is undoubtedly a much closer approximation of natural evolution.

The epigenetic axis is advancing into the application phase, where we are trying to apply our algorithms to the solution of real-life problems and for the control of autonomous robots. An interesting possible evolution along this axis would be the creation of neural networks capable of continuous learning, that is of learning new behaviors (and consequently of adapting their structure) not only during a dedicated learning phase, but also while operating. Obviously, such systems would much more closely approach the behavior of biological neural networks than conventional ANNs.

On the ontogenetic axis, to which this thesis belongs, even if a considerable amount of work remains, we can begin to glimpse a possible closure. The next major step in the development of this axis is the design of the BioWatch 2001, an extremely complex machine which we hope to present on the occasion of the Expo.01, a major scientific and cultural event which will take place in the year 2001 in Switzerland. The function of the machine will be that of a self-replicating and self-repairing watch, implemented through macroscopic versions of our artificial cells and molecules (Fig. 5-1).

In addition to all the mechanisms described in this thesis, this machine, which will occupy an entire building, will require further improvements to the molecular level. Notably, in order to be efficiently used to create the kind of artificial cells required by the BioWatch 2001, MuxTree will require a mechanism allowing the configuration register to be used as a memory, accessible to the rest of the circuit. In fact, the direct consequence of our cellular approach is that the genome memory (the memory containing the program to be executed in each processor) is necessarily large, as it must contain the instructions to be executed in all processors in the array. In the current version of MuxTree, which provides a single flip-flop per element as memory storage, such a memory would require an excessive number of elements. By using the 20-bit configuration register for memory storage, the size of our artificial cells can be considerably reduced.

Once this improvement is in place, the development cycle for MuxTree will approach its end. We might consider adding a few extra features, for example, in order to achieve true self-replication (as mentioned above in section 5.1), but such additions are not likely to improve the circuit's performance in any significant way. At this stage, we might well be interested in designing a VLSI chip containing an array of MuxTree elements.

The closure of development of MuxTree will not, however, necessarily mean the end of research in the ontogenetic axis. In fact, with a set of mechanisms in place capable of realizing an ontogenetic machine, we could try to consider a possible merging of the three axes of the POE model (Fig. 5-2). For example, following von Neumann's sequence of self-replicating machines, we could imagine replacing the functional part of the MuxTree element with a neuron-like structure, thus joining the epigenetic and ontogenetic axes.

For the moment, this kind of convergence is fairly remote, and a subject of speculation only. On the other hand, the work presented in this thesis is an interesting first step in the development of such advanced systems. By introducing features such as self-replication and self-repair, we hope to have shown that it is possible to draw inspiration from biology in the design of digital circuits, and indeed that bio-inspiration can lead to the development of novel and powerful architectures.

36.We cannot provide an accurate estimate of the fault coverage provided by our system, as MuxTree is a circuit in constant evolution still far from its final implementation.

37.Again, an accurate estimate is difficult, both because MuxTree is constantly evolving and because our only physical realization (described in Appendix B) relies on programmable logic (Xilinx FPGAs) to implement our elements. A more accurate estimate would be possible if MuxTree were to be implemented as a VLSI chip.

38.The gratifying number of references to this work in the literature seems to indicate that the automaton, designed as an intermediate step, has nevertheless a certain intrinsic interest.