Contemporary Logic Synthesis: with an Application to AQFP Circuit Optimization

Electronic devices play an irreplaceable role in our lives. With the tightening time to market, exploding demand for computing power, and continuous desire for smaller, faster, less energy-consuming, and lower-cost chips, computer-aided design for electronics, or electronic design automation (EDA), becomes not only inevitable but also critical in the semiconductor industry. Being responsible for the transformation and optimization of switching circuits at the level of logic gates, logic synthesis plays a central role in modern EDA flows and is key to bringing up the quality of results (QoR). For several decades, logic synthesis techniques have been developed based on the properties and needs of CMOS digital circuits and according to the available computing power. Recently, new challenges as well as opportunities have appeared and influenced the research directions of logic synthesis.The development of logic synthesis and the advancement of VLSI designs are both enablers and challengers of each other. The up-scaling of computing systems stresses logic synthesis algorithms for their scalability, efficiency, and QoR. Conversely, better computing systems make computationally intensive strategies in logic synthesis affordable. Moreover, emerging alternatives to CMOS-based technologies pose new problems to be solved in EDA and logic synthesis. As an example, adiabatic quantum-flux parametron (AQFP) is a promising superconducting electronic technology featuring ultra-low switching energy dissipation. However, it has unconventional path-balancing and fanout-branching constraints to be considered in EDA.This thesis presents a collection of novel approaches, demonstrating various aspects of contemporary logic synthesis. In the first part, we focus on technology-independent logic optimization with an emphasis on scalability while pushing the limits on QoR. In the second part, we show how new problems in EDA for emerging technologies like AQFP are approached, as well as how techniques presented in the first part are applied in AQFP circuit optimization.First, the proposal of a simulation-guided logic synthesis paradigm (a) sets the tone of the thesis, emphasizing additional QoR improvements with manageable runtime overhead. Then, the presentation of a family of heuristic resynthesis algorithms (b) complements the high-effort peephole optimization framework. At a higher level, we demonstrate that a simple design space exploration strategy (c), which discovers good optimization sequences on the fly, outperforms human-designed flows. To fulfill the special constraints imposed by the AQFP technology, we study possible constraint relaxations and their tradeoffs (d) and propose an AQFP technology legalization flow (e). Finally, by combining the proposed high-effort optimization (a, b) and other existing optimization algorithms with AQFP legalization (e) in the design space exploration framework (c), we achieve a significant 44% improvement over the state-of-the-art in the problem of AQFP circuit optimization.To sum up, this thesis presents the essence of contemporary logic synthesis with an application in AQFP circuit optimization as an example. Indeed, in present days, the major challenge in logic synthesis lies in finding a "good-enough" local optimal in the huge design space while maintaining reasonable efficiency, as well as inventing or re-designing novel methods to tackle unconventional constraints imposed by emerging technologies.