FPGA Paradiso

"All things created have an order in themselves, and this begets the form that lets the universe resemble God”
— "Paradiso", Dante

FPGAs are a rabbit hole that you do not climb out of. In this sense, they are a portal to a whole new world of computing. A world where you can bend your ideas at will. A world where you can build worlds upon worlds. ANd those who go exploring might never come back.

I am being a bit fecious here, but its ture. FPGAs have played a huge part in my life and guided a big part of my unddergrad education and graudte reuach experince. Without them my life would be very different and I wanted to sahre my journey with them.

Logic

One of the first intorducotry courses and electrical and compuer enginerng major at Geogria Tech takes is "Welcome to ECE 2020: Fundamentals of Digital Design". Makes sense; digial deigsn is a good mix of hardware, software, arhciture, and theory. After many goruling nights and cups of coffee, freshman revel in their acomplsihment that they can now understadn how one could deisgn a processor and write some MIPS assembly to run on it.

It is thought that the fundamental unit of all digital computing is logic gates. Logic gates take in several values of 0 or 1 and output a single value of 0 or 1. The most common logic gates are AND, OR, and NOT. They are different because each one outputs 0 or 1 based on different patterns of combinations of 0 or 1 in their input. The inputs and outputs that take in values of 0 or 1 are referred to as Boolean numbers (this will make talking about them easier). A 2-input AND gate takes in two Boolean inputs and outputs a single Boolean value. However, what makes an AND gate an AND gate is that it outputs 1 only when both inputs are 1. If either input is 0, the output is 0. A 2-input OR gate outputs 1 when either input is 1. A NOT gate is a 1-input gate; it is special in that it only takes one input and outputs the opposite value. If the input is 1, the output is 0. If the input is 0, the output is 1. The only other possible 1-input gate is a buffer where the output value is the same as the input value (logically and functionally speaking this seems useless but is in fact very useful for real physical implementations of these gates inside semiconductors). In general, we can build gates that take in any number of inputs and output a single value. Different gates are just different Boolean functions. By making this simple abstraction, we can then start to generalize a specialized gate like AND or OR into a more "general gate" or Boolean function.

It turns out that if you know the number of inputs of a Boolean function, you can start to fully write out all possible gates, or Boolean functions, that take in that number of inputs. We have mostly done this already for 1-input gates. The two main options for 1-input gates are the NOT gate and the buffer gate. Let's write out these gates. The taught way to do this is to use a truth table. A truth table is a table that lists all possible inputs for a given Boolean function and the output for each input. For a 1-input gate, there are only two possible inputs, 0 and 1. So we can write out the truth table for a 1-input gate as follows:

Input | Output
0     | ???
1     | ???

This represents all 1-input gates as I have made the outputs unknown. This is not a real gate but a generalization of all 1-input gates.

Now let's specialize this general "1-input gate" into a NOT gate.

NOT Gate
\--------------
Input | Output
0     | 1
1     | 0

And for completeness, let's write out the buffer gate.

Buffer Gate
\--------------
Input | Output
0     | 0
1     | 1

If you'll notice, I have not defined the gate where the output is always 0 for all inputs or the gate where the output is always 1 for all inputs. This is because these gates are also not very useful in a sense that they do not do anything in reaction to the input. For all practical purposes, we could replace these gates with a wire that is always 0 or 1. However, it is important to note that these gates do exist in the general sense of Boolean functions. By counting the NOT gate, the buffer, the always 0 gate, and the always 1 gate, we have 4 possible 1-input gates. Also, notice that if we want to represent a specific gate, we can just remember the output pattern for all inputs (sorted by the input values). For example, a NOT gate has the output pattern [1,0], the buffer gate has the output pattern [0,1], the always 0 gate has the output pattern [0,0], and the always 1 gate has the output pattern [1,1]. This is a very compact way to represent a gate under the assumption we know it's a 1-input gate.

This idea of gates as n-input Boolean functions is now starting to come together. However, it starts to show its usefulness once you look at 2-input gates. For 2-input gates, there are 4 possible inputs, 00, 01, 10, and 11. So we can write out the truth table for any 2-input gate as follows:

Input A | Input B | Output
0       | 0       | ???
0       | 1       | ???
1       | 0       | ???
1       | 1       | ???

We can specialize this general "2-input gate" into an AND gate.

AND Gate
\--------------------------------
Input A | Input B | Output
0       | 0       | 0
0       | 1       | 0
1       | 0       | 0
1       | 1       | 1

And to save space, this gate in the compact way mentioned earlier, we can just write out the output pattern for all inputs: [0,0,0,1].

We can also specialize this general "2-input gate" into an OR gate.

OR Gate
\--------------------------------
Input A | Input B | Output
0       | 0       | 0
0       | 1       | 1
1       | 0       | 1
1       | 1       | 1

And to save space, this gate in the compact way mentioned earlier, we can just write out the output pattern for all inputs: [0,1,1,1].

But let's say I want a specific unnamed 2-input gate with the following output pattern: [1,0,1,1]. I know that I can always reconstruct this gate into a complete truth table.

Input A | Input B | Output
0       | 0       | 1
0       | 1       | 0
1       | 0       | 1
1       | 1       | 1

This gate doesn't technically have a common name but is still just as valid and practical as an AND gate and can be implemented in a real circuit.

In fact, if we count the number of possible 2-input gates, there are 2^4=16 possible Boolean functions. Not all of them are practical, like the always-0 or always-1 gates, and not all are named and popular, as shown above. But as before, we can represent any 2-input gate as a list of 4 Boolean values that represent the pattern of that gate's output for all possible inputs.

Now why am I going on about this? In the ECE class, they present logic gates as these predefined set of constructs (basically: {AND, OR, NOT, Buffer, XOR, XNOR, NOR, NAND}) when in fact they are all generalizations of general n-input gates. This hides the fact that there are other 1-input, 2-input, and n-input gates that you can build as long as you know the output pattern for all possible inputs.

The Confusing Part

Before diving into any futher discussion about FPGAs, it's essential to differentiate between two types of the usage of thw word gates: the gates we aim to represent and the gates used in constructing the hardware we are using. This will also get to the core of why an FPGA is.

Gates in user's design are the gates that you're trying to implement when mapping your deisgn to an FPGA. For example, a student might deisgn a CPU and in that design there are many gates and other comtnts that have to do with the CPU deisgn. These gates are the ones that the user is trying to implement and are not tied to any specifc hardware or pahycal gates. These gates are just a abstraction of the user's design.

Gates in hardware are phsycally built in the physcal harwdare that you are using. In an FPGA, you don't design or define these gates; they are part of the FPGA's internal architecture. Their job is to be flexible enough to mimic the behavior of the User-Defined Logic Gates you're trying to implement.

FPGA's Trick

In reality, an FPGA is realy playing a neat tirck. It is using many phycal gates in hardware to emualte or behave as an abstact gate in your deisgn. You might ask why play this trick, if I have a gate in my deisgn and I want it in hardware, just make the hardware gate the same. You have now reached the core of what an FPGA is. An FPGA is a hardware device that can be reprogrammed to be any gate. If I pshycal make a gate in a chip the same as in my deisgn, its there permenaly until I make a new chip. However, if I use an FPGA, I can reprogram the FPGA to be any gate I want. Reprorgrmaming a chip is sginifcantly easier than making a new chip. Making a new chip can take months and cost a lot of money (to pay the people to design it and make it) while reporamming an FPGA can be done in a few seconds and only cost the price of the FPGA when you first bought it (I lfet out any nusainces of FPGAs but the fact that they are way chaper and whay afdcter to develop with is very much true).

In the end the price you pay for this flexiblity is that the FPGA needs more physcal hardware. To be abel to pretend to be any gate and also chnage what that gate is, you need many pashycal gates to acomplsih this.

LUTS

Now that we have cleared up the weird absaction that FPGAs are, lets expand on this ideas of n-input Boolean functions.

Is there a way to build a block that I can reprogram abritrialy to be any n-input gate as long as I know the output pattern for all possible inputs?

Well the answer is simple: we store the output pattern given by the user and then look-up the correct output pattern when the inputs are given. This kind of block is called a look-up table (LUT). A LUT is a block that takes in n boolean inputs and outputs a single boolean value. The LUT stores the output pattern for all possible inputs. When the LUT recives an input, it looks up the output pattern for that input and outputs the correct value. This is a very simple block that can be used to build any user defined n-input gate.

The LUT is one of the fundemental building blocks of an FPGA.