Projects

University of California Los Angeles
EDA Laboratory

Primary investigator (PI)

Synthesis and Verification for Heterogeneous FPGA and Defect Tolerance

Primary Investigator (PI)

Prof. Lei He
Prof. Rupak Majumdar

Attended Students

Zhe Feng
Yu Hu
Roy Lee
Victor Shih
Wenyao Xu

Funding sources
CCR-0306682, "Design and Synthesis of Power Efficient Programmable Fabric"
UC MICRO 05, "Power Efficient and Variation Tolerant FPGA"
MICRO 06-07, "Circuit Optimization for Robustness and Power Efficiency"

Research statement

Defect tolerance can be introduced by limited redundancy such as extra bits for regular circuit fabrics including memory and data path. However, cost-efficient redundancy is difficult to achieve for combinational logic, which is therefore one of the primary contributors to the system level errors. With high overhead in area, power and performance, TMR can be used to mask defects and soft errors, and logic duplication and redundancy in multi-threads/multi-cores have also been proposed to detect soft errors and re-start computation. However, the existing techniques are all based on deterministic and defect-free Boolean abstraction. This Boolean abstraction breaks down as process variations, environmental upsets, and reliability failures become more and more pronounced in emerging applications and technologies, and it becomes increasingly clear that the limiting physical properties of the devices must be reflected in higher level abstractions in order to conduct useful synthesis. Thus, we propose to first characterize devices with respect to these physical parameters, producing quantitative abstractions (e.g., defect probabilities with spatial correlation) that complement the Boolean abstraction. Then, we will study robust synthesis that optimizes for reliability in addition to standard area and delay using these quantitative abstractions of devices as inputs. Such robust synthesis may reduce area, power and performance overhead compared to TMR and redundancy in multi-threads and multi-cores.

This research studies robust Synthesis and its System Level Impacts, and considers both ASIC and heterogeneous FPGA.

Research Outcomes

IPR: In-Place Reconfiguration for FPGA Fault Tolerance. We present a fault-tolerant logic resynthesis based on In-Place Reconfiguration (IPR) for LUT-based FPGAs. IPR maximizes identical configuration bits for complementary inputs of an LUT such that the faults seen at the complementary inputs are not propagated. It preserves the function of the LUT and topology of the logic network, and therefore requires no change in physical design. Compared to ROSE, our recent fault-tolerant logic resynthesis algorithm that rewrites logic and physical synthesis with 30% more mean time to failure (MTTF) than the conventional logic synthesis, IPR is more scalable (it runs 140X faster than ROSE), reduces the relative fault rate by 4% and increases MTTF by 2% with similar area/performance. Applying both ROSE and IPR reduces the relative fault rate by 5% and increases MTTF by 6%. The above improvement assumes a single fault and more improvement is expected for multi-fault models. Also, this paper focuses on stochastic faults. But IPR is applicable to deterministic faults or ECO.

Post-Layout FPGA Retiming for Variational SET Mitigation. Single event transient (SET)-induced faults are significantly more pronounced than single event upset (SEU) for the FPGAs based on non-volatile memory. While most existing work studies SEU, this paper proposes a retiming algorithm, namely SaR, for mitigating variational SETs (i.e., SETs with different durations). Considering the reshaping effect of an SET pulse due to broadening and attenuation during its propagation, SaR redistributes the combinational paths via post-layout retiming and minimizes the possibility that an SET pulse is latched. In contrast to existing SET-mitigation techniques, the proposed SaR does not change the FPGA architecture or layout of an FPGA application except reconfiguring the connection between the flip-flop and LUT within a programmable logic block. Experimental results show that SaR increases the mean-time-to-failure (MTTF) by up to 3.78X while preserving the clock frequency for ISCAS89 benchmarks. To the best of our knowledge, this paper is the first in-depth study on retiming for FPGA SET mitigation.

Fault-Tolerant Resynthesis for Dual-Output LUTs. We present a fault-tolerant post-mapping resynthesis for FPGA-based designs that exploits the dual-output feature of modern FPGA architectures to improve reliability of a mapped circuit against faults. Emerging FPGA architectures, such as 6-LUTs in Xilinx Virtex-5 and 8-input ALMs in Altera Stratix-III, have a secondary LUT output that allows access to non-occupied SRAM bits. We show that this architectural feature can be used to build redundancy for fault masking with limited area, power, and performance overhead. Our algorithm improves reliability of a mapping by performing two basic operations: duplication (in which free configuration bits are used to duplicate a logic function whose value is obtained on the secondary output) and encoding (in which two copies of the same logic function are ANDed or ORed together in the fanout of the duplicated logic). The problem of fault tolerant post-mapping resynthesis is then formulated as the optimal duplication and encoding scheme that ensures minimal circuit fault rate w.r.t. a stochastic single fault model. We show an ILP formulation of this problem and an efficient algorithm based on generalized network flow. On MCNC benchmarks, experimental results show that for combinational circuits the proposed approach improves mean time-to-failure by 25% with 4% area overhead, and the proposed approach with explicit area redundancy improves MTTF by 113% with 36% area overhead, compared to the baseline mapping by ABC. To the best of our knowledge, this represents the first systematic study that exploits dual-output LUT architectures for FPGA fault tolerance. The paper was presented in SELSE'09.

Robust FPGA Resynthesis Based on Fault Tolerant Boolean Matching. We present the first in-depth study on FPGA logic synthesis for stochastic fault rate reduction considering both permanent and transient defects. We first develop a fault tolerant Boolean matching FTBM, which leverages the flexibility of the LUT configuration to maximize the stochastic yield rate for a logic function. We then propose a FTBM-based resynthesis algorithm ROSE to maximize stochastic yield rate for an entire circuit. Finally, we show that existing PLB (programmable logic block) templates for area-aware Boolean matching and logic resynthesis are not effective for fault tolerance, and we propose a new robust template with path re-convergence. Compared to the state-of-the-art academic technology mapper Berkeley ABC, ROSE using the proposed robust PLB template reduces the fault rate by 25% with 1% fewer LUTs, and increases MTBF (mean time between failures) by 31%, while preserving the optimal logic depth. The work was presented in IWLS'08 [C118] and accepted ICCAD'08 [C120] with the Best Paper Award nomination.

FPGA Area Reduction by Multi-Output Function Based Sequential Resynthesis. We propose a new resynthesis algorithm for FPGA area reduction. In contrast to existing resynthesis techniques, which consider only single-output Boolean functions and the combinational portion of a circuit, we consider multi-output functions and retiming, and develop effective algorithms that incorporate recent improvements to SAT-based Boolean matching. Our experimental results show that the proposed resynthesis algorithm reduces area up to 35% compared to the best existing academic technology mapper, Berkeley ABC. Furthermore, considering multi-output functions obtains 3x more area reduction compared to considering single-output functions, and sequential resynthesis obtains 1.5x more area reduction compared to combinational resynthesis when both consider multi-output functions. At the same time, all results preserve the optimal logic depth produced by the ABC mapper. The paper was presented in IWLS'08 [C119] and DAC'08 [C116]. The implementation of this work has been included as a part of the Open Access Gear package and we received the Best Contribution Award of IEEE Programming Contest at IWLS'08 [P1].

Exploiting Symmetry in SAT-Based Boolean Matching for Heterogeneous FPGA Technology Mapping. The Boolean matching problem is a key procedure in technology mapping for heterogeneous Field Programmable Gate Arrays (FPGA), and SAT-based Boolean matching (SAT-BM) provides a highly flexible solution for various FPGA architectures. However, the computational complexity of state-of-the-art SAT-BM prohibits its application practically. In this work we propose an efficient SAT-BM algorithm by exploring function and architectural symmetries. While the most recent work obtained up to 13x speedup, we achieve up to 200x speedup, when both are compared to the original SAT-BM algorithm. This work was presented in IWLS'07 [C102] and ICCAD'07 [C109]. The journal version can be found in [J44]

Design, Synthesis and Evaluation of Heterogeneous FPGA. Small gates, such as AND2, XOR2 and MUX2, have been mixed with lookup tables (LUTs) inside the programmable logic block (PLB) to reduce area and power and increase performance in FPGAs. However, it is unclear whether incorporating macro-gates with wide inputs inside PLBs is beneficial. In this work, we first propose a methodology to extract a small set of logic functions that are able to implement a large portion of functions for given FPGA applications. Assuming that the extracted logic functions are implemented by macro-gates in PLBs, we then develop a complete synthesis flow for such heterogeneous PLBs with mixed LUTs and macro-gates. The flow includes a cut-based delay and area optimized technology mapping, a mixed binary integer and linear programming based area recovery algorithm to balance the resource utilization of macro-gates and LUTs for area-efficient packing, and a SAT-based packing. We finally evaluate the proposed heterogeneous FPGA using the newly developed flow and show that mixing LUT and macro-gates, both with 6 inputs, improves performance by 16.5% and reduces logic area by 30% compared to using merely 6-input LUTs. This work was presented in IWLS'07 [C103] and ICCAD'07 [C110].

Low Power Technology Mapping for FPGA Architectures with Dual Supply Voltages. In this paper we study the technology mapping problem of FPGA architectures with dual supply voltages (Vdds) for power optimization. This is done with the guarantee that the mapping depth of the circuit will not increase compared to the circuit with a single Vdd. We first design a single-Vdd mapping algorithm that achieves better power results than the latest published low power mapping algorithms. We then show that our dual-Vdd mapping algorithm can further improve power savings by up to 11.6% over the single-Vdd mapper. In addition, we investigate the best low-Vdd/high-Vdd ratio for the largest power reduction among several dual-Vdd combinations. To our knowledge, this is the first work on dual-Vdd mapping for FPGA architectures. [C45]

References

J44. Yu Hu, Victor Shih, Rupak Majumdar. and Lei He, "Exploiting Symmetries to Speed-Up SAT-Based Boolean Matching for Logic Synthesis of FPGAs", accepted by IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

C45. D. Chen, J. Cong, F. Li and L. He,"Low Power Technology Mapping for FPGA Architectures with Dual Supply Voltages", the Twelfth International Symposium on Field Programmable Gate Arrays, Monterey, CA, pages: 109-117, February 2004

C102.Yu Hu, Victor Shih, Rupak Majumdar and Lei He, "Exploiting Symmetry in SAT-Based Boolean Matching for Heterogeneous FPGA Technology Mapping ", IWLS, 2007. (pdf) (ppt)

C103.Yu Hu, Satyaki Das and Lei He, "Design, Synthesis and Evaluation of Heterogeneous FPGA with Mixed LUTs and Macro-Gates ", IWLS, 2007. (pdf) (ppt)

C109.Yu Hu, Victor Shih, Rupak Majumdar and Lei He, "Exploiting Symmetry in SAT-Based Boolean Matching for Heterogeneous FPGA Technology Mapping", IEEE/ACM International Conf. on Computer-Aided Design (ICCAD), San Jose, CA, Nov. 2007. (pdf) (ppt)

C110.Yu Hu, Satyaki Das, Steve Trimberger and Lei He, "Design, Synthesis and Evaluation of Heterogeneous FPGA with Mixed LUTs and Macro-Gates", IEEE/ACM International Conf. on Computer-Aided Design (ICCAD), San Jose, CA, Nov. 2007. (pdf) (ppt)

C116.Yu Hu, Victor Shih, Rupak Majumdar, and Lei He, "FPGA Area Reduction by Multi-Output Function Based Sequential Resynthesis", IEEE/ACM Design Automation Conference, June, 2008, Anaheim, CA. (pdf)

C118. Yu Hu, Zhe Feng, Rupak Majumdar, and Lei He, "Templates and Algorithms of Boolean Matching for Fault Tolerance in FPGAs", IWLS 2008.

C119. Yu Hu, Victor Shih, Rupak Majumdar, and Lei He, "FPGA Area Reduction by Multi-Output Function Based Sequential Resynthesis", IWLS 2008.

C120. Yu Hu, Zhe Feng, Lei He, and Ruapk Majumdar, "Robust FPGA Resynthesis Based on Fault Tolerant Boolean Matching", accepted by ICCAD 2008. (Nominated for the Best Paper Award) (pdf)

C_SELSE. Ju-Yueh Lee, Yu Hu, Rupak Majumdar, Lei He, and Minming Li, Fault-Tolerant Resynthesis for Dual-Output LUTs, SELSE, 2009. (pdf)

P1. Yu Hu, Victor Shih, Rupak Majumdar, and Lei He, Mapping and Resynthesis for LUT-based FPGAs with an Efficient SAT-Based Boolean Matching, IWLS, 2008 (Best Contribution Award of the IEEE Programming Contest at IWLS 08).

Send your comments to our webmaster.
Last update: 01-31-2008.