Design mapping algorithms for hybrid FPGAs

The ongoing advancements in VLSI technology and Field Programmable Gate Array (FPGA) architectures have enabled the development of multi-million gate hybrid FPGAs containing diverse types of on-chip resources. Each type of resource in a hybrid FPGA is best suited for implementing a particular type of logic function. Given a target hybrid FPGA containing look-up tables (LUTs) and product term blocks (PLAs), this dissertation presents mapping approaches to minimize the design LUT count by packing PLAs, subject to user-defined performance constraints. The mapping approaches developed during the course of this dissertation support both gate-level and register transfer level (RTL) design descriptions. Given a gate-level design description, potential design PLA partitions are identified using a subgraph identification heuristic. PLA candidate partitions are subsequently selected using fast area, delay and Pterm estimators that evaluate and rank the fitness of each potential PLA partition. Given an RTL design description, the design RTL constructs are initially characterized using rule-based RTL area, delay and Pterm estimators. Based on the estimations, RTL structures are appropriately sized for PLAs using a set of RTL partitioning and clustering algorithms. In both the gate-level and RTL approaches, the rest of the design that is not mapped to PLAs is considered to be the LUT partition and is fed to vendor tools along with PLA partitions for final synthesis, placement and routing. It is shown that when tinning-constrained, our gate-level design mapping approach reduces LUT utilization for Apex20KE devices [1] by 8% and when unconstrained by 14% by migrating logic from LUTs to Pterm structures. Due to the presence of fewer number of PLA candidate subgraphs at RTL, the PLA logic identification procedure at RTL is twice as fast as the gate-level PLA subgraph identification procedure and saves about twice the number of LUTs