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

Yu Hu
Zhe Feng
Victor Shih

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

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.

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)

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.