Process variation in nanometer technology is becoming an important issue for cutting-edge FPGAs with a multimillion gate capacity. Considering both die-to-die and within-die variations in effective channel length, threshold voltage, and gate oxide thickness, we first develop closed-form models of chip-level FPGA leakage and timing variations. Experiments show that the mean and standard deviation computed by our models are within 3% from those computed by Monte Carlo simulation. We also observe that the leakage and timing variations can be up to 3X and 1.9X, respectively. We then derive analytical yield models considering both leakage and timing variations, and use such models to evaluate the performance of FPGA device and architecture considering process variations. Compared to the baseline, which uses the VPR architecture and device setup based on the ITRS roadmap, device and architecture tuning improves leakage yield by 10.4%, timing yield by 5.7%, and leakage and timing combined yield by 9.4%. We also observe that LUT size of 4 gives the highest leakage yield, LUT size of 7 gives the highest timing yield, but LUT size of 5 achieves the maximum leakage and timing combined yield. To the best of our knowledge, this is the first in-depth study on FPGA architecture and device coevaluation considering process variation.

This paper develops a trace-based framework to enable concurrent process and FPGA architecture co-development. Based on process parameters and traces for FPGA applications, the framework calculates the chip level performance and power distribution and soft error rate (SER) with consideration of process variations and device aging. As examples to utilize the framework, the paper further applies heterogeneous gate lengths to logic and interconnects for energy reduction, and studies the interaction between device aging, process variation and SER

Field programmable dual-Vdd interconnects are effective in reducing FPGA power. We formulate the dual-Vdd-aware slack budgeting problem as a linear program (LP) and a min-cost network flow problem, respectively. Both algorithms reduce interconnect power by 50% on average compared to single-Vdd interconnects, but the network-flow-based algorithm runs 11x faster on MCNC benchmarks. Furthermore, we develop simultaneous retiming and slack budgeting (SRSB) with flip-flop layout constraints in dual-Vdd FPGAs based on mixed integer linear programming, and speed-up the algorithm by LP relaxation and local legalization. Compared to retiming followed by slack budgeting, SRSB reduces interconnect power by up to 28.8%.

Process variation and prerouting interconnect delay uncertainty affect timing and power for modern VLSI designs in nanometer technologies. This paper presents the first in-depth study on stochastic physical synthesis algorithms leveraging statistical static timing analysis (SSTA) with process variation and prerouting interconnect delay uncertainty for field-programmable gate arrays (FPGAs). Evaluated by SSTA using the placed and routed circuits, the stochastic clustering, placement, and routing reduce the mean delay by 5.0%, 4.0%, and 1.4%, respectively, and reduce the standard deviation of delay by 6.4%, 6.1%, and 1.4%, respectively for MCNC designs. The majority of improvements come from modeling interconnect delay uncertainty for clustering and from considering process variation for placement, while routing has less improvement on delay. In addition, we study the interaction between each individual design stage. When applying all stochastic algorithms concurrently, the mean delay and standard deviation are reduced by 6.2% and 7.5%, respectively. On the other hand, stochastic clustering with deterministic placement and routing is a good flow with little change to the entire flow, but the mean delay is reduced by 5.0%, the standard deviation is reduced by 6.4%, and the runtime is slightly reduced compared to the deterministic flow. Finally, while its improvement over timing is small, stochastic routing is able to reduce the total wire length by 4.5% and to reduce the overall runtime by 4.2% compared to deterministic routing.

Field programmable dual-Vdd interconnects are effective to reduce FPGA power. However, the deterministic Vdd assignment leverages timing slack exhaustively and significantly increases the number of near-critical paths, which results in a degraded timing yield with process variation. In this paper, we present two statistical Vdd assignment algorithms. The first greedy algorithm is based on sensitivity while the second one is based on timing slack budgeting. Both minimize chip-level interconnect power without degrading timing yield. Evaluated with MCNC circuits, the statistical algorithms reduce interconnect power by 40% compared to the single- Vdd FPGA with power gating. In contrast, the deterministic algorithm reduces interconnect power by 51% but degrades timing yield from 97.7% to 87.5%

Process variation and pre-routing interconnect delay uncertainty affect timing and power for modern VLSI designs in nanometer technologies. This paper presents the first in-depth study on stochastic physical synthesis algorithms leveraging statistical static timing analysis (SSTA) with process variation and pre-routing interconnect delay uncertainty for FPGAs. Evaluated by SSTA with the placed and routed layout and measured at the same clock frequency, the stochastic clustering, placement and routing reduce the yield loss from 50 failed parts per 10 thousand parts (pp10K) for the deterministic flow to 9, 12 and 35pp10K respectively for MCNC designs. The majority of improvements are achieved during clustering and placement while routing stage has much less gain. The gain mainly comes from modeling interconnect delay uncertainty for clustering and from considering process variation for placement. When applying all stochastic algorithms concurrently, the yield loss is reduced to 5pp10K (a 10 X reduction) with the mean delay reduced by 6.2% and the standard deviation reduced by 7.5%. On the other hand, stochastic clustering with deterministic placement and routing is a good flow with little change to the entire flow, but the yield loss is reduced from 50pp10K to 9pp10K, the mean delay is reduced by 5.0%, the standard deviation is reduced by 6.4%, and the runtime is slightly reduced compared to the deterministic flow. Finally, while its improvement over timing is small, stochastic routing is able to reduce the total wire length for the same routing channel width by 4.5% and to reduce runtime by 4.2% compared to deterministic routing.

Late CMOS scaling reduces device reliability, and existing work has studied the permanent SER (soft error rate) for configuration memory in FPGA extensively. In this paper, we show that continuous CMOS scaling dramatically increases the significance of FPGA chip-level transient soft errors in circuit elements other than configuration memory, and transient SER can no longer be ignored. We then develop an efficient, yet accurate, transient SER evaluation method, called trace based methodology, considering logic, electrical and latch-window maskings. By collecting traces on logic probability and sensitivity and re-using these traces for different device settings, we finally perform device and architecture concurrent optimization considering hundreds of device and architecture combinations. Compared to the commonly used FPGA architecture and device settings, device and architecture concurrent optimization can reduce the transient SER by 2.8X and reduce the product of energy, delay and transient SER by 1.8X,

Device optimization considering supply voltage Vdd and threshold voltage Vt has little chip-area increase but a great impact on power and performance in the nanometer technology. This paper studies simultaneous evaluation of device and architecture optimization for field-programmable gate arrays (FPGAs). We first develop an efficient yet accurate timing and power evaluation method called a trace-based model. By collecting trace information from a cycle-accurate simulation of placed and routed FPGA benchmark circuits and reusing the trace for different Vdds and Vts, we enable device and architecture cooptimization considering hundreds of device and architecture combinations. Compared to the baseline FPGA architecture, which uses the Versatile Place and Route architecture model and the same lookup table and cluster sizes as those used by the Xilinx Virtex-II, Vdd suggested by the International Technology Roadmap for Semiconductor, Vt optimized with respect to the preceding architecture, and Vdd architecture and device cooptimization can reduce the energy-delay product (ED) by 20.5% and the chip area by 23.3%. Furthermore, considering the power gating of unused logic blocks and interconnect switches (in this case, sleep transistor size is a parameter of device tuning), our co-optimization reduces ED by 55.0% and the chip area by 8.2% compared to the baseline FPGA architecture. To the best of our knowledge, this is the first in-depth study in the literature on architecture and device cooptimization for FPGAs.

Power reduction is of growing importance for field-programmable gate arrays (FPGAs). In this paper, we apply programmable supply voltage (Vdd) to reduce FPGA power. We first design FPGA logic fabrics using dual-Vdd levels and show that field-programmable power supply is required to obtain a satisfactory power-versus-performance tradeoff. We further design FPGA interconnect fabrics for fine-grained Vdd programmability with minimal increase of the number of configuration static-random-access-memory cells. With a simple yet practical computer-aided design flow to leverage the field-programmable dual-Vdd logic and interconnect fabrics, we carry out a highly quantitative study using placed and routed benchmark circuits, and delay, power, and area models obtained from detailed circuit designs. Compared to single-Vdd FPGAs with the Vdd level suggested by the International Technology Roadmap for Semiconductors for 100-nm technology, field-programmable dual-Vdd FPGAs reduce the total power by 47.61% and the energy-delay product by 27.36%

Field programmable dual-Vdd interconnects are effective to reduce FPGA power.Assuming uniform length interconnects,existing work has developed time slack budgeting to minimize power based on estimating the lower bound of power reduction using dual-Vdd for given time slack.In this paper,we show that such lower bound estimation cannot be extended to mixed length interconnects that are used in modern FPGAs.We develop a technique to estimate power reduction using dual-Vdd for mixed length interconnects, and apply linear programming (LP)to solve slack budgeting to minimize power for mixed length interconnects.Experiments show 53%power reduction on average compared to single-Vdd interconnects.Furthermore,this paper presents a simultaneous retiming and slack budgeting algorithm to reduce power in dual-Vdd FPGAs considering placement and.ip-.op binding constraints.The algorithm is based on mixed integer and linear programming (MILP)and achieves up to 20%power reduction compared to retiming followed by slack budgeting.We propose a runtime e fficient flow to apply simultaneous retiming and slack budgeting only when it is necessary.To the best of our knowledge,this paper is the first in-depth study of simultaneous retiming and slack budgeting for dual-Vdd programmable FPGA power reduction while considering layout constraints.

Process variation affecting timing and power is an important issue for modern integrated circuits in nanometer technologies. FPGAs are similar to ASICs in their susceptibility to these issues, but face unique challenges in that critical paths are unknown at test time. This paper presents the first in-depth study on applying statistical timing analysis with cross-chip and on-chip variations to speed-binning and guard-banding in FPGAs. Considering the uniqueness of reprogrammability in FPGAs, we quantify the effects of timing-model with guard-banding and speed-binning on statistical performance and timing yield. We also develop a new variation aware placement, which is the first statistical algorithm for FPGA layout and reduces yield loss by 3.4x with guard-banding and 25x with speed-binning for MCNC and QUIP designs.

To reduce FPGA power, a linear programming (LP) based time slack allocation algorithm, EdTLC-LP, has been proposed recently for Vdd-programmable interconnects without using Vdd-level converters for mixed wire lengths. However, it takes a long time to solve the LP problem for time slack allocation. In this paper, we develop EdTLC-NW, a slack allocation algorithm based on min-cost network flow to reduce runtime. Compared to single Vdd FPGA with power-gating, EdTLC-LP and EdTLC-NW reduce interconnect power by 52.71% and 52.52%, respectively. EdTLC-NW achieves as good results as EdTLC-LP but runs 8X faster on average. Furthermore, the speedup increases for larger circuits and EdTLC-NW is 20X faster for the largest circuit.

To reduce field-programmable gate array power, Vdd programmability has been recently proposed to select the Vdd level for interconnects and power-gate unused interconnects. However, Vdd-level converters used in the existing Vdd-programmable method consume a large amount of leakage. This paper proposes two ways to avoid using level converters in interconnects, namely; 1) tree-based level converter insertion (TLC) and 2) dual-Vdd tree-based level converter insertion (dTLC). TLC enforces that there is only one Vdd level within each routing tree, while dTLC can have different Vdd levels within a routing tree, but no VddL switch drives VddH switches. Dual-Vdd assignment algorithms were developed considering chip-level time slack allocation for maximum power reduction. The algorithms include TLC-S and dTLC-S, two power sensitivity-based algorithms with implicit time slack allocation, and dTLC-LP, a linear programming (LP)-based algorithm with explicit time slack allocation. All allocate time slack first to interconnects with higher power sensitivity and assign low Vdd to them for more power reduction. Experiments show that dTLC-LP obtains the lowest power consumption. Compared to dTLC-LP, dTLC-S obtains a slightly higher power consumption but runs three times faster. Compared to the existing segment-based level converter insertion for dual Vdd, dTLC-LP reduces interconnect power by 52.90% without performance loss for Microelectronics Center of North Carolina benchmark circuits

Power has become an increasingly important design constraint for FPGAs in nanometer technologies, and global interconnects should be the focus of FPGA power reduction as they consume more power than logic cells. We design area-efficient circuits for programmable fine-grained power-gating of individual unused interconnect switches, and reduce interconnect leakage power dramatically because the interconnect switches have an intrinsically low utilization rate for the purpose of programmability. The low leakage interconnect via power-gating reduces total power by 38.18% for the FPGA in 100nm technology. Furthermore, it enables interconnect dynamic power reduction. We design a routing channel containing abundant or duplicated routing tracks with pre-determined high and low Vdd, and develop routing algorithm using low Vdd for non-critical routing to reduce dynamic power. The track-duplicated routing channel has small leakage power and increase the FPGA power reduction to 45.00%.

Device optimization considering supply voltage Vdd and threshold voltage Vt tuning does not increase chip area but has a great impact on power and performance in the nanometer technology. This paper studies the simultaneous evaluation of device and architecture optimization for FPGA. We first develop an efficient yet accurate timing and power evaluation method, called trace-based model. By collecting trace information from cycle-accurate simulation of placed and routed FPGA benchmark circuits and re-using the trace for different Vdd and Vt, we enable the device and architecture co-optimization for hundreds of combinations. Compared to the baseline FPGA which has the architecture same as the commercial FPGA used by Xilinx, and has Vdd suggested by ITRS but Vt optimized by our device optimization, architecture and device co-optimization can reduce energy-delay product by 20.5% without any chip area increase compared to the conventional FPGA architecture. Furthermore, considering power-gating of unused logic blocks and interconnect switches, our co-optimization method reduces energy-delay product by 54.7% and chip area by 8.3%. To the best of our knowledge, this is the first in-depth study on architecture and device co-optimization for FPGAs.

To reduce power, Vdd programmability has been proposed recently to select Vdd-level for interconnects and to powergate unused interconnects. However, Vdd-level converters used in the Vdd-programmable method consume a large amount of leakage. In this paper, we develop chip-level dual-Vdd assignment algorithms to guarantee that no low-Vdd interconnect switch drives high-Vdd interconnect switches. This removes the need of Vdd-level converters and reduces interconnect leakage and interconnect device area by 91.78% and 25.48%, respectively. The assignment algorithms include power sensitivity based heuristics with implicit time slack allocation and a linear programming (LP) based method with explicit time slack allocation. Both first allocate time slack to interconnects with higher transition density and assign low-Vdd to them for more power reduction. Compared to the aforementioned Vdd-programmable method using Vdd-level converters, the LP based algorithm reduces interconnect power by 65.13% without performance loss for the MCNC benchmark circuits. Compared to the LP based algorithm, the sensitivity based heuristics can obtain slightly smaller power reduction but run 4X faster.

Vdd-programmable FPGAs have been proposed recently to reduce FPGA power, where Vdd levels can be customized for different circuit elements and unused circuit elements can be power-gated. In this paper, we first develop an accurate FPGA power model and then design novel Vdd-programmable interconnect switches with minimum number of configuration SRAM cells. Applying our power model to placed and routed benchmark circuits, we evaluate Vdd-programmable FPGA architecture using the new switches. The best architecture in our study uses Vdd-programmable logic blocks and Vdd-gateable interconnects. Compared to the baseline architecture similar to the leading commercial architecture, the best architecture reduces the minimal energy-delay product by 44.14% with 48% area overhead and 3% SRAM cell increase. Our evaluation results also show that LUT size 4 always gives the lowest energy consumption while LUT size 7 always leads to the highest performance for all evaluated architectures.

Process variations in nanometer technologies are becoming an important issue for cutting-edge FPGAs with a multi-million gate capacity. Considering both die-to-die and within-die variations in effective channel length, threshold voltage, and gate oxide thickness, we first develop closed-form models of leakage and timing variations at the FPGA chip level. Experiments show that our models are within 3% from Monte Carlo simulation, and the leakage and delay variations can be up to 3/spl times/ and 1.9/spl times/, respectively. We then derive analytical yield models considering both leakage and timing variations, and use such models to evaluate FPGA device and architecture under process variations. Compared to the architecture similar to a commercial FPGA and device setting from ITRS roadmap, device tuning alone improves leakage yield by 39% and architecture and device co-optimization increases leakage yield by 73%. We also show that LUT size 4 gives the highest leakage yield, LUT size 7 gives the highest timing yield, but LUT size 5 achieves the maximum combined leakage and timing yield. To the best of our knowledge, this is the first in-depth study on FPGA device and architecture co-evaluation considering process variations.

Field programmable gate arrays (FPGAs) with supply voltage (Vdd) programmability have been proposed recently to reduce FPGA power, where the Vdd-level can be customized for FPGA circuit elements and unused circuit elements can be power-gated. In this paper, we first design novel Vdd-programmable and Vdd-gateable interconnect switches with minimal number of configuration SRAM cells. We then evaluate Vdd-programmable FPGA architectures using the new switches. The best architecture in our study uses Vdd-programmable logic blocks and Vdd-gateable interconnects. Compared to the baseline architecture similar to the leading commercial architecture, our best architecture reduces the minimal energy-delay product by 54.39% with 17% more area and 3% more configuration SRAM cells. Our evaluation results also show that LUT size 4 gives the lowest energy consumption, and LUT size 7 leads to the highest performance, both for all evaluated architectures.

Power optimization is of growing importance for FPGAs in nanometer technologies. Considering dual-Vdd technique, we show that configurable power supply is required to obtain a satisfactory performance and power tradeo#. We design FPGA circuits and logic fabrics using configurable dualVdd and develop the corresponding CAD flow to leverage such circuits and logic fabrics. We then carry out a highly quantitative study using area, delay and power models obtained from detailed circuit design and SPICE simulation in 100nm technology. Compared to single-Vdd FPGAs with optimized Vdd level for the same target clock frequency, configurable dual-Vdd FPGAs with full and partial supply programmability for logic blocks reduce logic power by 35.46% and 28.62% respectively and reduce total FPGA power by 14.29% and 9.04% respectively. To the best of our knowledge, it is the first in-depth study on FPGAs with configurable dual-Vdd for power reduction.

Traditional FPGAs use uniform supply voltage Vdd and uniform threshold voltage Vt. We propose to use pre-defined dual-Vdd and dual-Vt fabrics to reduce FPGA power. We design FPGA circuits with dual-Vdd/dual-Vt to effectively reduce both dynamic power and leakage power, and define dual-Vdd/dual-Vt FPGA fabrics based on the profiling of benchmark circuits. We further develop CAD algorithms including power-sensitivity based voltage assignment and simulated-annealing based placement to leverage such fabrics. Compared to the conventional fabric using uniform Vdd/Vt at the same target clock frequency, our new fabric using dual Vt achieves 9% to 20% power reduction. However, the pre-defined FPGA fabric using both dual Vdd and dual Vt only achieves on average 2% extra power reduction. It is because that the pre-designed dual-Vdd layout pattern introduces non-negligible performance penalty. Therefore, programmability of supply voltage is needed to achieve significant power saving for dual-Vdd FPGAs. To our best knowledge, it is the first in-depth study on applying both dual-Vdd and dual-Vt to FPGA considering circuits, fabrics and CAD algorithms.

Power is an increasingly important design constraint for FPGAs in nanometer technologies. Because interconnect power is dominant in FPGAs, we design Vdd-programmable interconnect fabric to reduce FPGA interconnect power. There are three Vdd states for interconnect switches: high Vdd, low Vdd and power-gating. We develop a simple design flow to apply high Vdd to critical paths and low Vdd to non-critical paths and to power gate unused interconnect switches. We carry out a highly quantitative study by placing and routing benchmark circuits in 100 nm technology to illustrate the power saving. Compared to single-Vdd FPGAs with optimized but nonprogrammable Vdd level for the same target clock frequency, our new FPGA fabric on average reduces interconnect power by 56.51% and total FPGA power by 50.55%. Due to the highly low utilization rate of routing switches, majority of the power reduction is achieved by power gating unused routing buffers. In contrast, recent work that considers Vdd programmability only for logic fabric reduces total FPGA power merely by 14.29%. To the best of our knowledge, it is the first in-depth study on Vdd programmability for FPGA interconnect power reduction.