Evolving circuits (was Re: ebay - cardamatic)

From: Sean 'Captain Napalm' Conner <spc_at_conman.org>
Date: Wed Feb 16 19:02:06 2005

It was thus said that the Great Tony Duell once stated:
>
> > It will only get worse. There's a scientist applying genetic algorithms
> > [1] to hardware [2]. The scientist, Adrian Thompson, used an FPGA and
>
> I am sorry, I'd not call him a 'scientist'. At least not in this bit of work.

  The article called him one---I'm just repeating what I read.

> > "bred" configurations (on a 10x10 area of the chip) to discrimiate between
> > a 1kHz and a 10kHz signal:
>
> Assuming that's 100 logic blocks and the chip is of normal-ish speed,
> that's nowhere near enough gates to get a 1ms-ish delay. So that sort of
> method can be ruled out I think.

  The article did mention that; in fact, the article goes into a bit more
depth than just the portion I quoted.

> > So how did evolution do it--and without a clock? When he looked at
> > the final circuit, Thompson found the input signal routed through a
> > complex assortment of feedback loops. He believes that these
> > probably create modified and time-delayed versions of the signal
> > that interfere with the original signal in a way that enables the
> > circuit to discriminate between the two tones. "But really, I don't
> > have the faintest idea how it works," he says.
>
> Does he even have an idea as to what the circuit _claims_ to be without
> any extra artefacts (like signal coupling between adjaent traces on the
> chip)? If not, %deity help us.

  He didn't "design" the circuit. What he did was generate X number of
random FPGA configurations for the 10x10 cell area, tested each one, and
those that were more promising kept and randomly mutated with each other;
the configurations that didn't pass were dropped. This process is then
repeated until you get the desired result. The article mentions it took
around 4,000 "generations" until he got a circuit that could discriminate a
1kHz and 10kHz signal.

> If he does, then it's possible (and can't be that hard, it's a lot
> simpler than most of the things I've had to analyse [1]) to work out what
> that circuit would do. At least then you'd know if it was down to some
> odd behaviour of that particular device.

  I think the closest you could come to this is to take a pile of random
components, wire them up randomly and then figure out what it does by just
looking at the connections. In Thompson's case, the circuit does what he
wants it to, but there are effects happening that can't be explained (I know
that a diode will trigger after .7v are applied, but that figure may be an
average and one particular diode may trigger at .69v, while another one at
.70002v. In most cases, this doesn't really effect the working of the
circuit, but in this case, the "circuit" may be using the fact that *this
cell* has a capacitance of 34uF and *that cell* an inductance of X units of
<whatever inductance is measured in> and the signal going through *these
five cells* takes 3.1415nS and *those five cells* in 3.1419nS and all this
together does what he wants it to do, but without *very sensitive* equipment
it would be hard to actually *know* what it is the chip is doing, just by
looking at the wiring alone.

> > Thompson says the feedback loops in the final circuit are unlikely
> > to sustain the 0 and 1 logic levels of a digital circuit. "Evolution
> > has been free to explore the full repertoire of behaviours available
> > from the silicon resources," says Thompson.
>
> What is that supposed to mean?

  I think what that means is that the circuit bred is using some very subtle
effect of the actual gates themselves (see above) that in normal use doesn't
matter.

> > That repertoire turns out to be more intriguing than Thompson could
> > have imagined. Although the configuration program specified tasks
> > for all 100 cells, it transpired that only 32 were essential to the
> > circuit's operation. Thompson could bypass the other cells without
>
> So we're now down to aropund 100 gates/ffs. The sort of thing that can be
> analysed by hand in an afternoon...
>
> > affecting it. A further five cells appeared to serve no logical
> > purpose at all--there was no route of connections by which they
> > could influence the output. And yet if he disconnected them, the
> > circuit stopped working.
>
> OK, it must be some kind of coupling. Either capacitive coupling between
> traces, or via the PSU, or...

  I do know that in another article I read on this, that moving the
configuration to another area *on the same chip* caused it to fail. And
yes, I've encounted programs like that 8-)

  The way around that is to run the "configurations" on multiple chips and
breed those; that should breed a version that isn't supsceptible to minor
variations in the gates of the FPGA.

> > It appears that evolution made use of some physical property of
> > these cells--possibly a capacitive effect or electromagnetic
> > inductance--to influence a signal passing nearby. Somehow, it
> > seized on this subtle effect and incorporated it into the solution.
>
> My big worry is that he doesn't really understand the chip. He doesn't
> know how signals are routed, he doesn't know what sort of coupling is
> going on, he doersn't know how the various logic gate behave (can they
> actually behave linearly?). So IMHO this piece of work is totally
> meaningless! That's one reason I don't want to call him a scientist.

  At a certain level (size wise), don't quantum effects take over?

> > -spc (Welcome to the future of non-deterministic hardware/software
> > design 8-P
>
> Fortunately my classic computers use deterministic designs, and I am
> quite happy to stick to those!

  I remember Michael Abrash (in his _Zen and the art of Assembly
Optimization_) spending a chapter on what exactly happens during five or six
instructions on the 8088, explaining what happens on each cycle and that
even then, that just covered *those five instructions* *at that particular
memory location* *for that instance in time* and that another capture would
reveal a different count of cycles, due to the pipe line, DMA and RAM
refresh. Not very deterministic behavior for a "classic computer".

  -spc (Not that I'm thrilled with genetic algorithms myself ... )
Received on Wed Feb 16 2005 - 19:02:06 GMT