An FPGA can be seen (visually at least) as a matrix of cells. Each cell has a LUT (look-up table) inside, implemented with SRAM and MUX.
Why does the size of such a LUT (and hence of the SRAM) need to be kept small in FPGAs (usually less than 10 input bits)?
Please correct me if I am saying something wrong.
The physical size of a binary LUT is exponential in its number of inputs. In particular, every time you add another input, the size doubles. To go from 10 inputs to 20, the size of each LUT would go up by a factor of 1024, and you'd barely be able to fit any of them onto the FPGA anymore.
You don't typically see LUTs with more than 6 inputs on FPGAs, as this already requires 64 bits of storage per LUT. It's much more efficient to compose circuits from multiple LUTs than to put everything into a single huge LUT.
As a simple example, let's say that you want to build a 16-input AND gate on an FPGA.
If the FPGA has 16-input LUTs, you can do it in a single LUT, which would contain 2^16 = 65536 SRAM cells.
If, however, the FPGA only has 4-input LUTs, you'll need to build a LUT cascade. Each LUT, when configured as an AND gate, compresses 4 inputs down to 1 output. To get from our total of 16 inputs down to 1 output, we need two layers of compression. This requires 5 LUTs in total. Each 4-input LUT consists of 2^4 = 16 SRAM cells, so in total, our 16-input AND gate requires 5*16 = 80 SRAM cells in this case.
By shrinking our LUT size from 16 inputs to 4, we were able to shrink the silicon area used by our circuit from 65536 SRAM cells down to just 80, even though we used more of those smaller LUTs.
Additionally, FPGAs have mechanisms to combine multiple smaller LUTs into larger ones if a circuit really requires big LUTs (for example to store constant data). Modern Xilinx FPGAs have 5-input LUTs, but can internally connect multiple of them together to form LUTs with up to 8 inputs within a single logic slice (at least if I remember this correctly). Bigger ones can be created across multiple slices, too, by using the FPGA's routing fabric.
FPGAs are designed to be as general purpose as possible. Considering that each LUT has N inputs and 1 output, you want those LUTs to be sized such that there is as little wasted space as possible.
The designers of the architecture of the FPGA do some analysis of common functionality that is implemented in their FPGAs and look at the average size of LUTs needed for those designs.
If across all these different designs, you find that most LUTs tend to be 4 input or smaller, with maybe a few 5 or 6 LUTs as well, then you would target your architecture towards LUT4s because this results in a good space to utilisation ratio.
If instead you made all the LUTs larger then you're going have more unused space in the design. For each extra bit you double the size of the LUT, so going from say LUT4 to say LUT10 wout be a 64x increase in size, most of which would be unutilised because the functions using them are mostly quite small (remember they analyse this across many designs).
Instead of making all the LUTs larger, they look at playing clever tricks to make variable sized tables. You make a compound block with two LUT4s, each with independent inputs, and outputs. You then add one additional multiplexer for the first output so that it can select from either LUT using one additional input. Such a block can still be used as two separate LUT4s for maximum flexibility in small functions. But by joining both sets of 4 inputs together and using the multiplexer select as a fifth bit, you can also use the block as a single LUT5 with very little extra space consumed and almost no speed penalty due to compactness of the two LUTs.
The compound approach can be extended to include adders, carry chains and larger LUT muxing (e.g. LUT6 which can still be split to smaller LUTs is quite common).
For really big functions such as memories, they then add a few sparsely place block RAMs. These sacrifice a large number of LUTs in favour of a single memory. But you still choose carefully how many of each are in each device to get a good tradeoff for maximum flexibility.
Another consideration is efficiency. Consider a 4-input LUT - it uses 16 bits. Two 4-bit LUTs require 32 bits. If your LUTs have a minimum size of 8 inputs, for example, you can produce the same logic functions as two smaller lUTs, but it will require 256 bits, and a waste of 87% of the chip area. General purpose logic typically has a lot of small-scale logic variables, so small LUTs are the most efficient use of real estate.
