Resynthesis Techniques for FPGA Optimizations

Yu Hu
Advisor: Lei He

Friday, May 22, 2009 at 10:00am-12:00pm
Boelter Hall 6750

Abstract:
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 logic capacity of FPGAs. Targeting area, power and reliability optimization for FPGAs, the 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.

Biography:
Mr. Hu is a graduate student working toward the Ph.D. degree in the Electrical Engineering Department of UCLA. His current research interests include the architecture and synthesis for low power and fault-tolerant reconfigurable devices and embedded circuits. He received his B.Eng. and M.Eng. both in computer science from Tsinghua University, Beijing, China, in 2002 and 2005, respectively. In the summer of 2006, he worked as an intern at Xilinx Research Laboratory, San Jose, CA. He is currently a Graduate Student Researcher with the Electrical Engineering Department, UCLA. He has authored over 30 technical papers in journals and international conferences and is the inventor of four patents in the field of CAD for VLSI designs. Mr. Hu received the IEEE CEDA Best Contribution Award from the Programming Challenge at IWLS 2008, UCLA Henry Samueli School of Engineering Dean's Special GSR Award in 2008 and 2009, and Outstanding Graduate Student Award in 2005 from Tsinghua University. His paper was nominated for IEEE/ACM William J. McCalla ICCAD Best Paper Award in 2008. Mr. Hu has been a full member of Sigma Xi since 2007 and a student member of IEEE since 2005.