IEEE Circuits and Systems Magazine - Q2 2021 - 9

of a 4-LUT using pass-transistor logic. In addition to the
output buffer, an internal buffering stage (shown between
the second and third stages of the LUT in Fig. 4(a)) is typically
implemented to mitigate the quadratic increase in
delay when passing through a chain of pass-transistors.
The sizing of the LUT's pass-transistors and the internal/
output buffers is carefully tuned to achieve the best areadelay
product. Classic FPGA literature [20] defines the
basic logic element (BLE) as a K-LUT coupled with an output
register and bypassing 2:1 multiplexers as shown in
Fig. 4(c). Thus, a BLE can either implement just a flip-flop
(FF) or a K-LUT with registered or unregistered output.
As illustrated in Fig. 4(d), BLEs are typically clustered
in logic blocks (LBs), such that an LB contains N BLEs
along with local interconnect. The local interconnect in
the logic block consists of multiplexers between signal
sources (BLE outputs and logic block inputs) and destinations
(BLE inputs). These multiplexers are often arranged
to form a local full [21] or partial [22] crossbar.
At the circuit level, these multiplexers are usually built
as two levels of pass transistors, followed by a two-stage
buffer as shown in Fig. 4(b); this is the most efficient circuit
design for FPGA multiplexers in most cases [23].
Fig. 4(d) also shows the switch and connection block
multiplexers forming the programmable routing that allows
logic blocks to connect to each other; this routing is
discussed in detail in Section III-B.
Over the years, the size of both LUTs (K) and LBs
(N) have gradually increased as device logic capacity
has grown. As K increases, more functionality can be
packed into a single LUT, reducing not only the number
of LUTs needed but also the number of logic levels on
the critical path, which increases performance. In addition,
the demand for inter-LB routing decreases as more
connections are captured into the fast local interconnect
by increasing N. On the other hand, the area of
the LUT increases exponentially with K (due to the 2K
SRAM cells) and its speed degrades linearly (as the multiplexer
constitutes a chain of K pass transistors with
periodic buffering). If the LB local interconnect is implemented
as a crossbar, its size increases quadratically
and its speed degrades linearly with the number of BLEs
in the LB, N. Ahmed and Rose [24] empirically evaluated
these trade-offs and concluded that LUTs of size 4-6 and
LBs of size 3-10 BLEs offer the best area-delay product
for an FPGA architecture, with 4-LUTs leading to a better
area but 6-LUTs yielding a higher speed. Historically,
the first LUT-based FPGA from Xilinx, the XC2000 series
in 1984, had an LB that contained only two 3-LUTs (i.e.
,).
NK23
== LB size gradually increased over time
and by 1999, Xilinx's Virtex family included four 4-LUTs
and Altera's Apex 20K family included ten 4-LUTs in
each LB.
SECOND QUARTER 2021
The next major change in architecture came in 2003
from Altera, with the introduction of fracturable LUTs
in their Stratix II architecture [25]. Ahmed and Rose in
[24] showed that an LB with ten 6-LUTs achieved 14%
higher performance than a LB with ten 4-LUTs, but at a
17% higher area. Fracturable LUTs seek to combine the
best of both worlds, achieving the performance of a larger
LUT with the area-efficiency of smaller LUTs. A major
factor in the area increase with traditional 6-LUTs is under-utilization:
Lewis et al. found that 64% of the LUTs in
benchmark applications used fewer than 6 inputs, wasting
some of a 6-LUT's functionality [26]. A fracturable {K,
M}-LUT can be configured as a single LUT of size K or can
be fractured into two LUTs of size up to K - 1 that collectively
use no more than K + M distinct inputs. Fig. 5(a)
shows that a 6-LUT is internally composed of two 5-LUTs
plus a 2:1 multiplexer. Consequently, almost no circuitry
(only the red added output) is necessary to allow a 6-LUT
to instead operate as two 5-LUTs that share the same inputs.
However, requiring the two 5-LUTs to share all their
O2
A
B
C
D
E
F
(a)
G
H
A
B
C
D
E
F
(b)
Figure 5. 6-LUT fracturable into two 5-LUTs with (a) no additional
input ports, leading to 5 shared inputs (A-E) or (b) two
additional input ports and steering multiplexers,
only 2 shared inputs (C, D).
leading to
IEEE CIRCUITS AND SYSTEMS MAGAZINE
9
1
O2
O1
1
O1
6-LUT
1
6-LUT
5-LUT
5-LUT
5-LUT
5-LUT
IEEE Circuits and Systems Magazine - Q2 2021

Table of Contents for the Digital Edition of IEEE Circuits and Systems Magazine - Q2 2021
