1CprE / ComS 583Reconfigurable ComputingProf. Joseph ZambrenoDepartment of Electrical and Computer EngineeringIowa State UniversityLecture #9 – Logic Emulation TechnologyCprE 583 – Reconfigurable ComputingSeptember 19, 2006 Lect-09.2Recap –FPGA-Based Router (FPX)• FPX module contains two FPGAs• NID – network interface device• Performs data queuing• RAD – reprogrammable application device• Specialized control sequencesOSC100MHz10 MHzOSCSDRAM(backside)8Mbit ZBTSRAM8Mbit ZBTSRAMDeviceInterfaceNetworkNIDRADReprogrammableApplicationDeviceVirtex1000E fg680RAD/NID StatusSDRAM(backside)SRAMProgramRADReprogOC3 / OC12 / OC48 Linecard ConnectorEPROMNID62.5 MHzVRM: 1.8V SwitcherJTAGWUGS Switch Backplane ConnectorFPXWashU / ARLJuly, 2000JL / MROSCCprE 583 – Reconfigurable ComputingSeptember 19, 2006 Lect-09.3Recap – CAM-Based Packet Filtering• Source Address = 128.252.0.0 / 16 • Destination Address = 141.142.0.0 / 16• Source Port = Don’t Care• Destination Port = 50• Protocol = TCP (6)• Payload includes general SPAM (List 0)7103 3971Src IP (hex) =80FC0505Dest IP (hex) =8D8E0202SrcPort = 1000Dest Port =0050Proto= 06084072Src IP value =80FC0000Dest IP (hex) =8D8E0000SrcPort = 0000Dest Port =50Proto= 06Src IP (hex) =FFFF0000Dest IP (hex) =FFFF0000SrcPort = 0000Dest Port =FFFFProto= FFValueMask: 1=care0=don’t careIP PacketCon-ten t=01Con-ten t=01Con-tent=03DROP the packet : It matches the filterCprE 583 – Reconfigurable ComputingSeptember 19, 2006 Lect-09.4Recap – Classification ArchitectureCAM MASK [1]CAM VALUE [1]CAM MASK [2]CAM VALUE [2]CAM MASK [3]CAM VALUE [3]CAM MASK [N]CAM VALUE [N]Flow ID [1]112 bitsFlow ID [2]Flow ID [3]Flow ID [N]Flow ID. . .. . .. . .16 bits Value ComparatorsMask MatchersPriority EncoderResulting Flow IdentifierFlow ListSource Address Destination Address16 bitsPayload Match Bits Source Port Dest.Port Protocol - - CAM Table - -Bits in IP HeaderCprE 583 – Reconfigurable ComputingSeptember 19, 2006 Lect-09.5Outline• Recap• Multi-FPGA Systems• Network topologies• System software• Theoretical Limits• Example Systems• Application – Logic EmulationCprE 583 – Reconfigurable ComputingSeptember 19, 2006 Lect-09.6Coupling in a Reconfigurable SystemStandalone Processing UnitI/OInterfaceAttached Processing UnitWorkstationMemoryCachesCoprocessorCPUFU• Many places to put reconfigurable computing components• Most implementations involve multiple discrete devices• How should these devices be connected together?2CprE 583 – Reconfigurable ComputingSeptember 19, 2006 Lect-09.7Modern Multi-FPGA Systems• Large logic capacity• All projects end up pushing capacity limits• Large amount of on-board RAM• High speed and high density• To support genome, vision and pharmacological apps• High speed FPGA-FPGA connections• To make multiple FPGAs more like one big FPGA• Inter-chip connectivity an issue• Parallel computers in the traditional sense• Suitable for spatially parallel applications• Transmogrifier-4, BEE2CprE 583 – Reconfigurable ComputingSeptember 19, 2006 Lect-09.8Mesh Topology• Chips are connected in a nearest-neighbor pattern• Simplicity is key• Linear array is essentially a 1-dimensional meshA B CD E FG H ICprE 583 – Reconfigurable ComputingSeptember 19, 2006 Lect-09.9Crossbar Topology• Devices A-D are routing only• Gives predictable performance• Potential waste of resources for near-neighbor connectionsA B C DW X Y ZCprE 583 – Reconfigurable ComputingSeptember 19, 2006 Lect-09.10Crossbar HierarchyE F G HM N O PI J K LQ R S TA B C DCprE 583 – Reconfigurable ComputingSeptember 19, 2006 Lect-09.11Other Two-Level SchemesA B CTSRO NQPD E FGHM LIJKF1F3F2F4CprE 583 – Reconfigurable ComputingSeptember 19, 2006 Lect-09.12Thought Exercise• Consider the linear array, mesh, crossbar, hierarchy, and other two-level topologies• In groups of 2, analyze the average distance needed to communicate given a random placement of functions to FPGAs• Can this be represented as a function of N?• Assume finite number of pins per device• Best topology wins a prize3CprE 583 – Reconfigurable ComputingSeptember 19, 2006 Lect-09.13Multi-FPGA Synthesis• Missing high-level synthesis• Global placement and routing similar to intra-device CADCprE 583 – Reconfigurable ComputingSeptember 19, 2006 Lect-09.14Bipartitioning• Perhaps biggest problem in multi-FPGA design is partitioning• NP-complete for general graphs• Many heuristics/attacks• Partitioner must deal with logic and pin constraints• Better to recursively bipartition circuitCprE 583 – Reconfigurable ComputingSeptember 19, 2006 Lect-09.15KL FM Partitioning Heuristic• KLFM – Fiduccia-Mattheyses (Kernighan-Lin refinement)• Greedy, iterative• Pick cell that decreases cut and move it• Repeat• Small amount of• Look past moves that make locally worse• RandomizationCprE 583 – Reconfigurable ComputingSeptember 19, 2006 Lect-09.16KL FM Algorithm• Randomly partition into two halves• Repeat until no updates• Start with all cells free• Repeat until no cells free• Move cell with largest gain (balance allows)• Update costs of neighbors• Lock cell in place (record current cost)• Pick least cost point in previous sequence and use as next starting position• Repeat for different random starting pointsCprE 583 – Reconfigurable ComputingSeptember 19, 2006 Lect-09.17Problems with Meshes• Rent’s Rule for the number of wires leaving a partition: P = KGB• Perimeter grows as G0.5but unfortunately most circuits grow at GBwhere B > 0.5• Effectively devices highly pin limited• What does this mean for meshes?CprE 583 – Reconfigurable ComputingSeptember 19, 2006 Lect-09.18Multi-FPGA Systems• Transmogrifier-4 (University of Toronto)• Four Altera Stratix EP1S80F1508C6 FPGAs, each with:• 79,040 LUTs• 7.4Mb internal block RAM• 176 9x9 MACs (4 9x9’s can become 1 36x36)• 1508 pin flip chips• Total TM-4 Capacity: • 316,160 Luts• 29.6Mb internal block RAM• 704 9x9 MACs4CprE 583 – Reconfigurable ComputingSeptember 19, 2006 Lect-09.19Transmogrifier-464/66MhzPCI2xNTSC Video In/Out1.2GHzPIIIGigabitEthernet840MbpsLVDS32GB DDRSDRAMExpansionPortsAltera StratixS80 FPGAIEEE 1394CprE 583 – Reconfigurable ComputingSeptember 19, 2006 Lect-09.20TM-4 FPGA Interconnects• Differential LVDS• Run up to 840 Mbps• Configurable as low speed single ended• 20 transmit and 20 receive