In this introductory chapter, we will present a short description of the motivations behind the development of our circuit, that is, the reasons which led us to draw inspiration from biology in our design (section 1.1). We will then introduce the basic features we wish to introduce in our new circuit (section 1.2), and conclude the chapter with a brief outline of the overall structure of the thesis (section 1.3), including an overview of our original contributions.
Recent technological advances, in the form of programmable logic circuits [14 ,103], have engendered a re-evaluation of biological inspiration in the design of computer hardware. This thesis, and the larger project which encompasses it, represent an attempt at exploiting such an inspiration in the design of digital circuits. This section contains a brief overview of the foundations of the work presented in this thesis.
Through his theory of automata, von Neumann conceived of a set of machines capable of many of the same feats as biological systems: evolution, learning, self-replication, self-repair, etc. At the core of his approach was the development of self-replicating machines, that is, machines capable of producing identical copies of themselves. In developing his theory, Von Neumann identified a set of criteria which had to be met in order to obtain useful biological-like behavior in computing machines. These criteria rested on two fundamental assumptions:
Von Neumann's research was, as we mentioned, never completed: the only machine he developed to any great extent was a theoretical model known as the universal constructor. Nevertheless, his theory of automata provides even today a firm foundation for the development of bio-inspired systems.
In the eighties, bio-inspiration gained new momentum under the label of artificial life, a research field pioneered by Christopher Langton which is attracting more and more interest in the scientific community. Under the impulse of new technology, bio-inspired hardware is also finally reaching the stage of physical realization.
The key technology which today allows the development of such approaches is the advent of programmable logic devices, usually referred to as field-programmable gate arrays(FPGAs) [14, 103]. These devices consist of two-dimensional arrays of identical elements. Each of these elements is designed to be able to implement a variety of different functions, depending on the value of its configuration, a string of bits defined by the user at run-time. The size of an FPGA element (known as its grain) can vary considerably from one device to the next, ranging from complex look-up table based architectures ( coarsegrain) to much smaller hard-wired elements ( fine grain). The elements are connected to each other through a connection network which is itself programmable.
A hardware designer can use an FPGA to implement just about any kind of digital logic circuit by defining the functionality of each element as well as the connections between these elements at run-time. Therefore, they are the ideal platform for the development of bio-inspired hardware, which requires that the layout of the circuit be modified through mechanisms such as self-replication, evolution, or healing (self-repair).
The goal of the work presented in this thesis is to develop an FPGA architecture which exploits biologically-inspired mechanisms to introduce two novel features: self-replication and self-repair. The resulting circuit, a very fine-grained FPGA known as MuxTreeSR (for tree of multiplexers with self-repair), was designed with a specific application in mind: its use as a platform for the implementation of the more complex bio-inspired structures we developed in the framework of a larger project, known as Embryonics.
As the possible intersections between these two worlds are manifold, so the Embryonics project advances along more than one research axis, investigating domains as diverse as artificial neural networks [36, 74] and evolutionary algorithms [64, 99].
The research axis to which this thesis belongs is concerned with the use of biologically-inspired mechanisms in the synthesis of digital circuits, and draws inspiration from two distinct sources. The first is the biological mechanism of multi-cellular organization: the complex behavior of natural organisms derives from the parallel operation of a multitude of simple elements, the cells, each containing the complete description of the organism (the genome). The second is von Neumann's concept of self-replication of an universal computer, a mechanism which allows for the automatic creation of multiple identical copies of a machine from a single initial copy.
These two approaches are fundamentally different. Both rely on a mechanism of self-replication to obtain arrays of elements which can be seen as processors, all executing an identical program. However, in von Neumann's case the processors are universal Turing machines, and are identical in structure as well as in functionality: the process of cellular differentiation is entirely absent, and the whole system can be seen as a self-replicating unicellularorganism. In nature, cells are different in structure and functionality (the appearance and behavior of a liver cell, for example, are considerably different from that of an epidermal cell), but any cell is potentially capable of replacing any other cell because it contains the description of the entire organism, i.e., the genome. Cellular differentiation is therefore at the very core of biological systems, which derive their complexity from the coordinated operation of small, differentiated cells.
In Embryonics, we developed a solution which tries to integrate the two approaches: our system consists of an array of artificial cells implemented by small processors which have an identical structure (the same hardware layout) but different functionality (different software). The biological inspiration is introduced by storing in each processor the code required by the entire array: each artificial cell will then select, depending on its position within the array, which portion of code to execute. The functionality of each processor will therefore be different, as in biology, because it executes a different part of its artificial genome. This considerable redundancy goes against conventional design rules (which emphasize the minimization of the size of the elements), but proves useful in the implementation, for example, of self-repair: since each cell contains the same code as any other cell in the system, then it can also replace any cell simply by executing a different portion of the artificial genome.
The approach used in the Embryonics project is thus based on the parallel operation of an array of artificial cells, each consisting of a small processor and containing the information required by the entire system. The novel FPGA presented in this thesis was designed so as to implement the self-replication of our cells directly in hardware, thus allowing the user to automatically realize the cellular array staring from the description of a single artificial cell. The programmable logic of our circuit can thus be seen as a molecular layer, providing the supporting material for the construction of our artificial cells.
Obviously, our array of processors will require a considerable amount of programmable logic, which implies that the probability of faults occurring somewhere in the circuit will be non-negligible. Hence the need to implement a mechanism which allows the circuit to operate in the presence of faults. Biological systems are faced with the same requirement, and solve it by replacing dead cells with new ones ( cicatrization). Since the creation of new silicon is not feasible given current technology, the electronic equivalent of cicatrization (i.e., self-repair) will have to rely on the presence of spare logic which can replace the faulty part of the circuit. Our FPGA will provide support for self-repair directly in hardware, thus simplifying the task of developing self-healing systems.
The first feature is directly related to von Neumann's approach and is at the core of biological inspiration in Embryonics, since it allows the creation of arrays of artificial cells starting from the description of a single such cell. In order to achieve a physical realization of von Neumann's machine, that is, the self-replication of an universal computer, our system will require the following capabilities:
Our task in designing a self-replicating FPGA should therefore be fairly obvious: since our artificial cells are universal machines capable of executing any given task given a sufficiently large memory (and are thus universal computers), in order to fulfill the requirements laid out by von Neumann our FPGA will require a mechanism capable of constructing multiple copies from the description of a single cell.
Self-repair depends on a somewhat different set of assumptions, related more to engineering than to biology. In biology, as well as in von Neumann's approach, self-repair is achieved through the replacement of faulty cells. As we will see in the next chapter, such a mechanism is indeed present in our machines: faulty cells are replaced by identical spare cells whenever necessary.
Introducing self-repair in our FPGA is the equivalent of cicatrization at the molecularlevel, a phenomenon which has no direct parallel in either biology or in von Neumann's work. Nevertheless, from an engineer's standpoint, it is a mechanism which is extremely interesting for a number of reasons:
From these observations, we can begin to outline the basic feature of our ideal self-repair mechanism. First of all, of course, it will require a self-test mechanism capable to detect as many faults as possible (ideally, it should be able to detect allpossible faults in the system, but such a goal is not likely to be achievable) transparently to the user. Moreover, such a system should be able to accurately determine the exact location of the fault (that is, which of the elements in the array is faulty) so that self-repair can restore the functionality of the circuit. As far the self-repair mechanism itself is concerned, it should be able to repair as many faults as possible (once again, it is not reasonable to assume that all faults will be repairable) and, should such a repair not be possible at the molecular level, activate the self-repair process at the cellular level.
Obviously, these features will introduce both additional hardware and additional delays in our circuit. Since our FPGA is extremely fine-grained, it will be very important to minimize the hardware overhead. On the other hand, the speed of operation is not an important factor in our research (biological systems, after all, operate relatively slowly). Our main effort in this project was therefore to minimize space (area) rather than time (delay), while of course respecting the considerable number of additional constraints imposed by the biological inspiration of our system.
Many of the choices in the design of our system stem from its being part of a larger project. Therefore, in chapter 2 we will provide an overview of the Embryonics project as a whole, as well as introduce some examples of biological inspiration in computer science, greatly expanding the brief outline provided above in section 1.1. The Embryonics project is, of course, a collective effort. As such, we cannot claim that the contents of this chapter are original work, even if we hope to have contributed to some extent in the project's development. However, we feel that such an introduction is necessary to fully understand the motivations of our design.
Chapter 3 is dedicated to self-replication. The development of a mechanism implementing this feature required a considerable amount of original research. In order to introduce the problem, the chapter will begin with an analysis of the existing approaches to self-replication in computer science, including a description of von Neumann's seminal work on the subject. After the historical background, we will introduce the original research which led to the final design of a self-replication mechanism for our FPGA.
Chapter 4 will contain a description of our self-repair mechanism. It will start with a description of the FPGA in its basic form, that is, without self-replication and self-repair. Next, we will introduce the problem of self-test and its implementation, before a description of the self-repair mechanism. The latter will also include a description of the modifications to the self-replication mechanism required by self-repair. Neither the self-test nor the self-repair mechanism can be considered original work by themselves, relying as they do on relatively well-known approaches. The originality of the material described in this chapter lies more in the implementation: applying these features to a fine-grained FPGA required a major effort to minimize the hardware overhead, which in turn required a careful analysis and simplification of the existing approaches. The chapter will then close with a simple but complete example of the operation of our system.
In the conclusion (chapter 5), we will analyze our system with respect to the initial requirements outlined above in section 1.2 , and investigate possible applications for our system outside of the Embryonics project. The main body of the project will then end with a few considerations on possible future developments for the Embryonics project in general and for our FPGA in particular.
The body of the thesis will be followed by two annexes: the first (Annex A) will describe a software package we developed in order to help us in the design of our self-replication mechanism; the second (Annex B) will describe in detail a prototype of our FPGA which we designed in order to demonstrate the feasibility of our system.