Michael Garvie

Current research

I'm currently researching the use of island based coevolutionary distributed Genetic Algorithms to arrive at efficient designs of circuits with Concurrent Error Detection and Fault Tolerance. To this purpose I run the Distributed Hardware Evolution Project which allows anyone to host an island of evolving circuits using their spare CPU.

I have also been researching the use of transistor level hardware evolution to arrive at autonomous embodied robotic controllers.

Popular Articles

Circuit design evolving in distributed digital world - New Scientist.com, 31 July 03

Full Article

Are you fit enough to recognise failure? - AISBQ, Issue 113

Article found on Page 4 of newsletter.

Academic Publications

Automatic Synthesis of Totally Self-Checking Circuits

Abstract: Totally self-checking (TSC) circuits are synthesised with a grid of computers running a distributed population based stochastic optimisation algorithm. The presented method is the first to automatically synthesise TSC circuits from arbitrary logic as all previous methods fail to guarantee the checker is self-testing (ST) for circuits with limited output codespaces. The circuits synthesised by the presented method have significantly lower overhead than the previously reported best for every one of a set of 11 frequently used benchmarks. Average overhead across the entire set is 23% of duplication and comparison overhead, compared with an average of 69% for the previous best reported values across the set. The methodology presented represents a breakthrough in concurrent error detection (CED). The highly efficient, novel designs produced are tailored to each circuit's function, rather than being constrained by a particular modular CED design methodology. Results are synthesised using two-input gates and are TSC with respect to all gate input and output stuck-at faults. The method can be used to add CED with or without modifications to the original logic, and can be generalised to any implementation technology and fault model. An example circuit is analysed and rigorously proven to be TSC.


Reliable Electronics through Artificial Evolution, doctoral thesis.

Summary: This thesis will demonstrate the use of evolutionary algorithms applied to electronic circuit de- signs (ie. Evolutionary Electronics) to improve the reliability of hardware in several ways. It will introduce Jiggling, an architecture for the self-repair of space-deployed reconfigurable hardware. Jiggling uses spare resources efficiently at a fine-grained level and if extended to sequential circuits would not depend on any unprotected repair mechanism. Reliability analysis of systems protected by Jiggling show they can survive with above 0.99 probability for 48 times longer than with the standard TMR/Simplex method. An architecture to distribute any evolutionary process across workstations and public contributors through the Internet is introduced and is shown to en- able circuits of industrial interest to be evolved. A method to synthesise digital combinational and sequential circuits with totally self-checking (TSC) concurrent error detection (CED) is shown to generate designs using less than 30% of duplication overhead, a figure previously unheard of in the literature. These designs do not adopt the traditional functional logic-checker structural con- straint and exhibit multiple self-checking strategies well suited to each circuit's particularities. The absolutely fault secure class of circuits is introduced as the most stringent one detecting multiple faults with no assumptions on their arrival time and it is shown that evolution can synthesise such circuits. The first method for the automatic synthesis of generic analog circuits with CED is also introduced and it is shown how Evolutionary Electronics is probably the best suited tool for the task. Finally the first example of transfer of a design evolved on real hardware to a different hardware medium is demonstrated. This is paramount because industry cannot be expected to produce evolved circuits in the same medium they were evolved in.

Download PDF.

Scrubbing away transients and Jiggling around the permanent: Long survival of FPGA systems through evolutionary self-repair, Proc. of 10th IEEE International On-Line Testing Symposium, © IEEE.

Abstract: The Jiggling architecture extending TMR+Scrubbing is shown to mitigate FPGA transient and permanent faults using low overhead. Mission operation is never interrupted. The repair circuitry is sufficiently small that a pair could mutual ly repair each other. A minimal evolutionary algorithm is used during permanent fault self-repair. Reliability analysis of the studied case shows the system has a 0.99 probability of surviving 17 times the mean time to local permanent fault arrival. Such a system would be 0.99 probable to survive 100 years with one fault every 6 years.

Download PDF. View BibTex reference.

Errata: The value of H used for repair simulations was 32, not 8. In equation 2, k=i-1.

Evolution of Combinational and Sequential On-Line Self-Diagnosing Hardware, Proc. of 2003 NASA/DoD Conference on Evolvable Hardware, © IEEE.

Abstract: The evolution of circuits with on-line built-in self-test is attempted in simulation for a full adder, a two bit multiplier and an edge triggered D-Latch. Results show that evolved designs perform full diagnosis using less or equal number of components than hand-designed equivalents.

Download PDF. View BibTeX reference.

Evolution of Self-Diagnosing Hardware, Proc. of 5th Int. Conf. on Evolvable Systems, © Springer Verlag 2003.

Abstract: The evolution of digital circuits performing built-in self-test behaviour is attempted in sumulation for a one bit adder and a two bit multiplier. Promising results show evolved designs can perform a better diagnosis using less resou rces thatn hand-designed equivalents. Future extensions of the approach could allow the self-diagnosis of analog circuits under failure and abnormal operating conditions.

Download PDF. View BibTeX reference.

Errata: In Fig. 1, the inputs to gate 8 should be B and Cin, and the caption should read "(b) full on-line solution with 4 extra gates.".

Undergraduate Dissertation - 2001

Cambridge University undergraduate dissertation titled "Gripping Evolvable Hardware" in PDF. Genetic Algorithms were used to search for circuit designs on an Altera FLEX FPGA chip and on a digital simulator. A new fitness function based on statistical correlation of data series was found to be superior to the standard "number of hits" fitness function. Various combinational and sequential circuits were evolved inc luding an oscillator whose frequency increased linearly with temperature. This dissertation also provides some documentation to the core functionality of Javga, Distrit and Islandev below.

Public Software Projects

All projects are Open Source Software, released under the GPL.

Distributed Hardware Evolution Project v1.72

Distributed Hardware Evolution Project v1.72 is a combination of the current versions of JaGa, DistrIT, IslandEv and the debugging/logging package De bugLib which can be found in each of these projects. To add requests to the DHEP To Do List either post them on the Forum or send them by email.

JaGa: Pluggable Genetic Algorithm system in Java

This GA framework is designed to be general purpose and can be used to evolve anything by plugging in custom modules. Currently there are implementations of a fairly complete set of Genetic Operators and Selection mechanisms. Also there are plug-in m odules to evolve hardware for various purposes and on various platforms. Visit the JaGa Sourceforge project home page.

DistrIT: Generic Distributed Processing Platform in Java

Set of classes which make distributing any CPU intensive process over many PC's and processors over a network trivial. Visit the DistrIT Sourceforge project home page.

IslandEv: Island based Co-Evolution Distributed GA

This package aims at using Distrit to allow any GA engine to be parallelized over many PCs using a 2D island coevolutionary model with variable migration rates. Classes in the Javga package (for eg: es.pj.circuits.control.EvoKingKong.java) use this pa ckage to start up a Distrit server distributing Javga over a network. Visit the IslandEv Source project home page.

PortIO: driver and classes for performing Port (serial, parallel, or arbitrary address...) I/O under Java in Windows 9x/NT/2000.

We must travel back in time to see this.

Javascript Units Converter

The most complete and easy to use I've seen so far (mind you this was written in 1997!). Click here to use it for free.