Results and Preliminary Analysis

The final circuit works near-perfectly on all of the FPGAs and conditions of Table 1. The only room for improvement is that sometimes when the input frequency is changed, the circuit's output responds after several cycles of the input, rather than after the minimum of a single half-cycle. For steady 1kHz or 10kHz input, in 24-hour tests no unwanted transitions in the output occurred.

As a further test of robustness, the final circuit was tested on six XC6216 FPGAs that were not used during evolution, including samples from both foundries. Each chip was first frozen to $\simeq-50^{\circ}$C using freezing spray, then the circuit's operation was monitored as the chip warmed to room temperature. The same near-perfect performance as before was seen in all of these conditions, indicating that the evolved design is usefully robust.

Figure 1 shows the functional part of the circuit. The configuration can be changed to clamp to constant values those cells and connections not shown, without affecting the behaviour.

Figure 1: The functional part of the evolved configuration. The large boxes represent the cells. A wire shown originating from the perimeter of a cell is the output of that cell's function unit. Inputs to a cell's function unit are indicated with small squares. If a cell's function unit output is taken from it's flip-flop (synchronous), then a small triangle is drawn at the bottom of the cell. The configurations of the function units are not shown. The cells are labelled with their (row, column) co-ordinates within the $10\times 10$ evolved array.

We now wish to discern whether there has been any advantage in allowing evolution the freedom to explore beyond conventional digital design rules. To see if any or all of the circuit's behaviour fits into a digital-logic model of operation, it was simulated in a well-known digital simulator (PSpice$^{TM}$). Working with noise-free binary signals, for each kind of component there is a model describing the internal propagation times from the component's inputs to its output. At the start of the simulation, the propagation times of each component are increased by a load model, to take account of what loads that output must drive.

The simulation model of the FPGA used components from the 74AC family, with the propagation times changed to match the approximate figures given in the datasheet [15]. Where necessary, the simulator defaults for the relationships between minimum, typical, and maximum timings were used. The other details, such as the loading model, were unchanged. The reconfigurable multiplexers were replaced by inverters or buffers hard-wired according to the final evolved configuration. The resulting model is shown in Figures 2 and 3, which also show all the details not visible in Figure 1.

Figure 2: The left half of the simulation model.
 

Figure 3: The right half of the simulation model.

The circuit worked first time in simulation, without any need to fine-tune the component timings. This means it does not rely on any aspects of the chips not captured in the simulation. In particular, it does not rely on any analogue effects, in contrast to an earlier experiment in which robustness was not an objective [13]. On a Pentium 233MHz processor with 32MB of memory, the simulation ran $\simeq 62000$ times slower than real time.

Using the schematic and simulation traces, the circuit appears to operate as shown in Figure 4. First, the input $I$ is `retimed' (sampled) to the 6MHz clock in cell (5,0). When the retimed input $R$ is high, cell (7,0) toggles at the clock frequency. When $R$ is low, this oscillation stops. Since the sampling in cell (5,0) delays $R$ by up to (but less than) a clock period with respect to $I$, the number of times the oscillator toggles is completely determined by how long the raw input is high, and hence on the input frequency. For some input frequencies, the oscillator toggles an odd number of times, so finishes in a different state, whereas for others it does not. This is the heart of the timing mechanism; cell (7,2) simply holds the final value of the previous oscillation while the next one is going on, and this is the output of the circuit.

Figure 4: An outline of the mechanism.

The core mechanism described so far uses only three cells, but would, at best, produce a constant output for one input frequency and an output toggling every cycle at the other input frequency. The function of all of the other cells in the circuit is to correct this, by delaying the retimed input. The delay on falling edges is constant, but for rising edges is variable, and is a function of the present output of the circuit. This is arranged so that if the input is 1kHz while the output is high, or if the input is 10kHz while the output is low, then the oscillator will have time for an odd number of toggles in a high half-cycle of the input, and the output will change state. If the input is 1kHz while the output is low, or 10kHz while it is high, then the oscillator toggles an even number of times and the output is constant. The implementation of the variable delay is not yet understood.

The simulator is able to report whenever there is a flip-flop data-to-clock setup time violation: that is, when the input to a flip-flop changes so soon before the clock edge arrives that the resulting output is uncertain. Setup time violations are only ever reported in the cell (5,0) which retimes the input: the other nine flip-flops in the evolved design operate in a reliable clocked fashion.

Figure 5: Typical cell outputs during simulation.

2000-02-03