This Issue's Contents

BCS Logo

Leading Edge

The chip that designs itself

Adrian Thompson's research has progressed so far that he no longer knows how his chips work. Clive Davidson meets a man who uses the principles of evolution in processor logic design

When microprocessor designers set out to create logic circuits they analyse the tasks they must fulfil and specify the solutions using a number of digital components. The manufacturers then fabricate these designs into silicon. But what if we could by-pass the human designers and give the tasks directly to the silicon components and tell them to get on with it? Would the hardware do it differently if left to its own devices? And would we understand what it did?

This is not science fiction speculation. For a researcher at Sussex University has done just that. He has found a way of allowing microprocessor hardware to use the principles of Darwinian evolution to create its own designs. And he has got to the point where he does not understand how the circuits work - only that they are far more efficient than any human could design.

Adrian Thompson, who works at the university's Centre for Computational Neuroscience and Robotics, came up with the idea of self-designing circuits while thinking about building neural network chips. A graduate in microelectronics, he joined the centre four years ago to pursue a PhD in neural networks and robotics.

Neural networks are highly simplified models of the human brain. They were devised by artificial intelligence researchers to mimic mental processes in an attempt to create intelligent systems. Neural networks have proved useful for some tasks such as pattern recognition and database searching. Developers usually simulate the networks of artificial neurons in software, but some hard-wire the networks on chips.

Either way, thought Adrian Thompson, it is a case of imposing a biological design on a completely foreign medium. The human brain evolved over millions of years, taking advantage of the inherent physical, chemical, electrical and other properties of organic matter. What if we could re-run evolution, only this time in silicon? Would it produce a design customised to the properties of the silicon?

The problem was how to introduce the wet, vital forces of evolution, with its processes of mating, mutation and reproduction, into the dry, mechanical world of silicon. Adrian Thompson found his solution in genetic algorithms and field programmable gate arrays.

Genetic algorithms are another fairly recent addition to the artificial intelligence researcher's tool-box. A genetic algorithm is a program that simulates evolutionary processes to 'breed' the best solution to a problem where there are a number of possible solutions.

The user starts by expressing a set of arbitrary solutions as strings of binary code. This is the initial population. The algorithm checks each member of the population to see how well it solves the problem: the fitness test. It deletes those that do badly and makes copies of those that do well. It allows some of the solutions to 'mate' by swapping over parts of their code strings. And it introduces some mutation by switching at random a number of bits in the population's code strings from one to zero or vice versa. Then it runs the cycle of fitness test, mating, mutation and reproduction over again. The process ends when further iterations make no improvement to the evolved solution.

Genetic algorithms can provide a fast method of searching for optimal solutions and people have used them for everything from selecting high performing shares on the stock market to creating works of art. Sussex University's Centre for Computational Neuroscience and Robotics is a leading international centre of research into the use of such algorithms.

Adrian Thompson knew he could use genetic algorithms to simulate evolution but the problem remained of how to insert this process into the silicon world.

The solution appeared with a new generation of programmable chips. Conventional microprocessors have their logic circuits hard-wired onto the silicon. Field programmable gate arrays (FPGAs), on the other hand, have an array of components: the designer specifies the logic and interconnections in software and then downloads them to the chip.

Adrian Thompson saw that he could get a genetic algorithm to create the circuit designs in software but run the fitness tests on the physical circuits.

'I realised I could let the genetic algorithm work with the medium to find the intrinsic resources of the medium,' he says.

To test his theory, he got hold of a new FPGA from specialist Xilinx Development in Edinburgh which, unlike previous generations, had no limit on how many times it could be reprogrammed or what circuits could be implemented. He set the FPGA and its genetic algorithm the task of designing a circuit that could discriminate between two audio tones - one at 1KHz and another at 10KHz. The circuit had to output a steady five-volt signal when it heard one of the tones and a zero-volt signal when it heard the other.

To get the experiment started, he created an initial population of 50 random circuit designs coded as binary strings. The genetic algorithm, running on a standard PC, downloaded each design to the FPGA and tested it with the two tones generated by the PC's sound card. At first there was almost no evidence of any ability to discriminate between the two tones, so the genetic algorithm simply selected circuits which did not appear to behave entirely randomly. The fittest circuit in the first generation was one that output a steady five-volt signal no matter which tone it heard.

By generation 220 there was some sign of improvement. The fittest circuit could produce an output that mimicked the input - wave forms that corresponded to the 1KHz or 10KHz tones - but not a steady zero or five-volt output.

By generation 650, some evolved circuits gave a steady output to one tone but not the other. It took almost another 1,000 generations to find circuits that could give approximately the right output and another 1,000 to get accurate results. However, there were still some glitches in the results and it took until generation 4,100 for these to disappear.

The genetic algorithm was allowed to run for a further 1,000 generations but there were no further changes.

Designing a circuit to discriminate between two audio tones is a relatively simple task for a human microprocessor designer. However, Adrian Thompson deliberately did not give the genetic algorithm a component that would be essential to a human designer: a clock.

The logic components of microprocessors are made out of transistors that flip between on and off - equivalent to binary ones and zeroes - as the chip carries out coding instructions. But transistors are analogue devices that take some time to charge up to an 'on' setting or to discharge to 'off'. To allow time for the transistors to turn fully on or off, and therefore to give binary values, circuit designers use a clock to stagger the processing of instructions. Although the time intervals are minute - modern PC processor clocks typically tick at over 100m times a second (100MHz) - a clock is critical to the operation of a digital system.

A conventional, human approach to designing a circuit to discriminate between two tones would use a clock to count the intervals between the peaks of the tone sound waves - with longer intervals between the 1KHz tones than between the 10KHz tones. If no clock was available among the components, the human designer would need to create one on the chip. This is not difficult - but it would take far more than the array of 1010 logic components that Adrian Thompson allocated on the FPGA for his experiment.

So without a clock or the apparent wherewithal to make one, how did the genetic algorithm and FPGA solve the problem?

'I haven't the faintest idea how the circuit works,' he says.

Nonetheless, some things are clear. The circuit operates in an analogue - not digital - manner. And it uses the physical properties of the FPGA - possibly capacitive effects or electromagnetic inductance - to create a highly efficient solution. So efficient, in fact, that a number of organisations are now taking a keen interest in Adrian Thompson's work.

The FPGA maker Xilinx is now sponsoring him. The company's head, John Gray, believes the research is ground breaking and 'could have early applications in mundane but important situations like controlling traffic flows'.

One kind of traffic could be telecommunications signals, and British Telecom is now sponsoring Adrian Thompson's colleague Paul Layzell, who is extending his work. Motorola is also interested, as is the space industry, which is always looking for more compact devices. But there is some way to go before evolved circuits will be in general use. One issue is the robustness of the circuit designs to changes in their environment. For example, Adrian Thompson's circuit works perfectly over a temperature range of around 10_C. Raise or lower the temperature beyond these limits and it starts to malfunction.

But resilience to temperature change was not part of the fitness test, he says. He is currently working on a new set of experiments that will attempt to evolve circuits that are tolerant to temperature changes and to hardware faults.

'There's no reason to think that evolution can't find a strategy that would handle a wide range of temperatures,' he says. Evolution is particularly good at creating fault tolerant systems and this could be one of the major attractions of evolved designs.

But solving the robustness issues might just be the first problem the circuits face. If they evolve to the point where they are useful in, say, engine control systems or medical equipment, we will face an ethical dilemma.

As Inman Harvey, research fellow in evolutionary robotics at the Sussex centre, says, 'How acceptable is a safety-critical component of a system if it has been artificially evolved and nobody knows how it works?'

The answer, he suggests, will mean accepting that we already rely on systems designed by conventional means that we cannot prove will work under all conditions and in the rigorous testing of the evolved devices.

Some believe that evolved hardware is the beginning of a process that will lead to a new generation of machines beyond our understanding or control.

Adrian Thompson himself is reluctant to speculate on where his experiments might lead. 'I'm not trying to beat traditional human designers at their own game,' he says. 'I'm just trying to explore what evolution can do.'

Spreading the word

This regular Leading Edge feature is a chance for researchers in universities and industry to share their experience with the information systems professionals who will ultimately use the results of their work, and with other researchers. People researching the technologies which could underlie the computer designs, software development techniques and automated working methods of the future are invited to contact The Computer Bulletin editor (see the Keep in touch panel at the bottom of the Contents page).

Clive Davidson is a freelance journalist.

This Issue's Contents

Copyright British Computer Society 1998