Technology Mapping and Optimization Algorithms for Logic Synthesis of Advanced Technologies
Logic synthesis is a key component of electronic design automation (EDA) tools, essential for designing high-performance, compact, and power-efficient integrated circuits. The continuous downscaling of complementary metal-oxide-semiconductor (CMOS) technology has led to remarkable improvements in performance, power efficiency, and density of integrated circuits. However, as CMOS technology faces challenges in further downscaling transistor dimensions, with only marginal improvements at smaller nodes, logic optimization becomes even more vital for enhancing power-performance-area (PPA) metrics. Additionally, many potential alternative technologies to CMOS are emerging, offering significant advantages in power efficiency and performance. Nevertheless, existing EDA tools for CMOS are often not well-suited for these new technologies, necessitating the development of specialized synthesis techniques.
This thesis focuses on developing state-of-the-art logic synthesis methods for advanced technologies. These technologies include conventional CMOS for field-programmable gate arrays (FPGAs) and standard-cell-based designs, as well as superconducting electronics (SCE). In particular, we concentrate on the technology mapping problem, which involves translating a technology-independent circuit description into an interconnection of gates specific to a technology library.
Novel contributions are organized into four parts. First, we improve performance-driven technology mapping for FPGAs. We introduce powerful and runtime-efficient algorithms to decompose functions into lookup tables (LUTs). Then, we develop a LUT mapper that utilizes this decomposition to minimize delay. Our results show substantial advancements over existing methods, including some of the best public results for combinational benchmark circuits. We also propose a LUT mapper that exploits non-routable connections in FPGAs to minimize the circuit delay. Second, we enhance technology mapping for standard-cell-based design. We develop algorithms that address the matching and covering problems, fully leveraging standard cells in modern libraries, including large-input and multiple-output cells. We demonstrate significant improvements compared to the state of the art. Third, motivated by multiple logic representations available in logic synthesis, we propose a technique to translate circuits between different logic representations and perform circuit optimization. Then, we show how to leverage efficiently don't care conditions in logic rewriting. Our methods contribute to obtaining the best-known results in majority-inverter graphs (MIGs) size. Next, we present practical algorithms for factored form literal optimization in modern logic synthesis based on and-inverter graphs (AIGs), demonstrating applications in standard-cell-based design and transistor-level synthesis. Fourth and last, we research synthesis solutions for the two most mature logic families in SCE: the adiabatic quantum-flux parametron (AQFP) and the single-flux quantum (SFQ). For AQFP circuits, we demonstrate that depth-optimal technology mapping is a tractable problem and propose scalable algorithms for mapping and post-mapping area reduction. Finally, we introduce a synthesis framework for SFQ circuits. We show strong results in both logic families.
Considering the increasing difficulties in meeting the design objectives of modern ICs, we argue that innovative research in EDA solutions is of extreme importance.
EPFL_TH10876.pdf
main document
openaccess
N/A
1.18 MB
Adobe PDF
b01e9bd9168ca177034795ed3a5a64a9