The Xilinx XC6216 [15] Field
Programmable Gate Array (FPGA) [11]
is a reconfigurable VLSI chip particularly suitable for evolutionary work.
It will soon be commercially available -- the work reported here was carried
out on a 
-test version. A simplified representation of the
device is shown in Fig. 1.
Figure 1: A simplified view of the XC6216 FPGA. Only those features used in the
experiment are shown. Top: A 
corner of the 
array of cells; Below: the internals of an individual cell, showing the
function unit at its centre. The symbol
represents a multiplexer --
which of its four inputs is connected to the output (via an inversion) is
controlled by the configuration memory. Similar multiplexers are used to
implement the user-configurable function F.
It has an array of
reconfigurable cells, each of which is connected to its four
neighbours: North, East, West and South (NEWS) as shown. There is also a
hierarchical arrangement of wires spanning 4, 16 and 64 cells, but these were
not used in this experiment. Each cell contains a function unit that can be
configured to perform any boolean function of two inputs, or multiplexer
functions of three inputs. Each of a function unit's three inputs (not all of
which are necessarily used) can be configured to be sourced by any of the four
NEWS neighbours. The output of a cell in each of the NEWS directions can be
configured to be driven either by the output F of its function unit, or by the
signal arriving at one of the other NEWS faces. This allows a cell
to connect some of its NEWS neighbours directly together at the same time as
performing a function; a cell can `route across itself' in some directions
while giving the output of function F in others. The cells are configured
independently (they do not all perform the same function), so even using only
the nearest-neighbour links a very large range of possible circuits can be
implemented.
Around the periphery of the array of cells are Input/Output Blocks (IOBs) and
pads that interface the signals at the edge of the array to the pins of the
chip. This is done in a more complex and flexible way than shown in the
figure; all that is important here is that the chip was configured with a
single input and a single output as shown. The choice of input and output
positions was made before the experiment started, and then kept fixed. The
unused IOBs simply appeared as inputs of a constant value. Only a
corner of the chip was used, and the unused cells were also configured just to
produce a constant value. There are numerous other features of the device that
were not used, and have not been mentioned.
At any time, the configuration of the chip is determined by the bits held in
an on-chip memory, which can be written from software running on a host
computer. No configuration of the cells can cause the device to be damaged --
it is impossible to connect two outputs together, for instance, because all
internal connections are uni-directional. So an evolutionary algorithm can be
allowed to manipulate the configuration of the real chip without the need for
legality constraints or checking. Here, we directly encode the configuration
bits for the corner -- determining how the four outputs of each
cell are derived and what function is performed by each function unit -- onto
a linear bit-string genotype of length 1800 bits. This was done in a raster
fashion, reading cell-by-cell from left to right along each row, and taking
the rows from bottom to top.