ece1756_lecture6_part2_2026_fpga_arch_styles

Overview

Vaughn Betz compares four FPGA logic-element styles, from fuse-programmed PROMs and PALs to SRAM lookup tables and mux-based cells, showing how area scaling, static power, and programmable-routing costs shaped their adoption. He then examines hierarchical routing, crossbar scaling, and Rent's rule, explaining why routing capacity and long wires make hierarchical FPGAs difficult to scale for designs with poor locality.

Key takeaways

PROM area scales as 2^N times M, while PAL area is roughly proportional to N times M; PALs therefore support larger functions before input count becomes prohibitive.
A K-input LUT implements any K-input Boolean function, but both its SRAM storage and mux circuitry grow as 2^K, so larger functions must be composed from multiple LUTs.
Mux-based logic cells use fewer logic resources as input count grows linearly, but their extra routing ports can cost more than the logic saved.
A full crossbar with n inputs and m outputs requires O(nm) switching resources; multi-stage networks reduce area but introduce blocking and more complicated routing decisions.
Rent's rule, T = kG^P, links logic size to terminal demand: pipelines can have P near 0, two-dimensional arrays near 0.5, and random control logic around 0.75.
Hierarchical FPGA routing designed for P = 0.5 may fail on P = 0.75 designs or force them to use only half the chip, while long upper-level wires add delay and can make nearby blocks communicate inefficiently.

Chapters

0:00 PROMs: The First Programmable Logic Architecture

An N-bit decoder activates one of 2^N word lines, selecting the programmed output pattern.
Fuse connections between word and bit lines encode output values; a blown fuse leaves a weak pull-up unopposed.
A PROM acts as a lookup table, but its dominant storage cost scales as 2^N times M outputs.

8:10 PALs Replace PROM Truth Tables with AND-OR Arrays

Programmable Array Logic, or PAL, uses input signals and their complements to form programmable AND terms followed by OR gates.
A macro block can include a flip-flop, an output bypass multiplexer, and feedback to support sequential logic.
PAL area scales roughly with N inputs times M outputs, better than PROM's exponential dependence on input count, though available product terms limit which functions fit.

8:45 Wired-OR Gates Make PAL Product Terms Compact

De Morgan's theorem lets an AND function be implemented using an OR of complemented inputs followed by inversion.
A wired-OR structure can implement a wide gate with about N+1 transistors, using pull-down transistors and a weak pull-up.
When any pull-down transistor is on, the circuit has a direct power-to-ground path, creating unacceptable static power at modern transistor counts.

14:50 CMOS Power Concerns End the Wired-OR Era

The wired-OR's static current is not ordinary transistor leakage: an active pull-down and weak pull-up conduct simultaneously.
Billions of such circuits would consume excessive power, making this style unsuitable as a dominant modern logic element.
CMOS NAND gates can still implement related logic, but wired-OR PAL structures are no longer the prevailing approach.

20:00 Xilinx LUTs Store Truth Tables in SRAM

The lookup table, or LUT, was introduced by Xilinx in 1984; Ross Freeman is associated with its key patent.
A K-input LUT uses a 2^K-to-1 multiplexer with each data input driven by an SRAM configuration bit.
A bypass multiplexer and flip-flop let a LUT output be either combinational or registered.

23:40 LUT Capacity Grows Exponentially with Input Count

A K-input LUT needs 2^K SRAM bits, and its multiplexer circuitry also grows exponentially with K.
Practical LUTs therefore have only a modest number of inputs, commonly around four to seven rather than dozens.
Each LUT can implement any function of its K inputs, simplifying CAD checks, while larger functions require connecting multiple LUTs.

27:00 Mux-Based Logic Cells Trade LUT Inputs for Routing Ports

Actel, now part of Microchip, used mux-based FPGA logic in which mux data inputs connect to signals rather than fixed SRAM truth-table bits.
A two-level mux structure can compute a three-input XOR by using two signals as select inputs and routing a signal or its complement to each data input.
Mux trees scale linearly in their number of inputs, but their many signal connections consume costly programmable-routing ports, and many functions cannot use every input effectively.

42:00 Why FPGA Routing Needs More Than Logic Cells

No logic element scales well enough to handle arbitrarily large functions on its own, so an FPGA must connect many smaller elements.
Programmable routing is a major architectural resource and can occupy more area than the logic elements it connects.
The next design challenge is building routing networks that scale without requiring a full connection from every block to every other block.

43:40 Altera MAX 7000: Hierarchical PAL Blocks

The Altera MAX 7000 is an example of an early hierarchical FPGA built from multiple PAL-style AND-OR blocks.
A switch network connects smaller logic blocks so they can collectively implement larger functions.
A full crossbar offers unrestricted connectivity, but its cost grows with the product of its input and output counts.

47:00 Crossbar Area Grows as Inputs Times Outputs

A crossbar with n inputs and m outputs needs a programmable switch at each of the n-by-m intersections.
Building one multiplexer per output gives the same scaling: each mux selects among n inputs, and there are m outputs.
Crossbars are easy for CAD tools and do not block connections, but their quadratic growth makes large networks impractical.

50:00 Multi-Stage Networks Reduce Large-Scale Routing Cost

Larger FPGAs replace a single crossbar with several levels of switch networks.
Multi-stage networks can bring area closer to proportional to the number of inputs plus outputs, rather than their product.
The savings come with trade-offs: routing can be blocked, and CAD tools must handle more complex connectivity.

54:40 Hierarchical Routing Groups Logic into Wire Levels

A hierarchical network connects nearby logic blocks through level-one wires, then uses higher-level wires to link groups of blocks.
Examples include Andrew DeHon's academic architecture, older Altera devices such as Apex, and designs from Flex Logix.
The hierarchy can be irregular because each level requires its own layout pattern rather than repeating one identical tile.

58:00 Partitioning Maps RTL Hierarchy onto FPGA Blocks

Partitioners divide a design into groups while trying to minimize the signals crossing between groups, enabling fast placement of logic elements.
RTL modules such as C1 and C2 instantiated by C3 can provide a natural, though imperfect, hierarchy for mapping.
Hierarchical designs often keep internal signals inside modules, so higher-level groups need fewer interconnects than the sum of their lower-level groups.

1:04:00 Rent's Rule Estimates Interconnect Demand

Rent's rule models a logic block's terminals, meaning its inputs and outputs, as T = k times G^P, where G is the amount of logic.
The Rent exponent P lies between zero and one and varies by circuit; it estimates how quickly interconnect demand grows with design size.
The rule is an empirically observed CAD model used to estimate routing needs, not a universal law of nature.

1:09:00 Pipelines and Arrays Illustrate Good Routing Locality

A one-dimensional processing chain can have P near zero: adding stages increases logic while the overall design still has one input and one output.
A two-dimensional SRAM array has P near 0.5 because its row and column terminals grow roughly with the square root of its cell count.
Nvidia Blackwell tensor units use systolic-array structures with similar two-dimensional data flow and roughly 0.5-style locality; random control logic can approach P = 0.75.

1:14:00 Hierarchical FPGA Wiring Assumes a Rent Exponent

An FPGA architect chooses how many wires to allocate at each hierarchy level, effectively assuming a target interconnect-growth rate.
With an architectural exponent of 0.5 and two base wires, the lecture's example grows to about three wires at the next level and four at the following level.
Designs whose actual Rent exponent is higher can demand more wires than the architecture provides, causing routing failure.

1:22:00 Poor Locality Can Force Designs to Use Half a Chip

For a design with P = 0.75, the example's demand rises from two base wires to about 3.4 and then 5.7, exceeding the architecture's allocation of four at the third level.
A CAD tool can sometimes resolve the shortage by spreading logic across more of the FPGA, but the example requires using only 50% of the available blocks.
Building in enough wiring for every high-exponent design would raise chip cost, while an architecture tuned for P = 0.5 may fail or waste capacity on less-local designs.

1:27:00 Long Hierarchical Wires Add Delay and Miss Local Connections

Top-level hierarchical wires span large distances and have high resistance and capacitance, making them slow even when routed on thicker upper metal layers.
Repeaters can improve long-wire delay, but add buffers and cost, including extra circuitry for programmable bidirectional routes.
Physically adjacent logic blocks can be far apart in the routing hierarchy, forcing communication through several long stages and wasting potential speed and area.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Vaughn Betz.