Unconstrained Temporal Structure

  Real physical electronic circuits are continuous-time dynamical systems. They can display a broad range of dynamical behaviour, of which discrete-time systems, digital systems and even computational systems are but subsets. These subsets are much more amenable to design techniques than dynamical electronic systems in general, because the restrictions to the dynamics that each subset brings support design abstractions, as described above. Intrinsic EHW does not require abstract models, so there is no need to constrain artificially the dynamics of the reconfigurable hardware being used.

In particular, there no longer needs to be an enforced method of controlling the phase (temporal co-ordination) in reconfigurable hardware originally intended to implement digital designs. The phase of the system does not have to be advanced in lock-step by a global clock, nor even the local phase-controlling mechanisms of asynchronous digital design methodologies imposed. The success of pulse-stream neural networks [19, 20], where analogue operations are performed using binary pulse-density signals, gives a clue that allowing the system's phase to unfold in real-time in a way useful to the problem at hand can add a powerful new dimension to electronic systems: time. Mead's highly successful analogue neural VLSI devices (eg. the `silicon retina') [21], exploiting the continuous-time dynamics of networks of analogue components (with the transistors mostly operating in the sub-threshold region), show how profitable an excursion into the space of general dynamical electronic systems can be.

In some applications, dynamics on more than a single timescale are needed in an EHW circuit. For example, a real-time control system needs to behave on a timescale suited to the actuators (typically in the range milliseconds to seconds), while the underlying dynamics of the controller's electronic components might be measured in nanoseconds. Being able to have different parts of a circuit behaving at different timescales can also be significant in other ways; indeed, learning can be thought of as a dynamic on a slower timescale than individual task-achieving behaviours.

There are several ways in which high-speed electronic components can give rise to much slower behaviour:

• The phase can be governed by one or more external signals, a digital clock being the prime example.
• Large time-constant resources can be provided. Large capacitors or inductors cannot be made in VLSI, so either external components can be made available, or special techniques can be used to make the most of smaller on-chip components [22].
• The high-speed components can somehow be assembled to give rise to slower dynamics, without explicitly providing large time-constant resources or slow-speed clocks.

Is the last of these possibilities feasible in an EHW framework? To find out, a simulation experiment was performed to see if a network of high-speed logic gates could be evolved to oscillate at a much slower timescale. The number of logic nodes available was fixed at 100, and the genotype determined which of the boolean functions of Table 1(a) was instantiated by each node, and how the nodes were connected. The nodes were analogous to the reconfigurable logic blocks of an FPGA, but an input could be connected to the output of any node without restriction. The linear bit-string genotype consisted of 101 segments (numbered 0..100 from left to right), each of which directly coded for the function of a node and the sources of its inputs, as shown in Table 1(b). (Node 0 was a special `ground' node, the output of which was always clamped at logic zero.) This encoding is based on that used in [23]. The source of each input was specified by counting forwards/backwards along the genotype (according to the `Direction' bit) a certain number of segments (given by the `Length' field), either starting from one end of the string, or starting from the current segment (dictated by the `Addressing Mode' bit). When counting along the genotype, if one end was reached, then counting continued from the other.

 

 
Table 1: (a) Node functions

 

BITS MEANING

0-4 Junk

5-7 Node Function POINTER TO FIRST INPUT

8 Direction

9 Addressing Mode

10-15 Length POINTER TO SECOND INPUT

16 Direction

17 Addressing Mode

18-23 Length

At the start of the experiment, each node was assigned a real-valued propagation delay, selected uniformly randomly from the range 1.0 to 5.0 nanoseconds, and held to double precision accuracy. These delays were to be the input-output delays of the nodes during the entire experiment, no matter which functions the nodes performed. There were no delays on the interconnections. To commence a simulation of a network's behaviour, all of the outputs were set to logic zero. From that moment onwards, a standard asynchronous event-based logic simulation was performed [24], with real-valued time being held to double precision accuracy. An equivalent time-slicing simulation would have had a time-slice of seconds, so the underlying synchrony of the simulating computer was only manifest at a time-scale 15 orders of magnitude smaller than the node delays, allowing the asynchronous dynamics of the network to be seen in the simulation. A low-pass filter mechanism meant that pulses shorter than 0.5ns never happened anywhere in the network.

The objective was for node number 100 to produce a square wave oscillation of 1kHz, which means alternately spending seconds at logic 1 and at logic 0. If k logic transitions were observed on the output of node 100 during the simulation, with the transition occurring at time seconds, then the average error in the time spent at each level was calculated as :

For the purpose of this equation, transitions were also assumed to occur at the very beginning and end of the trial, which lasted for 10ms of simulated time. The fitness was simply the reciprocal of the average error. Networks that oscillated far too quickly or far too slowly (or not at all) had their evaluations aborted after less time than this, as soon as a good estimate of their fitness had been formed. The genetic algorithm used was a conventional generational one [3], with elitism and linear rank-based selection. At each breeding cycle, the 5 least fit of the 30 individuals were killed off, and the 25 remaining individuals were ranked according to fitness, the fittest receiving a fecundity rating of 20.0, and the least fit a fecundity of 1.0. The linear function of rank defined by these end points determined the fecundity of those in-between. The fittest individual was copied once without mutation into the next generation, which was then filled by selecting individuals with probability proportional to their fecundity, with single-point crossover probability 0.7 and mutation rate per bit.

Fig. 1 shows that the output of the best individual in the generation (Fig. 2) was approximately thousand times slower than the best of the random initial population, and was six orders of magnitude slower than the propagation delays of the nodes. In fact, fitness was still rising at generation 40 when the experiment was stopped because of the excessive processor time needed to simulate this kind of network. This result suggests that it is possible for evolution to arrange for a network of high-speed components to generate much slower behaviour, without having to provide explicit `slowing-down' resources with large time constants, and without the need for a clock (though these could still be useful).

  
Figure 1: Output of the evolving oscillator. (Top) Best of the initial random population of 30 individuals, (Bottom) best of generation 40. Note the different time axes. A visible line is drawn for every output spike, and in the lower picture each line represents a single spike.

  
Figure 2: The evolved 4kHz oscillator (unconnected gates removed, leaving the 68 shown).

The evolved oscillators produced spike trains rather than the desired square wave. Probing internal nodes indicated that this was because beating between spike trains of slightly different frequencies was being used to generate a much lower frequency; beating only works for spikes, not for square waves. This does not mean that the task was easy: it is difficult for beats to reduce the frequency by the massive factor required and yet produce an output as regular as that seen in Fig. 1.

The simulation was quite an unrealistic model of the evolution of the configuration of a real FPGA. No analogue effects were modelled apart from time, but they would be a big part of the way a real chip would behave. Nevertheless, the result lends strength to the concept of evolving unconstrained dynamical systems, because beating evolved: a highly effective solution which is essentially a continuous-time phenomenon. Beating does not just occur at one node but throughout the network, which does not have any significant modules.