[Hardware] FPGAs

[Jecel Assumpcao Jr]

I was asked about FPGAs and materials about them. Perhaps my reply will
be of interest to other people on this list, so here is what I wrote:

I happen to be writting a 20 page report on "reconfigurable computing"
which includes some material that might be interesting, but sadly it is
in Portuguese. I did a search for "fpga tutorial" but was not happy with
the results I saw. This site has some interesting stuff but is probably
not the first place you should look:

http://www.fpga4fun.com/

Here is a very short version of the introduction I am writing:

There are two types of logic circuits - combinational ones which depend
only on their current inputs and sequential ones which depend on their
current and past inputs. The latter are circuits which include memory.

Normally combinational circuits are implemented by connecting together a
bunch of simple logic gates, like AND, OR and NOT. But an alternative is
to use a memory circuit, ironically enough. You simple connect the
inputs to the address pins and use the data pins as the outputs.

For example, imagine you have a combinational circuit which takes two
inputs of two bits each (A1, A0, B1 and B0) and outputs three bits
representing their sum. You can do this with about four AND gates and
four Exclusive-OR gates but a memory chip programmed like this would
also work:

#(0 1 2 3 1 2 3 4 2 3 4 5 3 4 5 6) at: ((a1 * 8) + (a0 * 4) + (b1 * 2) +
b0)

So one way to implement logic circuits would be to use Read-Only Memory
chips (ROMs), but these are "programmed" at the factory by designing a
special layer to be used when manufacturing. That takes many weeks and
is very expensive. An alternative is to use Programmable ROMs (PROMs)
which can be inserted into a low cost device and have their contents
changed by blowing out tiny fuses. There is no way to "unblow" a fuse so
if you make a mistake you have to throw the device away and use another
one.

PROMs were used on the Xerox Alto computer and the disk controller for
the Apple II, among many other designs of the 1970s.

The Erasable PROM (EPROM) allowed you to reuse the same device since you
could expose it to ultraviolet light to reset it to the blank state.
These devices were larger and slower than PROMs. The only example I know
of an EPROM being use as logic was for the video signals generator on my
own Merlin 2 design.

If you look at any of these memory devices, you will see a decoder
circuit which takes the address and outputs a separate line of each
possible input combinations. If you have 9 address lines on a small
PROM, for example, then the decoder will activate one of 512 lines.
These lines are connected to the data lines via transistors and fuses.
The decoder part is equivalent to 512 AND circuits of 9 inputs each
while the second section is equivalent to 8 (if that is how many data
outputs this PROM has) OR circuits with 512 inputs each where some
(actually, most) of these inputs can be disabled by the programming
device.

A very reasonable alternative is to have a smaller number of ANDs and
let their inputs be programmable as well. This is known as a
Programmable Logic Array (PLA) and like a ROM there is a version
"programmed" in the factory (often included as part of a larger design)
and versions which can be programemd "in the field" using a low cost
device. Yet another variation has programmable inputs for the ANDs but
fixed connections for the ORs and these Programmable Array Logic (PAL)
circuits became far more popular - eight of them were used in the
original Mac, for example.

An entirely different kind of user defined devices are the Gate Arrays
(GA, or Uncommited Logic Array, ULA, as it was known in the UK). Like
ROMs they have several layers which are exactly the same for all clients
and an additional layer which is defined for each design. This makes it
far cheaper than a chip where all layers are unique to a single design.
Unlike the ROM, however, the fixed layers of the GA have a large number
of simple gates. While with a ROM, PROM or even PAL you had essentially
a single combinational block per integrated circuit, with the GA you
could have many such blocks and connect them together. You could even
implement memory circuits and have sequential designs as well.

So we get to the Field Programmable Gate Array (FPGA) invented by Xilinx
in 1984. Instead of using a custom layer to connect the blocks like in
the GA, the FPGA had a switching circuit similar to the old telephone
system where any block could be connected to any other block. And these
blocks were 16 by 1 memory circuits (known as Look Up Tables, LUTs),
which allowed any of 64 thousand possible logic functions of 4 inputs to
be programmed. In addition, each block could have an optional flip-flop
(1 bit memory circuit) connected to its output for sequential designs.

Meanwhile, the PALs grew and grew and become known as Complex
Programmable Devices (CPLDs). These normally keep their programming
(using Flash memory technology these days) when the power is out and are
used for the smaller designs while FPGAs are used for large designs.
Some FPGAs also keep their programming but most of them have to be
reprogrammed every time you turn them one.

The first major change in FPGAs was allowing the LUT to be used as an
actual 16 by 1 memory in a design, which is a 16 fold increase in
density compared to using just the flip-flops. With this change it
started to become practical to put very small processor designs into a
FPGA. By the end of 1990s actual memory blocks started to be added to
FPGAs and then multiplier circuits. This made them particularly useful
for digital signal processing (DSP) applications and made them even
nicer for processor designs. As FPGAs got larger and larger we went from
needing many FPGAs to implement a single processor to being able to put
many processors into a single FPGA. Around the end of 2000 there was a
dramatic drop in prices for low end FPGAs due to intense competition
between Xilinx and Altera and they made FPGAs practical for end products
rather than just for prototypes.

I hope this helps give you a better idea of where these things came
from. Perhaps I should send this to the list.

Cheers,
-- Jecel