Electronic engineers have long known the power of simulated annealing: a stochastic optimisation procedure embedded in many CAD tools, used in such tasks as placement and routing . In simulated annealing, a current imperfect candidate solution to the optimisation problem is randomly perturbed; if the random change is deemed to be not too deleterious (hopefully beneficial, occasionally) for the current stage of optimisation, then it is kept and our current candidate solution becomes the perturbed one. Otherwise, other random perturbations are tried until a not-too-deleterious one is found. This process of random variation with non-random selection is then iterated; all being well, a satisfactory solution is eventually obtained even if the initial starting-point was completely random.
The process described above satisfies an abstract definition of Darwinian evolution (selection acting on heritable variation), so the FPGA community is already extensively using an `evolutionary algorithm.' Various different families of evolutionary algorithm have been developed over the last three decades; notably Genetic Algorithms , Genetic Programming , Evolutionary Programming , and Evolution Strategies . Some of these have a more obvious analogy with natural evolution, adding the strategy of maintaining a population of candidate solutions, with the possibility that two or more individuals in the population can be combined to produce an `offspring' (analogous to sexual recombination). Which evolutionary algorithm is best for a particular problem depends on the nature of the problem's search-space, and the subtleties of the evolutionary algorithm's detailed operation.
So an evolutionary algorithm can take an FPGA configuration corresponding to a circuit design, and gradually improve it (through a sequence of small adaptations) according to some `fitness' criterion. In the placement example, the fitness criterion might be a measure of circuit area, used to decide whether a perturbation in the design's placement should be selected. An interesting possibility now suggests itself. Rather than perturbing the placement of a predetermined fixed design, why not start from a completely random FPGA configuration, make the fitness criterion a measure of how close the chip's behaviour comes to meeting the specification for the desired circuit behaviour, and allow the evolutionary algorithm full freedom to manipulate the configuration? Then, the evolutionary algorithm would be performing all of circuit design and implementation automatically. Ideally, this would give the human designer more time to spend in the pub. In practice, it shifts the human's design task to the more abstract level of designing a fitness function which successfully guides the chosen evolutionary process to the desired goal, and this is no small feat. Usually there is also much work to be done in tailoring the evolutionary algorithm to the problem.
Not surprisingly, artificial evolution's promise as the ultimate in `design automation' is difficult to realise. Under names such as `evolvable hardware' and `evolutionary electronics,' significant research effort is now being directed into this area [5,2,7]. Some extremes of hype predict evolution `at electronic speeds' of staggeringly large and complex circuitry, exceeding what can be achieved by conventional methods. My own view is that the uses of evolutionary design lie primarily in exploring beyond the scope of conventional methods, not competing with them. For example, I do not anticipate the top-down design of digital circuits going out of fashion soon. Indeed, the size of circuits achieved through evolutionary methods has been rather modest so far.
We have already seen that the evolutionary design of an FPGA configuration can be very different from a normal design flow. By directly manipulating the configuration, there is no distinction between design and implementation; evolution is always working with an implemented system. In fact, devices such as the Xilinx XC6200 family  make it possible to perform the fitness evaluations -- the measurement of how closely a candidate configuration meets the specification -- in real silicon, without the need for simulation of FPGA behaviour. For a fitness measurement, the candidate configuration is downloaded onto a real FPGA; this physically instantiated circuit design then behaves in real-time according to semiconductor physics, and can be evaluated by applying test stimuli while monitoring the behaviour. This approach has a number of possible benefits:
Clearly, the evolutionary algorithm has found an extremely efficient solution in a region of `design-space' beyond the scope of conventional techniques. The task was a simple one, but not remote from applications. Figure 3 shows how the 1kHz/10kHz input was replaced with audio signals for the spoken words `Go' and `Stop', and evolution was continued to adapt the 1kHz/10kHz circuits to this new discrimination task. A circuit performing reasonably well when the words were spoken into a microphone was found, still just using the corner of cells and no external components or clock. This `incremental' approach to artificial evolution, where a related previous result is adapted and built-upon to perform a new task, is one of the best answers to the challenge of evolution being a fairly lengthy process.
The problem with this approach is that the circuits can be too precisely tailored to the exact conditions in which they were evolved. The evolved configuration might not work on another FPGA device of the same type, or at a different temperature. Work is underway to tackle this difficulty by evaluating each candidate solution in extreme environmental conditions: on FPGAs made at different foundries, at different temperatures, power-supply voltages, etc. . Initial results are encouraging: by making robustness part of the problem to be solved in this way, evolution should be free to find strategies for robustness that are tailored to the task and the properties of the implementation medium. Thus, it may be possible to obtain a robust solution which is still more efficient than in synchronous digital design, which forbids all analogue continuous-time dynamics in order to guarantee robustness. It may prove desirable to provide a stable clock as an extra input to the evolving circuits, but nothing need be said about how it should be used. The clock would then be a resource, rather than a dynamical constraint, and evolution would be free to ignore it or use it to stabilise the dynamics in any way: a true `time-giver.'
The above will seem bizarre to most trained designers. Artificial evolution can be let free to explore everything a reconfigurable device can do, to find the forms and processes that are `natural' to the physics of this medium. It seems clear that these exciting circuits will have some applications, but the practical difficulties of guaranteeing adequate robustness, and of scaling-up to complex tasks, are not to be denied. The circuits evolved so far are certainly tantalising enough to be worth pursuit. Perhaps just as importantly, this evolutionary approach may provide a useful stimulus to re-think what sort of thing an electronic circuit can be.
http://www.informatics.sussex.ac.uk/users/adrianth/index.html gives full details of this research and links to others, and  gives the full story in one volume.
I gratefully acknowledge the support of the following organisations:
EPSRC, Xilinx, Hewlett Packard, British Telecom, Motorola, Zetex.