Evolving circuits (was Re: ebay - cardamatic)

From: Tony Duell <ard_at_p850ug1.demon.co.uk>
Date: Thu Feb 17 18:15:44 2005

> > 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.

Sure.
> > 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

Sure. But presumably it's possible to read out the final configuration
from the FPGA and analyse it assuming the FPGA behaves exactly as the
data sheet claims (i.e. no hidden capacitive coupling, etc). Has this
been done? If not, why not?

> those that were more promising kept and randomly mutated with each other;
> the configurations that didn't pass were dropped. This process is then

Obviously I don;t know how this was done, but I know from bitter (and
expensive) experience that some configuration patterns for some FPGAs can
do things like connect outputs together inside the chip (and other things
that no sane designer would want to do). I got a rather expensive FPGA
hot enought to let the magic smoke out by doing that...

Do we know that there are no illegal things like that in the final
configuration.
> 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

If it is something like this, then it's going to be hellishly unreliable!

> 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.

My point is to look at the connections and try to analyse the circuit
based on that. Prove that coa't be the whole story and then investigate
what coupling, etc, sould possibly explain the observed behaviour.

> 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.

Another question. Is this circuit reproducable? If you take the final
configuration and program it into another FPGA of the same type, does it
work? That, I think, would isolate coupling effects (which would be much
the same for all FPGAs of a given type) from threshold effects (which
wouldn't).


> > 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-)


OK, that would seem to indicate there's more to this than the observed
connections. But it doesn't isolate coupling from threshold effects. Both
would change if you moved the circuit around the chip.

> 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.

Unless of course it _depecds_ on these variations, in which case you'll
end up breeding something that doesn't work at all.

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

Yes, but a lot smaller than the cells of any normal FPGA.

> 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".

Not so. Every (correctly-working :-)) computer I've worked on has been
entirely deterministic. OK, you will have to take account of DMA (and
refresh, which was done by the DMA controller in the PC and XT),
Interrupts, etc...

If you're tracing a program you might find the execution suddendly goes
to an ISR because somebody has pressed a key or something. But pressing
that key at the exactly same point in the progrma will cause the machine
to do the same thing each time. It's possible to understand what is going
on _precisely_ provided you take into account all the variables. Every
flip-flop changes state for a precisely-defined set of conditions.
There's nothing random about it.

-tony
Received on Thu Feb 17 2005 - 18:15:44 GMT