1CprE / ComS 583Reconfigurable ComputingProf. Joseph ZambrenoDepartment of Electrical and Computer EngineeringIowa State UniversityLecture #3 – FPGA BasicsCprE 583 – Reconfigurable ComputingAugust 29, 2006 Lect-03.2Quick Points• HW #1 is out• Due Thursday, September 7 (12pm)• Submission via WebCT• Possible strategiesAssigned DueEffort LevelStandard Preferred CprE 583 – Reconfigurable ComputingAugust 29, 2006 Lect-03.3Recap• FPGAs – spatial computation• CPU – temporal computation• FPGAs are by their nature more computationally “dense” than CPU• In terms of number of computations / time / area• Can be quantitatively measured and compared• Capacity, cost, ease of programming still important issues• Numerous challenges to reconfigurationCprE 583 – Reconfigurable ComputingAugust 29, 2006 Lect-03.4Outline• Recap• FPGA Taxonomy• Lookup Tables and Digital Logic• Interconnect / Routing Structures• FPGA Architectural IssuesCprE 583 – Reconfigurable ComputingAugust 29, 2006 Lect-03.5FPGA Taxonomy• Programming technology – how is the FPGA programmed? Where does it store configuration bits?• SRAM• Anti-fuse• EPROM• Flash memory (EEPROM)• Logic cell architecture – what is the granularity of configurable component? Tradeoff between complexity and versitility• Transistors• Gates• PAL/PLAs• LUTs• CPUs• Interconnect architecture – how do the logic cells communicate?• Tiled• Hierarchical• LocalCprE 583 – Reconfigurable ComputingAugust 29, 2006 Lect-03.6Anti-Fuse Technology• Dielectric that prevents current flow• Applying a voltage melts the dielectric• One time programmable – not really reconfigurable computing2CprE 583 – Reconfigurable ComputingAugust 29, 2006 Lect-03.7Anti-Fuse Technology (cont.)• Negligible programming overhead• Fast routing• Nonvolatile (hold data after power off)• High level of security:• No bitstream can be intercepted in the field• Need a Scanning Electron Microscope (SEM) to figure out the anti-fuse states©ActelCprE 583 – Reconfigurable ComputingAugust 29, 2006 Lect-03.8E(E)PROM Technology• To program a transistor, a voltage differential between the access/floating gates accelerates electrons from the source fastenough to travel across the insulator to the floating gate• Electrons prevent the access gate from closing• EPROM – Erasable Programmable Read-Only Memory• Nonvolatile• Can be erased using UV light•EEPROM – Electrically Erasable Programmable Read-Only Memory• Removes the electrons by reversing the voltage differential• Limited number of erases possible• Precursor to Flash technologyCprE 583 – Reconfigurable ComputingAugust 29, 2006 Lect-03.9Flash / EEPROM Devices• Migrated from early PLD technology• Traditionally based on AND/OR architecture• High ratio of logic-to-registers• Future of Flash devices?• Logic elements (LUTs and flip flops)• Segmented routing• Low logic to register ratioActel ProASIC Plus logic cellCprE 583 – Reconfigurable ComputingAugust 29, 2006 Lect-03.10SRAM Technology• SRAM – Static Random Access Memory• SRAM cells are larger (6 transistors) than anti-fuse or EEPROM• Slower• Less computational power per λ2• SRAM bits can be programmed many timesCprE 583 – Reconfigurable ComputingAugust 29, 2006 Lect-03.11Which Devices to Study?• SRAM – ~95%, Flash/Anti-fuse – ~5%CprE 583 – Reconfigurable ComputingAugust 29, 2006 Lect-03.12Lookup Tables (LUTs)• What is a Lookup Table (LUT)?• In most generic terms, a pre-loaded memory• Great way of implementing some function without calculation – a cheat sheetDataAddrR_WQint table[256] = {1,7,8,9,…14};int Q, addr;...Q = table[addr];Q7: What is the answer to life, the universe, and everything?Answer Key...A(Q7) = 423CprE 583 – Reconfigurable ComputingAugust 29, 2006 Lect-03.13LUTs and Digital Logiccarrylogick-LUTDFFI1 I2 … IkCoutCinOUT• Each k-LUT operates on k one-bit inputs• Output is one data bit• Can perform any Boolean function of k inputsCprE 583 – Reconfigurable ComputingAugust 29, 2006 Lect-03.14LUTs and Digital Logic (cont.)• k inputs Æ 2kpossible input values• k-LUT corresponds to 2kx 1 bit memory• How many different functions?• Two-input (A1,A2) case• F(A1,A2) = {0, A1nor A2, Ā1and A2, Ā1, A1and Ā2, Ā2, A1xor A2, A1nand A2, A1and A2, A1xnor A2, A2, Ā1or A2, A1, A1or Ā2, A1or A2, 1} = 16 different possibilities• What to store in the LUT?0 00 11 01 1A1A200000100010100211003001041010501106111070001810019010110110111001112101113011114111115CprE 583 – Reconfigurable ComputingAugust 29, 2006 Lect-03.15LUTs and Digital Logic• F(input) can be 0 or 1 independently for each of the 2kbits• 22kpossible functions• Not all patterns are unique (k! permutations of the inputs)• Approximately 22k/ k! unique functions• Is this efficient?• How to select k value?0 00 11 01 1A1A200000100010100211003001041010501106111070001810019010110110111001112101113011114111115CprE 583 – Reconfigurable ComputingAugust 29, 2006 Lect-03.16LUT Mapping• How many gates in a 2-LUT + flip-flop?0 00 11 01 1A1A2x0x1x2x3fDFF00.511.5~8DQQ’RS4CprE 583 – Reconfigurable ComputingAugust 29, 2006 Lect-03.17LUT Mapping (cont.)• Implement the following logic function with k-LUTs, for k={2, 3, 4}:F = A0A1A3+ A1A2Ā3+ Ā0 Ā1 Ā2A0A3A2A3A1A0A2A1FA0A1A2A3FA0A2A3FA0A2A1CprE 583 – Reconfigurable ComputingAugust 29, 2006 Lect-03.18Logic Block Granularity• Each k-LUT requires 2kconfiguration bits:• The 2-LUT implementation requires 22x 7 = 28 bits • The 3-LUT needs 23x 3 = 24 bits• The 4-LUT needs just 24x 1 = 16 bits• Using configuration bits as area measure (area cost), the 4-LUT implementation achieves minimum logic area4CprE 583 – Reconfigurable ComputingAugust 29, 2006 Lect-03.19Interconnect• Problem:• Thousands of operators producing results• Each taking as outputs the results of other bit operators• Initial assumptions – have to connect them all simultaneouslyCprE 583 – Reconfigurable ComputingAugust 29, 2006 Lect-03.20Interconnect Design Issues• Flexibility – route anything (within reason?)• Bisection bandwidth• Simultaneous routes• Area• Bisection bandwidth• Switches• Delay (and Power)• Switches in path• Wire length• Routability – difficulty of finding a routeCprE 583 – Reconfigurable ComputingAugust 29, 2006 Lect-03.21General