FPGA
Understanding FPGA LUTs Through C Arrays
Jan Merle
· 8 min read
As an embedded developer with a software background, as opposed to an electronics background, I sometimes struggle with simple hardware concepts. So it’s always a nice surprise if a hardware concept actually maps to a software concept, instead of just looking like it does (which happens far too often). One such concept is the FPGA LUT. A LUT, short for lookup table, is what a field programmable gate array (FPGA) uses for the “programmable gate” part of its name. In short, it is a piece of hardware inside the FPGA that can be “programmed”1 to compute any conceivable boolean function with N inputs. For example, a LUT2 can be programmed to act like an and-gate, an or-gate, or any of the 14 remaining two-input boolean functions. And exactly how it does that was the surprising thing for me: the LUT is just a block of random access memory (RAM). And that is something I’m familiar with.
So, instead of explaining how a LUT works in terms of its use inside an FPGA, let’s try to make a logic gate out of memory in C, before coming back to how the real thing works and how it differs from our handmade LUT. Consider the following C array:2
int and2[4] = { 0, 0, 0, 1 };If we squint really hard, this array becomes a truth table:
// Index x1 x0 | x1 and x0
int and2[4] = { // --------|----------
0, // 0 (0b00) --> 0 0 | 0
0, // 1 (0b01) --> 0 1 | 0
0, // 2 (0b10) --> 1 0 | 0
1, // 3 (0b11) --> 1 1 | 1
};By treating the bits of the array index individually as the input columns of the truth table, we can see that this array fully describes the boolean function and. Computing the function then becomes a matter of looking up the value stored at the index formed by the input variables, hence the name lookup table.
// Example: Compute the value of 1 & 0
unsigned int x1 = 1;
unsigned int x0 = 0;
int y = and2[x1 << 1 | x0 << 0]; // y == 0Let’s examine what happened here: first we shifted the input variables up to their corresponding bit of the array index, or’ed them together yielding the value 2, and finally used that value to index into the LUT array. The value stored there is 0, which is the correct result for 1 & 0. You can try this yourself with the other input combinations.
Here’s an ASCII diagram showing how the inputs and output correspond to the and-gate:
y = and2[0b10];
| ||
| || _________
| || | |
| ||___|x0 |
| | | & y|___
| |____|x1 | |
| |_________| |
| |
|_____________________________|To compute the other 15 two-input boolean functions, we can just use their corresponding truth tables instead. Functions with more inputs require larger arrays, but the idea is the same:
// Index x2 x1 x0 | x2 or x1 or x0
int or3[8] = { // ------------|---------------
0, // 0 (0b000) --> 0 0 0 | 0
1, // 1 (0b001) --> 0 0 1 | 1
1, // 2 (0b010) --> 0 1 0 | 1
1, // 3 (0b011) --> 0 1 1 | 1
1, // 4 (0b100) --> 1 0 0 | 1
1, // 5 (0b101) --> 1 0 1 | 1
1, // 6 (0b110) --> 1 1 0 | 1
1, // 7 (0b111) --> 1 1 1 | 1
};In general, the size of the array is 2^N, where N is the number of inputs.
Let’s compare this to how it really works in an FPGA. Without going into too much detail about the actual implementation, there are a few differences compared to our simplified model. First of all, a real LUT doesn’t waste memory by using 32 bits (that’s how large int is on my machine) for storing a single boolean value. Instead, each memory cell of the LUT stores only one bit, since that’s all we need to represent a truth value.
The next difference lies less in the implementation of the LUT itself (after all it’s just memory in both cases) than in how an FPGA and a CPU work. In an FPGA, the LUT behaves like a real gate would, constantly yielding an output that only depends on its inputs. Our software LUT on the other hand must be actively read by the CPU to yield a value.
Since I’ve used array variables to represent the LUTs in C, I could potentially modify them to compute a different function later (although I would choose a more generic name in that case). An FPGA usually configures the memory cells of its LUTs at power-on from an external source, after which they stay fixed until the next reset. So instead of a variable, think of a real LUT as a constant.3
The last thing we haven’t discussed yet is how the memory of the LUT is accessed. I won’t go into how this is done by a CPU, but in a LUT, something called a multiplexer is used. In the case of a LUT2, this is a 4-to-1 multiplexer that uses a two-bit input address (composed of its two input bits) to select one of the 4 bits stored in the LUT. Here’s what this looks like schematically for a LUT2 configured as &:
0 1 2 3
_______________
| | | | |
| 0 | 0 | 0 | 1 | RAM
|___|___|___|___|
| | | |
x1 x0 00 01 10 11
| | ________|___|___|___|________
| |__\ /
|_______\ 4-to-1 multiplexer /
\_______________________/
|
yThe neat thing about using a C array as a LUT is that it abstracts away the actual addressing of the truth values. But now that we can see how this works in a real LUT, we can make it explicit in our code. Conceptually, the closest thing to an N-to-1 multiplexer in C (besides arrays) is the switch-case statement, even though its implementation wildly differs.
unsigned int x1 = 1;
unsigned int x0 = 0;
int y;
switch(x1 << 1 | x0 << 0) {
case 0b00: y = and2[0]; break;
case 0b01: y = and2[1]; break;
case 0b10: y = and2[2]; break;
case 0b11: y = and2[3]; break;
}Earlier, I showed a LUT with three inputs that uses twice as much memory as a LUT with two inputs. This approach does not scale well: a LUT20, for example, would already require 2^20 bits (128 KiB) of memory. As very large LUTs like this are rarely needed, what hardware vendors usually do is to build a larger LUT by combining two smaller LUTs, using another multiplexer.4
___________ |\
| LUT2 | | \
x0 ___|x0 | | \
| y|___ | \
x1 ___|x1 | | | |
|___________| |___1| 2 |
___________ | to |___ y
| LUT2 | ___0| 1 |
x0 ___|x0 | | | |
| y|___| | /
x1 ___|x1 | | /
|___________| | /|
|/ |
x2By now we have all the tools to write the equivalent in C: two arrays for the LUT2s, and a switch statement to combine them. However, I have chosen to use a ternary expression instead, as it maps even better to the concept of a 2-to-1 multiplexer (an if statement would be possible too, but less concise).
// Index x1 x0 | x1 or x0
int or3_low[4] = { // --------|---------
0, // 0 (0b00) --> 0 0 | 0
1, // 1 (0b01) --> 0 1 | 1
1, // 2 (0b10) --> 1 0 | 1
1, // 3 (0b11) --> 1 1 | 1
}; //
// x1 x0 | always 1
int or3_high[4] = { // --------|---------
1, // 0 (0b00) --> 0 0 | 1
1, // 1 (0b01) --> 0 1 | 1
1, // 2 (0b10) --> 1 0 | 1
1, // 3 (0b11) --> 1 1 | 1
};
unsigned int x2 = 1;
unsigned int x1 = 1;
unsigned int x0 = 0;
int y = x2 ? or3_high[x1 << 1 | x0 << 0]
: or3_low [x1 << 1 | x0 << 0];Note how neither table describes the intended function on its own, but combined, they exactly match the truth table of or3 shown earlier.
We’ve seen that even after drilling down a layer into the LUT implementation, the array analogy still stands semantically. The array just hides the addressing that the multiplexer or its switch-case analog makes explicit.
I hope this article helped build a mental model of how an FPGA computes boolean functions. But if I managed to get you interested in FPGAs in general, it is worth pointing out that the LUT is only one of several components that make up an FPGA. Also of note are: routing, which is how connections between LUTs, multiplexers and other components are made configurable, and flip-flops, which are the key to holding state in an FPGA. Nandland has a nice introduction to the latter and other FPGA topics (including LUTs). If you’d rather learn to actually make hardware designs for an FPGA, the site also has introductions to hardware description languages.5
Footnotes
-
You will also often hear “configurable” instead of “programmable” in this context. I’m using the two terms interchangeably here. ↩
-
The code listings shown here are deliberately kept short and to the point in order to illustrate a concept without distractions. They should not be taken as examples of good C code. ↩
-
On some FPGAs, this is not quite true, as they allow partial reconfiguration after the fact, or can use the LUTs’ memory cells directly as RAM. ↩
-
For example, the LUT6 on a Xilinx 7 Series FPGA is a combination of two LUT5s and a multiplexer driven by the 6th input. See UG953. Here, the hardware vendor built this combined circuit directly in silicon, but the same technique can be used to combine a dedicated multiplexer and two LUTs with the same number of inputs, by programming the FPGA accordingly. ↩
-
One is about Verilog, the other about VHDL. Note that neither tutorial concerns itself with running FPGA designs on real hardware, though the author seems to have resources for that too. ↩