Projects

University of California Los Angeles
Design Automation Laboratory

Primary investigator (PI)

Synthesis and Verification for Defect and Soft-error Tolerance

Primary Investigator (PI)

Prof. Lei He
Prof. Rupak Majumdar

Attended Students

Cheng-ru Chang
Zhe Feng
Yu Hu
Roy Lee
Carson Umsted (part-time student working at JPL)
Victor Shih

Industrial Liaisons

Shi-Jie Wen (Cisco)
Rick Wong (Cisco)
Yutao He (JPL)

Funding sources
NSF 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 "
UC Discovery Grant 193357, Cisco, and ICscape (2010-2012): "In-Place Logic Re-Synthesis for Design Closure"
UC Discovery Grant (180890), Cisco (2010-2012), "Reliable Circuits and Systems"
UC Discovery 2011 Proof of Concept Program (197728) for Acceleration of Technology Transfer, "Soft Error Mitigation for FPGA Based Systems"
In kind donations from Actel/Microsemi, Altera, Xilinx and JPL

Research statement

Defects and soft errors can be tolerated 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

Heterogeneous Configuration Memory Scrubbingfor Soft Error Mitigation in FPGAs. We present HCS (Heterogeneous CRAM Scrubbing) for FPGAs. By utilizing stochastic fault modeling for SEUsin CRAM, we present a quantitative estimate of system MTTF improvement through CRAM scrubbing. HCS then leverages the fact that different SEUs have unequaleffectson the circuit system operation, and scrubs the CRAM bits at different rates based on the sensitivity of the bits to the circuit system failures. To develop a technique which improves system MTTF most for a given circuit system, we present a dynamic programming algorithm which solves the problem efficiently and effectively. Through a system level study on an H.264/AVC decoder implemented on a Xilinx Virtex-5 FPGA, we show an estimation of 60% MTTF improvement by HCS over the existing homogeneous CRAM scrubbing method, while contributing virtually no area, performance and power overhead to the system.[C157]

IPF: In-Place X-Filling to Mitigate Soft Errors in SRAM-based FPGAs. SRAM-based Field Programmable Gate Arrays (FPGAs) are vulnerable to Single Event Upsets (SEUs). We show that a large portion (40%-60% for the circuits in our experiments) of the total used LUT configuration bits are don't care bits, and propose to decide the logic values of don't care bits such that soft errors are reduced. Our approaches are efficient and do not change LUT level placement and routing. Therefore, they are suitable for design closure. For the ten largest combinational MCNC benchmark circuits mapped for 6-LUTs, our approaches obtain 20% chip level Mean Time To Failure (MTTF) improvements, compared to the baseline mapped by Berkeley ABC mapper. They obtain 3x more chiplevel MTTF improvements and are 128x faster when compared to the existing best in-place IPD algorithm.This work was presented in FPL'07 [C149]

In-Place Decomposition for Robustness in FPGA. The programmable logic block (PLB) in a modern FPGA features a built-in carry chain (or adder) and a decomposable LUT, where such an LUT may be decomposed into two or more smaller LUTs. Leveraging decomposable LUTs and underutilized carry chains, we propose to decompose a logic function in a PLB into two subfunctions and to combine the subfunctions via a carry chain to make the circuit more robust against single-event upsets(SEUs). Note that such decomposition can be implemented using the decomposable LUT and carry chain in the original PLB without changing the PLB-level placement and routing. Therefore, it is an in-place decomposition (IPD) with no area and timing overhead at the PLB level and has an ideal design closure between logic and physical syntheses. For 10 largest combinational MCNC benchmark circuits with a conservative 20% utilization rate for carry chain, IPD improves MTTF (mean time to failure) by 1.43 and 2.70 times respectively, for PLBs similar to those in Xilinx Virtex-5 and Altera Stratix-IV. This work was presented in ICCAD'10 [C144]

Mitigating FPGA Interconnect Soft Errors by In-Place LUT Inversion. Modern SRAM-based FPGAs (Field Programmable Gate Arrays) use multiplexer-based unidirectional routing, and SRAM configuration cells in these multiplexers contribute to the majority of soft errors in FPGAs. In this paper, we formulate an In-Placed inVersion (IPV) on LUT (Look-Up Table) logic polari-ties to reduce the Soft Error Rate (SER) at chip level, and reveal a locality and NP-Hardness of the IPV problem. We then develop an exact algorithm based on the binary integer linear program-ming (ILP) and also a heuristic based on the simulated annealing (SA), both enabled by the locality. We report results for the 10 largest MCNC combinational benchmarks synthesized by ABC and then placed and routed by VPR. The results show that IPV obtains close to 4x chip level SER reduction on average and SA is highly effective by obtaining the same SER reduction as ILP does. A recent work IPD has the largest LUT level SER reduction of 2.7x in literature, but its chip level SER reduction is merely 7% due to the dominance of interconnects. In contrast, SA-based IPV obtains nearly 4x chip level SER reduction and runs 30x faster. Furthermore, combining IPV and IPD leads to a chip level SER reduction of 5.3x. This does not change placement and routing, and does not affect design closure. To the best of our knowledge, our work is the first in-depth study on SER reduction for modern multiplexer-based FPGA routing by in-placed logic re-synthesis.This work was presented in ICCAD'11 [C152]

Rewiring for Robustness. Logic synthesis for soft error mitigation is increasingly important in a wide range of applications of FPGAs. We present R2 , an algorithm for rewiring a post-layout LUTbased circuit that reduces the overall criticality of the circuit, here criticality is the fraction of primary inputs that lead to observable errors at the primary outputs if an single event upset inverts a configuration bit. Our algorithm explicitly optimizes the robustness of the interconnect, the dominant component of FPGAs. The key idea of R2 is to exploit Boolean flexibilities in the circuit implementation to replace wires of high criticality with those with lower criticality while preserving the circuit functionality. We estimate criticalities using Monte Carlo fault simulation. We represent flexibilities using SPFDs (Set of Pairs of Functions to be Distinguished), and use criticality information to choose candidates for rewiring, assigning the maximum flexibility to high criticality wires. Compared to IPR, a recent robust logic optimization, our implementation increases MTTF (Mean Time to Failure) by 24%, showing for the first time, the advantages of exploiting Boolean flexibilities in optimizing for robustness. It also reduces FPGA wire and LUT numbers by 5% and 2% respectively, more than the reductions obtained by the existing rewiring algorithm for area minimization. This paper was nominated Best Paper Award by DAC 2010.[C140]

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. This paper was nominated Best Paper Award by ICCAD 2009.

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 with 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 ASPDAC'10.

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

C157. Cheng-Ru Chang, Naifeng Jing, Juexiao Su, Shijie Wen, Rich Wong, Lei He , "Heterogeneous Configuration Memory Scrubbing for Soft Error Mitigation in FPGAs", Field-Programmable Technology (FPT), 10-12 Dec. 2012 (pdf)

C152. Naifeng Jing, Ju-Yueh Lee, Weifeng He, Zhigang Mao and Lei He, "Mitigating FPGA Interconnect Soft Errors by In-Place LUT Inversion," ICCAD 2011 (ppt) (pdf)

C149 Zhe Feng, Naifeng Jing, Yu Hu and Lei He, "IPF: In-place X-Filing to Mitigate Soft Errors in SRAM-based FPGAs", International Conference on Field Programmable Logic and Applications(FPL), Sep.,2011.(ppt)(pdf)

C144 Ju-Yueh Lee, Zhe Feng and Lei He, "In-Place Decomposition for Robustness in FPGA," 2010 International Conference on Computer-Aided Design , Nov. (ppt)(pdf)

C140 Manu Jose, Yu Hu, Rupak Majumdar and Lei He, "Rewiring for Robustness", 47th IEEE Design Automation Conference (DAC'10) , Anaheim, CA, June 13-18, 2010.(pdf)

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

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(pdf)

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. (pdf)(ppt)

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

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.