Metastability is a phenomenon that can cause system failures in digital circuits. It may occur whenever signals are being transmitted across asynchronous or unrelated clock domains. The impact of metastability is increasing as process geometries shrink and supply voltages drop faster than transistor Vts. FPGA technologies are significantly affected since leading edge FPGAs are amongst the first devices to adopt the most recent process nodes. In this paper, we present a comprehensive suite of techniques for modeling, characterizing and optimizing metastability effects in FPGAs. We first discuss a theoretical model of metastability, and verify the predictions using both circuit level simulations and board measurements. Next we show how designers have traditionally dealt with metastability problems and contrast that with the automatic CAD algorithms described in this paper that both analyze and optimize metastability-related issues. Through our detailed experimental results, we show that we can improve the metastability characteristics of a large suite of industrial benchmarks by an average of 268,000 times with our optimization techniques.

Abstract—This work presents the first published algorithm to simultaneously optimize both short- and long-path timing constraints in a Field-Programmable Gate Array (FPGA): the Routing Cost Valleys (RCV) algorithm. RCV consists of two components: a new slack allocation algorithm that determines both a minimum and a maximum delay budget for each circuit connection, and a new router that strives to meet and, if possible, surpass these connection delay constraints. RCV improves both long-path and short-path timing slack significantly versus an earlier Computer-Aided Design (CAD) system, showing the importance of an integrated approach that simultaneously optimizes both types of timing constraints. It is able to meet longpath and short-path timing on all 157 Peripheral Component Interconnect (PCI) cores tested, while an earlier algorithm failed to achieve timing on 75 % of the cores. Even in cases where there are no short-path timing constraints, RCV outperforms a stateof-the-art FPGA router and improves the maximum clock speed of circuits by an average of 3.2 % (and up to 24.7%). L Index Terms—FPGA, routing, slack allocation, timing

This work presents the routing cost valleys (RCV) algorithm - the first published algorithm that simultaneously optimizes all short- and long-path timing constraints in a field-programmable gate array (FPGA). RCV is comprised of a new slack allocation algorithm that produces both minimum and maximum delay budgets for each circuit connection, and a new router that strives to meet and, if possible, surpass these connection delay constraints. RCV achieves excellent results. On a set of 100 large circuits, RCV improves both long-path and short-path timing slack significantly vs. an earlier computer-aided design (CAD) system that focuses solely on long-path timing. Even with no short-path timing constraints, RCV improves the clock speed of circuits by 3.9% on average. Finally, RCV is able to meet timing on all 72 peripheral component interconnect (PCI) cores tested, while an earlier algorithm fails to achieve timing on all 72 cores.

One of the most difficult and time-consuming steps in the creation of an FPGA is its transistor-level design and physical layout. Modern commercial FPGAs typically consume anywhere from 50 to 200 man-years simply in the layout step. To date, automated tools have only been employed in small parts of the periphery and programming circuitry. The core tiles, which are repeated many times, are subject to painstaking manual design and layout. In this paper we present a new system (called GILES, for Good Instant Layout of Erasable Semiconductors) that automatically generates a transistor-level schematic from a high-level architectural specification of an FPGA. It also generates a cell-level netlist that is placed and routed automatically. The architectural specification is the one used as input to the VPR [3] architectural exploration tool. The output is the mask-level layout of a single tile that can be replicated to form an FPGA array. We describe a new placement tool that simultaneously places and compacts the layout to minimize white space and wiring demand, and a special-purpose router built for this task.GILES can place and route a tile consisting of four 4-input LUT logic cells and all of its programmable wires in a 0.18μm CMOS process using 8 layers of metal and 25983μm2 of area. When we generate the layout of an architecture similar to the Xilinx Virtex-E FPGA (built in a 0.18μm process) GILES requires only 47% more area than the original. The layout area of an architecture similar to the Altera Apex 20K400E (also built in a 0.18µm process) constructed by GILES requires 97% more area than the original.