| Computer-aided design (CAD) is one of the key influencers to the quality (e.g., area, power, performance and reliability) of a field programmable gate arrays (FPGAs)-based design. Resynthesis, a circuit rewriting technique in FPGA CAD flow, has emerged to cope with the inherent NP-hardness of the many CAD tasks, the ever increasing design complexity and the logic capacity of FPGAs. Targeting area, power and reliability optimization for FPGAs, this dissertation proposed several novel resynthesis algorithms. In contrast to existing resynthesis techniques, our proposed approaches employ formal methods (e.g., Boolean Satisfiability (SAT) and Stochastic Satisfiability) as the kernel to ensure the correct-by-construction property. In addition, our resynthesis explore multiple new design freedoms (e.g., retiming) and architectural features (e.g., dual-output LUTs and Vdd-programmable interconnect) in order to achieve better quality.;Specifically, this dissertation first presents a systematic study on local rewriting-based resynthesis at logic level. The core algorithm is an efficient SAT-based Boolean matching. Two logic resynthesis techniques using this Boolean matching are proposed for area reduction and fault tolerance, respectively. Particularly, the area-aware resynthesis simultaneously performs logic rewriting and retiming in order to explore a large searching space; the fault-tolerant resynthesis extends the SAT-based Boolean matching to a stochastic version and maximizes the stochastic yield rate under random faults. In addition, this dissertation proposes two more resynthesis algorithms based on global optimization. These two algorithms take the advantage of the architectural features, i.e., a logic resynthesis for fault-tolerance using dual-output LUTs and a physical resynthesis for low power using Vdd-programmable interconnect. The effectiveness of the proposed algorithms are verified by experimental results. |
