A Development Model for Robust Fault-Tolerant Design

by Andy Tyrrell and Hong Sun

Multi-cellular organisms, products of long-term biological evolution, demonstrate strong principles for the design of complex systems. Their nascent processes, including growth, cloning (self-replication) and heeling (self-repair and fault-tolerance), are attracting increasing interest from electronic engineers. All of these characteristics are encoded in the information stored in the genome of the fertilized cell (zygote). The process of growth from a single zygote to a mature organism is called development.

Development is controlled by genes, which determine the synthesis of proteins. The activity of genes sets up the complex interactions between different proteins, between proteins and genes within cells, and hence the interactions between cells. The development of an embryo is determined by these interactions. Figure 1 shows a representation of the pattern formation of cells controlled by the concentrations of a morphogen. Based on the level of morphogen in each cell, the cells develop into different patterns according to threshold values.

Figure 1: French flag model of pattern formation.

Inspired by natural evolution, Evolvable Hardware (EHW) was developed in the last decade as a new approach to the design of electronic systems. It has demonstrated the ability to perform a wide range of tasks from pattern recognition to adaptive control. A variant of this approach mimics the developmental process from embryo to multi-cellular organism, constructing robust and fault-tolerant circuits.

Motivated by the importance of the interactions in and between cells in biology, this work seeks an approach to increase these interactions, investigating whether this benefits evolution and development. Honeycomb structures, often produced by natural evolution and claimed by architects and economists to be the most efficient structure for covering an area, are used. The concept of a morphogen is employed when judging the state of a cell. The proposed model mimics various cell developmental processes. Although some processes (eg cell movement) are restricted by the fixed hardware architecture, those such as changes in cell state, cell-to-cell signalling, and cell death are modelled.

The cells used in this cellular model are homogenous; they all interpret the same genome and exhibit the same structure. Each cell has direct access to its six neighbouring cells. No direct access to non-adjacent cells is allowed in the current model. Figure 2 shows the connections between cells. The control unit (CU) in Figure 2 generates the state and chemical of the cell. The state decides what type the cell will be, while the chemical constructs the development environment. The Execution Unit (EU) would perform any functional activities required by the cell (for example logical functions required as part of any arithmetic operations).

Figure 2: Connections between cells.

This cellular model can be used for the task of pattern formation (the shape of different flags or other shapes) or functional circuits (multiplier or even parity, etc). The difference between pattern formation and functional circuits is that during pattern formation, the fitness of the system is based on whether the states of the cells are in accord with the expected states, the EU not being required. When developing functional circuits, the state generated by the CU is used to control the EU function and the fitness of the system is based on the output of the EU. Here we illustrate an experiment looking at the pattern formation of the French Flag, so only the CU is used.

The model is defined using the VHDL language, with Xilinx Virtex XCV1000 as its target FPGA. The evolutionary process is designed to be implemented in hardware, and can therefore be considered Intrinsic Evolvable Hardware (IEHW).

Using a process of evolution and developmental growth a French flag pattern can be formed using this hardware. (It should be noted that functional circuits have also been produced using this same technique.) An interesting emergent property of all of these systems is their capacity to recover from different faults.

For example, we can change all red cells into blue, white cells are changed into grey (dead state) and blue cells are switched to red. Hence all the states of cells are wrong and the chemicals are all set to 0. In five steps the system recovered from this fault, and maintained the correct shape thereafter.

In another example, all cells apart from the top left cell are set to dead and their chemicals are set to 0. A correct shape appears in four steps, although this turns into a shape with a fault in another two steps, and finally regains the correct shape in another two steps.

The honeycomb model presented here is part of a larger research project, but this simple example shows its capacity for pattern formation: its ability to develop into a specific shape, maintain that shape and recover to the shape after many kinds of transient faults are injected.

Basic cell processes in embryonic development are imitated. A morphogen is used to mimic the pattern formation process of the embryo. Chemicals are used to build up the environment for development. The interactions between cells are based on the transmission of chemical and state information.

Link:
http://www.elec.york.ac.uk/intsys/

Please contact:
Andy M. Tyrrell, University of York, York, UK
E-mail: amtohm.york.ac.uk