Case Study

We now present an analysis of probably the most bizarre, mysterious, and unconventional unconstrained evolved circuit yet reported. The aim is to explore how analysis may be able to abate some of the worries associated with employing very unusual evolved circuits in an engineering application.

The task of the evolved circuit (Fig. 1) was simply to distinguish between 1kHz and 10kHz audio tones, producing a steady high output whenever one tone was present at the input, and a steady low for the other. It was evolved directly on a Xilinx XC6216 Field-Programmable Gate Array (FPGA). In simple terms, this VLSI device consists of an uncommitted array of components (or `cells'). Switches made from transistors (multiplexers) control how each component behaves, and how they are connected to each-other. The settings of the switches are controlled by the contents of RAM memory bits distributed throughout the chip; this memory can be rapidly and repeatedly written to by a host microprocessor, causing any of a vast number of possible electronic circuits to be physically instantiated in silicon.
 
 

Figure 1: The circuit for analysis, after pruning. For simplicity, only the connections between the cells are shown, not their functions, which are also under evolutionary control. Of the signals arriving from its four neighbours, those used as inputs to a cell's function are marked with small boxes. Each of a cell's four outputs (to the four neighbours) can be driven either directly from one of the cell's inputs, or by the output of the cell's function.

Evolution was allowed to exploit the capabilities of the FPGA as freely as possible. Each candidate design was a setting of the configuration bits for a $10\times10$ corner of the array of cells. To test its fitness, each design was configured onto a real FPGA (no simulation), half-second bursts of 1kHz and 10kHz test stimuli were applied to its input, and a fitness score was automatically assigned according to the degree to which the output approximated the desired discrimination behaviour. The behaviour of the final circuit (shown in the diagram) is near-optimal according to this fitness measure.

The FPGA chip is intended for digital designs: the cells can be configured to perform various Boolean functions. However, being made of real transistors, a cell is really an analogue component behaving in continuous time. These analogue cells have very high gain (amplification); for most inputs their output rapidly saturates either fully high or fully low. Consequently, if certain design-rules are followed, then the system's behaviour can be abstracted to a binary description: a digital logic system. The basic digital design rule is that recurrent connections -- paths through the circuit by which a component's output can (indirectly) later affect its own input -- must only be allowed to operate at particular discrete instants. This gives the components time to saturate to their extreme (digital) states before their inputs change again. In synchronous design, this is done on the ticking of a global `clock', whereas in asynchronous digital design more local co-ordination is used.

In our experiment, no constraints were placed on the circuit's structure or dynamical behaviour. No clock was provided, so evolution was searching the space of continuous-time dynamical systems made from the high gain analogue components normally used as logic gates. Evolution was free to explore the full repertoire of the FPGA's possible behaviours, of which digital systems constitute but a small subset. The components behave on the timescale of nanoseconds, and one of the original motivations of the experiment was to see if the dynamics of the FPGA could be organised to give an orderly behaviour on a very different timescale: the periods of the two tones to be distinguished are 1ms and 0.1ms. The experiment (fully described in [Thompson 1998]) was successful, and the resulting circuit of Fig. 1 is considerably smaller than would be achieved by conventional methods given the same resources.

Until the present study, one could only speculate as to the circuit's means of operation, so unusual are its structure and dynamics. It was clear that continuous time played an important role. If the circuit was configured onto a different, but nominally identical, FPGA chip (not used during evolution), then its performance was degraded. If the temperature is raised or lowered, then the circuit still works, but the frequencies between which it discriminates are raised or lowered. (Digital circuits usually display unchanged behaviour followed by brittle failure on approaching their thermal limits.)[Thompson 1997b] These initial observations warranted a concerted application of our tactics for unconventional analysis.

In Figure 1, the first analysis step has already been taken. Of the $10\times10$ corner of FPGA cells, only those actively contributing to the behaviour are shown. All of the cells not shown can be simultaneously `clamped' without affecting the output. To clamp a cell, the configuration sent to the FPGA was changed so that the cell's function produced a constant output, and this sourced all four of the cell's output connections. Where a connection is shown passing through a clamped cell, all of the cell's attributes except for this connection could be clamped. The cells shaded grey in the diagram were enigmatic. Although not connected to the rest of the circuit, if they were clamped then the output became less reliable, briefly changing to spurious states occasionally. One of the aims of further analysis was to learn the influence of these `grey cells'.

If the input frequency was gradually changed from 1kHz to 10kHz, the output (low at 1kHz) would begin rapidly to alternate between low and high, spending more time high as the frequency was increased, eventually staying steady high for frequencies near 10kHz. This binary behaviour of the output voltage suggested that perhaps part of the system could be understood in digital terms. By temporarily making the assumption that all of the FPGA cells were acting as Boolean logic gates in the normal way, the FPGA configuration could be drawn as the logic circuit diagram of Figure 2.
 
 

Figure 2: The logic circuit representation. The numbers in hexagons are rough estimates of time delays (in ns), based on the maximum values specified by the manufacturer. `IOB' refers to the inverting Input/Output Blocks that interface the edges of the reconfigurable array to the physical pins of the chip.

The logic circuit diagram shows several continuous-time recurrent loops (breaking the digital design rules), so the system's behaviour is unlikely to be fully captured by this Boolean level of abstraction. However, it contains many `canalysing' functions [Kauffman 1993], such as AND and OR: functions where one input can assume a value which makes the other inputs irrelevant. It so happens that whenever our circuit's input is 1, all of the recurrent loops in Parts A & B are broken by a cascade of canalysing functions. Within 20ns of the input becoming 1, A and B satisfy the digital design rules, and all of their gates deterministically switch to fixed, static logic values, staying constant until the input next goes to 0.

Part C of the circuit is based around a 2:1 multiplexer. When Part B is in the static state, the multiplexer selects the input marked `1' to be its output. This input comes from the multiplexer's own output via an even number of inversions, resulting in no net logic inversion but a time delay of around 9ns. Under certain conditions, it is possible for such a loop to oscillate (at least transiently), but the most stable condition is for it to settle down to a constant logic state. The output of the whole circuit is taken from this loop. As this Part C loop provides the only possibility for circuit activity during a high input, the next step in the analysis was to inspect the output very carefully while applying test inputs.

We had already observed that the output only ever changes state (high$\Rightarrow$low or low$\Rightarrow$high) on the falling edge of the input waveform (Fig. 1). Although never required to do so during evolution, we discovered that the output also responds correctly to the width of single high-going pulses. Figure 3 shows a low$\Rightarrow$high output transition occurring after a short pulse; further short pulses leave the output high, but a single long pulse will switch it back to the low state. The output assumes the appropriate level within 200ns after the falling edge of the input. The circuit does not respond to the width of low-going pulses, and recognises a high-going pulse delimited by as little as 200ns of low input at each end of the pulse. The output is perfectly steady at logic 1 or 0, except for a brief oscillation during the 200ns `decision time' which either dies away or results in a state change.
 
 

Figure 3: The response to a single high-going pulse.

This is astonishing. During the single high-going pulse, we know that parts A and B of the circuit are `reset' to a static state within the first 20ns (the pulse widths are vastly longer: 500$\mu$s and 50$\mu$s correspond to 1kHz and 10kHz). Our observations at the output show that Part C is also in a static state during the pulse. Yet somehow, within 200ns of the end of the pulse, the circuit `knows' how long it was, despite being completely inactive during it.

This is hard to believe, so we have reinforced this finding through many separate types of observation, and all agree that the circuit is inactive during the pulse. Power consumption returns to quiescent levels during the pulse. Many of the internal signals were (one at a time) routed to an external pin and monitored. Sometimes this probing altered (or destroyed) the circuit's behaviour, but we have observed at least one signal from each recurrent loop while the circuit was successfully discriminating pulse-widths, and there was never activity during the pulse. We were concerned that perhaps, because of the way the gates are implemented on the FPGA, it was possible that glitches (very short-duration pulses) were able to circulate in the circuit while our logic-analysis predicts it should be static; possibly these glitches could be so short as to be unobservable when routed to an external pin. Hence, we hand-designed a high-speed `glitch-catching' circuit (basically a flip-flop) as a configuration of two FPGA cells. Glitches sufficiently strong to circulate for tens of microseconds could be expected to trigger the glitch-catcher, but it detected no activity in any of the recurrent loops during an input pulse.

We performed a digital simulation of the circuit (using PSPICE), extensively exploring variations in time-delays and parasitic capacitances. The simulated circuit never reproduced the FPGA configuration's successful behaviour, but did corroborate that the transient as the circuit enters its static state at the beginning of an input pulse is just a few tens of nanoseconds, in agreement with our experimental measurements of internal FPGA signals, and according with the logic analysis. We then built the circuit out of separate CMOS multiplexer chips, mimicking the way that the gates are actually implemented by multiplexers on the FPGA, and also modelling the relative time-delays. Again, this circuit did not work successfully, and -- despite our best efforts -- never produced any internal activity during an input pulse.

We then went back to find the first circuit during the evolutionary run which responded at all to input frequency. Its behaviour is shown in Figure 4. During a pulse, the output is steady low. After the pulse, the output oscillates at one of two different frequencies, depending on how long the preceding pulse was. These oscillations are stable and long-lasting. The differences are minor between this circuit and its immediate evolutionary predecessor (which displays no discrimination, always oscillating at the lower of the two frequencies). In fact, there are no differences at all in the logic circuit diagrams; the changes do things like alter where a cell's function takes an unused input from. This lends further support that circulating glitches are not the key: there was no change to the implementation of the recurrent loops.
 
 

Figure 4: Behaviour of the first frequency-discriminating ancestor. The upper waveform is the output, and the lower the input; we see the behaviour immediately after the falling edge of a single input pulse. Left: long pulse, Right: short pulse. The input to the FPGA is actually delayed$\sim$ 40ns by an intervening buffer, relative to the wave seen here.

We see bistable oscillations reminiscent of Fig. 4 at internal nodes of part A of the final circuit. On being released from the canalysed stable state, the difference in the first 100ns of oscillatory behaviour in part A is used by parts B & C to derive a steady output according to the pulse width. There is some initial state of the part A dynamics which is determined by the input pulse length. This initial state does not arise from any circuit activity in the normal sense: the circuit over the entire array of cells was stable and static during the pulse. It is a particular property of the FPGA implementation, as it is not reproduced in simulation or when the circuit is built from separate small chips. One guess is that the change in initial state results from some slow charge/discharge of an unknown parasitic capacitance during the pulse, but we cannot yet be sure.

We understand well how parts B & C use A's initial oscillatory dynamics to derive an orderly output, and have successfully modelled this in simulation. The time delays on the connections from A to B & C are crucial. This explains the influence of the `grey cells', which are all immediately adjacent to (or part of) the path of these signals. Varying the time delays in the simulation produces a similar result to interfering with the grey cells. Mostly, the loop of part C serves to maintain a constant and steady output even while the rest of the circuit oscillates, but immediately after an input pulse it has subtle transient dynamics interacting with those of A & B.

1998-11-18