Digital DesignCopyright © 2006Frank VahidECE 274 - Digital LogicBeyond the Book: FPGAs Lecture 23 – Underlying FPGA Implementation How does an FPGA work? How do we program the FGPA?Digital DesignCopyright © 2006Frank VahidECE 274 - Digital LogicFPGA Programmable IC Technology – FPGA Manufactured IC technologies Weeks to months to fabricate Large (hundred thousand to million dollar) initial costs Programmable ICs are pre-manufactured Can implement circuit today Just download bits into device Slower/bigger/more-power than manufactured ICs But get it today, and no fabrication costs Popular programmable IC – FPGA  "Field-programmable gate array" Developed late 1980s Programmable in secondsDigital DesignCopyright © 2006Frank VahidECE 274 - Digital Logic FPGA Internals: Lookup Tables (LUTs)F = x'y' + xyx0011y0101F10014x1 Mem.0123rda1a01yxDF1001 Basic idea: Memory can implement combinational logic e.g., 2-address memory can implement 2-input logic 1-bit wide memory – 1 function4x1 Mem.10010123rda1a01Dy=0x=0F=14x1 Mem.10010123rda1a01Dy=1x=0F=04x1 Mem.10010123rda1a01Dy=0x=1F=04x1 Mem.10010123rda1a01Dy=1x=1F=1Digital DesignCopyright © 2006Frank VahidECE 274 - Digital Logic FPGA Internals: Lookup Tables (LUTs)F = x'y' + xyG = xy'x0011y0101F1001G00104x2 Mem.100001100123rda1a01xyD1 D0FG What if we want two outputs? Use a 2-bit wide memory Such memory in FPGA known as Lookup Table (LUT)4x1 Mem.100001100123rda1a01D1y=0x=0F=14x1 Mem.100001100123rda1a01D1y=1x=0F=04x1 Mem.100001100123rda1a01D1y=0x=1F=04x1 Mem.100001100123rda1a01D1y=1x=1F=1D0G=0D0G=0D0G=1D0G=0Digital DesignCopyright © 2006Frank VahidkpswBeltWarnk00001111p00110011s01010101w00000010ECE 274 - Digital Logic FPGA Internals: Lookup Tables (LUTs) What if we have more inputs? Example: Seat-belt warning lightProgramming(seconds)Fab1-3 months8x 1 Mem.00000010DwIC01234567a2a1a0kpsDigital DesignCopyright © 2006Frank VahidECE 274 - Digital Logic FPGA Internals: Lookup Tables (LUTs) Lookup tables become inefficient for more inputs 3 inputs Æ 8 entries 8 inputs Æ 256 entries 16 inputs Æ 65,536 entries!kpsCircuit8x 1 Mem.00010Dw01267a2a1a0kpsw…Circuit8x 1 Mem.00010Dw012254255w…Circuit8x 1 Mem.00010Dw0126553465535w…cefhdgbaa7a6a5abca4a3a2defa1a0ghin1in0in3in2in5in4in7in6in9in8in10in11in12in13in14in15in1in0in3in2in5in4in7in6in9in8in10in11in12in13in14in15a14a13a11a12a10a8a9a7a5a6a4a3a2a1a0Digital DesignCopyright © 2006Frank VahidMap to 3-input LUTs5-input circuit, but 3-input LUTs availablekpstdwBeltWarn8x 1 Mem.00000010D01234567a2a1a0kpsxdt8x 1 Mem.01111111Dw01234567a2a1a0ECE 274 - Digital Logic FPGA Internals: Lookup Tables (LUTs) FPGAs thus have numerous small (3, 4, 5, or even 6-input) LUTs If circuit has more inputs, must partition circuit among LUTs Example: Extended seat-belt warning light systemPartition circuit into 3-input sub-circuitskpstdxwBeltWarn3 inputs1 outputx=kps'3 inputs1 outputw=x+t+dSub-circuits have only 3-inputs eachkps' x+t+dDigital DesignCopyright © 2006Frank VahidECE 274 - Digital LogicFPGA Internals: Lookup Tables (LUTs) Partitioning among smaller LUTs is more size efficient Example: 9-input circuitacbdfgFiehacbdfegih3x13x13x13x1F512x 1 Mem.8x 1 Mem.Original 9-input circuitPartitioned among 3x1 LUTsRequires only 4 3-input LUTs (8x1 memories) –much smaller than a 9-input LUT (512x1 memory)Digital DesignCopyright © 2006Frank Vahid8x 2 Mem.1001000000000000D0D101234567a2a1a0d1d00i1i08x2 Mem.0000100100000000D0D1d3d201234567a2a1a00i1 i0d0d1d2d3Sub-circuit has 2 inputs, 2 outputsSub-circuit has 2 inputs, 2 outputsECE 274 - Digital Logic FPGA Internals: Lookup Tables (LUTs) LUT typically has 2 (or more) outputs, not just one  Example: Mapping a 2x4 decoder to 3-input 2-output LUTsDigital DesignCopyright © 2006Frank VahidCLBSM SMSM SMCLBCLBCLBCLBCLBCLBCLBCLBRepresents channel with tens of wiresConnections for just one CLB shown, but all CLBsare obviously connected to channelsECE 274 - Digital LogicFPGA Internals: Overall Architecture Consists of hundreds or thousands of CLBs and switch matrices (SMs) CLB - LUT + additional components SM – configurable routing between CLB Arranged in regular pattern on a chipDigital DesignCopyright © 2006Frank VahidECE 274 - Digital LogicFPGA Internals: Programming an FPGA How do we program an FPGA? All configuration memory bits are connected as one big shift register Known as scan chain Shift in "bit file" of desired circuit8x 1 Mem.00000010D101234567a2a1a0kpdt8x 1 Mem.01111111Dw01234567a2a1a0Switch Matrix101101D0sxpinBit file contents for desired circuit: