Historically, open-source FPGA synthesis and technology mapping tools have been considered far inferior to industry-standard tools. We show that this is no longer true. Improvements in recent years to Yosys (Verilog elaborator) and ABC (technology mapper) have resulted in substantially better performance, evident in both the reduction of area utilization and the increase in the maximum achievable clock frequency. More specifically, we describe how ABC9 — a set of feature additions to ABC — was integrated into Yosys upstream and available in the latest version. Technology mapping now has a complete view of the circuit, including support for hard blocks (e.g., carry chains) and multiple clock domains for timing-aware mapping. We demonstrate how these improvements accumulate in dramatically better synthesis results, with Yosys-ABC9 reducing the delay gap from 30% to 0% on a commercial FPGA target for the commonly used VTR benchmark, thus matching Vivado's performance in terms of maximum clock frequency. We also measured the performance on a selection of circuits from OpenCores as well as literature, comparing the results produced by Vivado, Yosys-ABC1 (existing work), and the proposed Yosys-ABC9 integration.

A new algorithm is proposed to rapidly evaluate an FPGA routing architecture without need of explicitly routing benchmark applications. The algorithm takes as input a probability distribution of nets to be accommodated and a description of an architecture. It produces an estimate for the usage of each type of mux in the FPGA (including intra-cluster muxes), valuable feedback to the architect. The estimates are shown to correlate with actual routed applications in both academic and commercial architectures. This is due in part to the algorithm's novel ability to account for long and multi-fanout nets. Run time is reduced by applying periodic graphs to model FPGAs' regular structure.

FPGA performance depends in part on the choice of basic logic cell. Previous work dating back to 1999-2005 found that the best look-up table (LUT) sizes for area-delay product are 4-6, with 4 better for area and 6 for performance. Since that time several things have changed. A new 'LUT structure' mapping technique can target cells with a larger number of inputs (cut size) without assuming that the cell implements all possible functions of those inputs. We consider in particular a 7-input function composed of two tightly-coupled 4-input LUTs. Changes in process technology have increased the relative importance of wiring delay and configuration memory area. Finally, modern benchmark applications include carry chains, math and memory blocks. Due to these changes, we show that mapping to a 7-input LUT structure can approach the performance of 6-input LUTs while retaining the area and static power advantage of 4-input LUTs.

Field-Programmable Gate Arrays (FPGA) implement logic functions using programmable cells, such as K-input lookup-tables (K-LUTs). A K-LUT can implement any Boolean function with K inputs and one output. Methods for mapping into K-LUTs are extensively researched and widely used. Recently, cells other than K LUTs have been explored, for example, those composed of several LUTs and those combining LUTs with several gates. Known methods for mapping into these cells are specialized and complicated, requiring a substantial effort to evaluate custom cell architectures. This paper presents a general approach to efficiently map into single-output K-input cells containing LUTs, MUXes, and other elementary gates. Cells with to 16 inputs can be handled. The mapper is fully automated and takes a logic network and a symbolic description of a programmable cell, and produces an optimized network composed of instances of the given cell. Past work on delay/area optimization during mapping is applicable and leads to good quality of results.

Packing is a critical step in the CAD flow for cluster-based FPGA architectures, and has a significant impact on the quality of the final placement and routing results. One basic quality metric is routability. Traditionally, minimizing cut (the number of external signals) has been used as the main criterion in packing for routability optimization. This paper shows that minimizing cut is a sub-optimal criterion, and argues to use the Rent characteristic as the new criterion for FPGA packing. We further propose using a recursive bipartitioning-based k-way partitioner to optimize the Rent characteristic during packing. We developed a new packer, PPack2, based on this approach. Compared to T-VPack, PPack2 achieves 35.4%, 35.6%, and 11.2% reduction in wire length, minimal channel width, and critical path delay, respectively. These improvements show that PPack2 outperforms all previous leading packing tools (including iRAC, HDPack, and the original PPack) by a wide margin.

This paper describes a non-volatile reprogrammable FPGA fabric, whose configuration data are provided directly by flash memory. The fabric is optimized for low-cost, low-power applications, leveraging the density of flash and the elimination of conventional configuration SRAM and its attendant static power. After surveying the necessary background on flash and its application to FPGAs, the 1T flash cell is described along with relevant novel aspects of the fabric architecture. The addition of a third level of switching between inter-cluster signals and logic inputs helps to reduce area and raise typical utilization above 95%. Despite the longer signal path, performance is maintained by synergism between the improved routing flexibility and extreme minimization of the fastest LUT input delay. Test cost is reduced by built-in circuits that can test all switches without reprogramming the flash memory. The fabric has been implemented in a 65nm CMOS embedded flash process.

Simulated annealing remains a widely used heuristic for field-programmable gate array placement due, in part, to its ability to produce high-quality placements while accommodating complex objective functions. This paper discusses enhancements to annealing-based placement which improve upon both quality and run-time. Specifically, intelligent strategies for selecting and placing cells are interspersed with traditional random moves during an anneal, allowing the annealer to converge more quickly and to attain better quality with less statistical variability. For thesameamountofcomputationaleffort, the contributions discussed in this paper consistently improve both critical path delay and wire length compared to traditional annealing perturbations.

Simulated annealing remains a widely-used heuristic for FPGA placement due, in part, to its ability to produce high-quality placements while accommodating complex objective functions and architectural constraints. In this work, we investigate the concept of "directed moves" during annealing as a means of improving upon the quality and run-time of the technique. We intersperse "intelligent" strategies for selecting and placing cells along with traditional, random moves during an anneal. This allows our annealer to converge more quickly and to attain better-quality placements with less statistical variability. Our results confirm that, for the same amount of computational effort, directed moves achieve 5% and 10% improvement in critical path delay and wire length, respectively, compared to traditional annealing perturbations.

We introduce the concept of post-placement interconnect entropy: the minimal number of bits required to describe a well-placed netlist, which has connection lengths distributed according to Rent's rule. The entropy is a function of the number N of cells in the netlist and the Rent exponent p. We derive an expression for the entropy per cell and show that it converges as N approaches infinity. The entropy provides an achievable lower bound on the number of configuration bits in a programmable logic device (PLD) [or field-programmable gate array (FPGA)] and a useful measure of its routing flexibility. Specific numerical values are computed for practical situations. For example, any scalable FPGA composed of 4-input lookup table cells would require 31 configuration bits per cell. We compare this to the actual number of configuration bits in a standard FPGA architecture. We generalize the bound to dimensions higher than two, and show that for any p there is an optimal dimension that minimizes the bound.

We introduce the concept of post-placement interconnect entropy: the minimal number of bits required to describe a well-placed netlist, which has connection lengths distributed according to Rent's rule. The entropy is a function of the number N of cells in the netlist and the Rent exponent p. We derive an expression for the entropy per cell and show that it converges as N approaches infinity. The entropy provides an achievable lower bound on the number of configuration bits in a programmable logic device. Specific numerical values are computed for practical situations. For example, any scalable FPGA composed of 4-input lookup table cells would require 31 configuration bits per cell. We compare this to the actual number of configuration bits in a standard FPGA architecture. We generalize the bound to dimensions higher than two, and show that for any p there is an optimal dimension that minimizes the bound.

Novel problems concerning routing in a segmented routing channel are introduced. These problems are fundamental to routing and design automation for field programmable gate arrays (FPGAs), a new type of electrically programmable VLSI. The first known theoretical results on the combinatorial complexity and algorithm design for segmented channel routing are presented. It is shown that the segmented channel routing problem is in general NP-complete. Efficient polynomial time algorithms for a number of important special cases are presented.>

Routing channels in a field-programmable gate array contain predefined wiring segments of various lengths. These may be connected to the pins of the gates or joined end-to-end to form longer segments by programmable switches. The segmented channel routing problem is formulated, and polynomial time algorithms are given for certain special cases. The general problem is NP-complete, but it can be adequately solved in practice. Experiments indicate that a segmented channel with judiciously chosen segment lengths may near the efficiency of a conventional channel.

The penalties for configuring VLSI arrays for yield enhancement are assessed.Each dement of the fabricated array is assumed to be defective with independent probability p.A fixed fractmn R of the elements are to be connected into a prespecified defect-free configuration by means of switched interconnections.The probability that this can be done, known as the yield, must be bounded away from zero.The additional interconnections required increase the integrated circuit's area by the area overhead ratio AOR.Propagation delay is determined by the maximum connection length d.The following results are shown.Connection of RN fixed pins to distinct nondefective elements from an Nelement linear array requires d = O(log N), AOR = O(log N).Connection of RN pairs of elements from two N-element linear arrays requires only constant d and AOR.Connection of a chain ofRN 2 dements from an N x N array requires only constant d and AOR; this result is closely related to the percolation model of statistical physics.Connection of a V'-RN x d'-RN lattice from an N x N array requires d = [~( IV]-~ N).Algorithms are presented that connect any fraction R < I -p of the dements with yield approaching one as N increases.