Exploring Beyond the Scope of Human Design: Automatic generation of FPGA configurations through artificial evolution.
(Extended Abstract)

Adrian Thompson
Centre for Computational Neuroscience and Robotics,
School of Cognitive and Computing Sciences,
University of Sussex, Brighton BN1 9QH, UK.
adrianth@sussex.ac.uk

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 [12]. 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 [3], Genetic Programming [4], Evolutionary Programming [1], and Evolution Strategies [6]. 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 [13] 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:

• By always working with an implemented system, implementation details are taken into consideration at all times during the automatic design process. This may be able to produce more efficient implementations than top-down design, where implementation details are mostly left until the later stages.
• Requirements at the implementation level (such as area, power, and even fault-tolerance [10]) can be integrated with the behavioural specifications when formulating the fitness criterion. Again, this means that these factors can influence the direction of all stages in the design process, potentially more effectively than in top-down methodologies.
• If we are careful not to enforce our prejudices as human designers onto the evolutionary process, it can be set free to explore the full repertoire of behaviors the FPGA device can produce. Physical effects normally too complex or difficult to model can now be exploited in composing the overall behaviour.

These principles were adopted in evolving a $10\times 10$ corner of a XC6216 FPGA to discriminate between 1kHz and 10kHz square-waves (to produce a steady high output for one and a steady low for the other). A genetic algorithm was allowed to explore any possible configuration of the $10\times 10$ corner, and no external components were provided. In particular, there was no clock: to enforce a synchronisation constraint on the otherwise continuous-time dynamics of the device would be to pre-judge the strategies that evolution could explore. Figure 1 shows the final successful evolved circuit, and Figure 2 shows its behaviour and that of circuits at some intermediate stages in evolution. See [9] for full details. Note:

• The circuit is miniscule. A human designer, given the same resources (no external clock), would use much more area.
• It is operating as a continuous-time analogue dynamical system, even though the XC6216 is intended to be used as a digital device. The design constraints of a digital methodology were not imposed, so evolution has used whatever behaviours the chip manifested. See the intermediate output waveforms for a glimpse of the type of dynamics that was explored, and which presumably still underlies the final orderly behaviour.
• Even though the cells have propagation delays of only a few nanoseconds, only 32 were used in producing the neat discrimination between input periods of 1ms and 0.1ms: the strategy used must be unusual.
• The cells shaded gray are not connected to the main part of the circuit through conventional routing resources, but it can be shown that they are still contributing to the behaviour. Possible mechanisms include electromagnetic coupling, or interaction through the power-supply or substrate. Evolution was able to exploit this physical behaviour, even though it would be difficult to analyse.

Figure 1: The functional part of the evolved 1kHz/10kHz tone discriminator circuit ($10\times 10$ corner of XC6216 configuration)

Figure 2:Top: Input to the circuit; Below: corresponding output of the best individual in the population after 0, 1400 and 3500 generations of evolution (population size of 50). These are photographs of the oscilloscope screen.

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 $10\times 10$ 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.

Figure 3: Audio signals were thresholded to provide test inputs for incremental evolution of the discriminator circuit.

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. [11]. 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 [8] gives the full story in one volume.

I gratefully acknowledge the support of the following organisations: EPSRC, Xilinx, Hewlett Packard, British Telecom, Motorola, Zetex.
 

1999-02-23