Our technology mapping work has targeted both lookup-table (LUT) only based architectures and hybrid FPGA devices which contain both LUTs and PLAs. Our LUT mapping approach is based on binary decision diagram (BDD) decomposition. The approach has been shown to be significantly faster and more delay-efficient than previous graph-covering and cut-based FPGA synthesis techniques. The approach is particularly effective for arithmetic circuits, which are efficiently implemented with XORs.

As integration levels in FPGA devices have increased over the past decade, the structure of programmable logic resources has become more diversified. In addition to traditional 4-input look-up table resources found in most SRAM-based devices, many programmable architectures now contain function-specific structures optimized for specific design circuitry. In this work a novel FPGA technology mapping approach has been developed that automatically partitions user designs into netlist subgraphs appropriately-sized for implementation on both types of available user resources. The subgraphs are subsequently mapped to assigned target resources. An important aspect of the technology mapping process is the intermediate determination of subgraph size in terms of subgraph input, output and product term count relative to available PLA resources. In the study it is shown that fast estimation of post-minimization product term counts plays an especially important role in the mapping of designs to PLAs. Pterm estimation allows for the rapid and accurate evaluation of logic density for each subgraph without the need to perform a full complement of time-consuming minimization passes. It is shown that our heuristic algorithm generates improved results compared to previous algorithms targeting PLA/LUT-based devices for a set of FPGA benchmark circuits and increases device utilization for Altera APEX20KE devices by about 10% compared to existing LUT-only mapping approaches.

Recently, as programmable logic device capacities have scaled, concerns about device layout times have increased. With the imminent availability of multi-million gate FPGAs in the next few years the need to address device compile time issues has become critical. Recent trends in ASIC development indicate a strong shift toward design reuse through the use of intellectual property (IP). By considering portions of the user design as pre-compiled macro-blocks numerous tradeoffs in tasks ranging from high-level synthesis to device layout have been evaluated leading to accelerated design translation and higher performance design implementation. In this work we describe Frontier, an FPGA placement system that uses design macro-blocks in conjuction with a series of placement algorithms to achieve highly-routable and high-performance layouts quickly. In the first stage of design placement, a macro-based floorplanner is used to quickly identify an initial layout based on inter-macro connectivity. Next, an FPGA routability metric is used to evaluate the quality of the initial placement. Finally, if the floorplan is determined to be unroutable, a feedback-driven placement perturbation step is employed to achieve a lower cost placement. For a collection of large reconfigurable computing benchmark circuits our placement system exhibits a 4x speedup in combined place and route time versus commercial FPGA CAD software with improved design performance for most designs. It is shown that floorplanning, routability evaluation, and back-end optimization are all necessary to achieve efficient placement solutions.

To speed FPGA routing, we have developed a modified depth-first maze router for island-style FPGA architectures. This router incorporates a novel search technique which guides each net from source to sink by first examining routing congestion at the sink. This domain negotiation approach is shown to accelerate routing by over 10% in FPGA architectures which contain subset switchboxes.