Introduction

Host an island with a population of circuits struggling for survival in a hostile online world. During your PCs idle time individuals from this population will evolve through artificial evolution in a process of survival of the meekest into circuits with Concurrent Error Detection (CED) and will compete with those hosted on other PCs by migrating to and from them. These circuits will not be constrained by conventional design rules since evolution finds efficient solutions without worrying about how complex they are to understand - just as it did with our own bodies and brains. You can join into this cluster in one minute by installing the client found here. Check up on how your population is doing compared to others here and name your best creations if they enter the "better than human" hall of fame.

Self-Diagnosing Hardware is capable of detecting deviations from its normal behaviour due to faults. Self-Diagnosis is important especially in mission critical systems such as medical equipment, transport controllers and those in hazardous environments such as space missions and nuclear power stations. Built-In Self-Test (BIST) is widely used yet commonly requires more than 100% area overhead or off-line testing. However in mission critical systems off-line testing is unsuitable because we must diagnose failure immediately. The standard on-line solution is a voting system with two copies of the module being diagnosed which is capable of detecting faults immediately by comparing the outputs of the copies. However, this solution requires 100% redundancy for the extra module plus more logic for the voter. In the last 40 years of CED research, spawned by the NASA aerospace program, conventional design has not come up with a significant improvement to the voting system as such an on-line CED solution. You can help us to arrive at the next generation of self-diagnosing circuits.

As an increasing number of mission critical tasks are automated, self-checking circuits are of paramount importance. For example in medical applications (heart monitors, pacemakers), transport (aeroplane hardware, traffic lights, car ABS braking), space (satellites, probes) and industrial facilites (nuclear power plants) and more to come in the future as cars start driving themselves, surgical operations are performed remotely, etc.. In all these areas human lives or great economic loss are at risk. By joining this project you would be making a valuable contribution to exciting research and helping to push the bounds of human knowledge. Not only this, but the circuits produced by this project are truly better than those of conventional design so would lead to safer controllers in current and emerging mission critical applications saving lives and money.

Evolutionary methods such as Genetic Algorithms (GA) or Evolutionary Strategies (ES) attempt to apply Darwinian evolution to other domains. A GA roughly works like this:

  1. Encode the problem at hand as a binary genotype.
  2. Created a population with random genotypes.
  3. Evaluate all individuals in the population.
  4. Select the fittest for reproduction.
  5. Create a new population by applying cross over to those selected.
  6. Apply background mutation to all individuals in population.
  7. Go back to 3 and repeat till we find an optimal solution.

This simple algorithm has been applied to a wide range of problems from parameter fitting in economic models to the design of aircraft wings. One of the most striking examples of the power of blind variation and selection is Adrian Thompson's tone discriminator. By exploiting the subtle physics of a reconfigurable chip (a Field Programmable Gate Array) an evolved design distinguished between two spoken words using only 100 gates: something unthinkable using conventional design. Read more about this from a New Scientist Cover Story. There are other examples where evolutionary methods applied to hardware have produced circuits comparable to those designed by experts and also unconventional circuits in which resources are used extremely efficiently.

Evolving Self-Diagnosing Hardware was first attempted by the author for some toy circuits: a two bit multiplier and a one bit adder. After hundreds of thousands of generations, circuits evolved performing full diagnosis using about half the overhead the conventional solution would have required. For example when using two-input logic-gate technology, a two-bit multiplier can be implemented using 7 gates. Adding an extra copy, and 7 more gates for comparing 4 outputs, we have an overhead of 14 gates for the conventional voting system CED solution. After four million generations (a months processing time on a single PC) the GA found a circuit (diagram) with the same behaviour using only 9 extra gates. It is hard to work out exactly what operating principles underlie its operation but it looks like it tends to use more XOR gates which always propagate a bit flip in one of their inputs, and also exploits design diversity to compare multiple sections of the circuit simultaneously. Many evolved circuits are described and their diagrams can be found in the published papers.

This proves that evolution is capable of reaching areas of design space beyond the scope of conventional design, and also that these areas contain so far unseen efficient solutions, waiting to be plucked. How many such circuits could evolution find better than today's? We believe they are everywhere, and we intend to start searching for them by using a cluster of islands based on contributor's PCs. Why self-diagnosing hardware? It is very hard to design a circuit producing reliable behaviour when faults are thrown at it, which is why human designers have chosen to simply have an extra copy of the whole circuit as a solution. However this is expensive in terms of power and silicon area, the former crucial in space missions and the latter in mass production. The circuits to be given to the cluster to evolve will be of industrial size, such as a Viterbi decoder, which is used inside every mobile phone.

As an increasing number of mission critical tasks are automated, self-checking circuits are of paramount importance. For example in medical applications (heart monitors, pacemakers), transport (aeroplane hardware, traffic lights, car ABS braking), space (satellites, probes) and industrial facilites (nuclear power plants) and more to come in the future as cars start driving themselves, surgical operations are performed remotely, etc.. In all these areas human lives or great economic loss are at risk. By joining this project you would be making a valuable contribution to exciting research and helping to push the bounds of human knowledge. Not only this, but the circuits produced by this project are truly better than those of conventional design so would lead to safer controllers in current and emerging mission critical applications saving lives and money.