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:
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
hardware@lists.squeakfoundation.org