Logic Synthesis

Logic synthesis, at its core, focuses on transforming a high-level specification of a digital circuit into an optimized, technology-dependent implementation that can be physically realized. As the demands for integrated circuits increase, the complexity of their building blocks has grown to billions of transistors organized in intricate data paths, control structures, and memory elements. Modern logic synthesis pipelines need to address a multitude of objectives such as performance, power consumption, and manufacturing cost, while simultaneously coping with the exponential complexity that arises from the sheer scale and heterogeneity of today’s systems.

Originally tailored to standard CMOS design flows and guided by well-established metrics like area, delay, and power, logic synthesis has significantly evolved. With the emergence of new computing paradigms (e.g., approximate computing, heterogeneous integration, in-memory computing) and advanced device technologies, synthesizing logic from an initial description to a final circuit implementation has become more sophisticated than ever. Novel data structures and algorithms enable scalable and flexible transformations that leverage Boolean function manipulation, network rewriting, resubstitution, and equivalence checking. Moreover, the synergy with technology mapping, physical design, verification, and test ensures a fully integrated Electronic Design Automation (EDA) stack, making logic synthesis a foundational step in the semiconductor design process.

Despite the maturity of classical logic synthesis, open problems and research opportunities abound. These include improved scalability for massive industrial designs, better support for emerging device technologies and operating conditions such as cryogenic temperatures and new transistor-level primitives, and advanced optimization techniques that reflect contemporary design objectives such as energy efficiency, reliability, and security. Addressing these challenges requires a delicate blend of mathematical rigor, clever heuristics, algorithmic engineering, and integration with state-of-the-art formal methods.

Our Work

In our group, we conduct research in logic synthesis to streamline and advance the translation from abstract specifications to realizable circuits. Our goal is to create novel algorithms, data structures, and frameworks that enable both academic researchers and industry practitioners to achieve better results under ever-more challenging constraints. Our main research activities encompass, but are not limited to, the following areas:

• Efficient Boolean Function Manipulation and Transformation: We design and improve algorithms for representing and optimizing Boolean functions, including Binary Decision Diagrams (BDDs), And-Inverter Graphs (AIGs), Majority-Inverter Graphs (MIGs), or other emerging logic representations. By refining these foundational data structures, we facilitate faster and more scalable logic optimizations, enabling better trade-offs between area, delay, and power consumption.

• Logic Network Rewriting and Restructuring: Our work includes advanced rewriting techniques that simplify logic networks through algebraic and Boolean transformations. By judiciously replacing subgraphs with functionally equivalent but structurally simpler components, we systematically reduce complexity. This approach leads to significantly improved results in terms of circuit depth, node count, and timing closure, all achieved through careful theoretical analysis and heuristic guidance.

• Approximate and Multi-Objective Logic Synthesis: Beyond classical notions of correctness and minimality, we explore logic synthesis methods that permit controlled approximation. By selectively introducing small inaccuracies in exchange for substantial gains in energy efficiency or area reduction, approximate logic synthesis allows designs to meet strict power budgets or performance targets for applications like machine learning and multimedia processing. Our frameworks incorporate multi-objective optimization to balance competing metrics (e.g., area, delay, power, reliability).

• Technology Mapping and Target-Aware Optimization: We extend logic synthesis beyond abstract gate-level descriptions to consider specific target technologies, from advanced FinFET nodes to emerging beyond-CMOS devices. By integrating precise technology mapping techniques, we ensure that the resulting circuits exploit the full capabilities of a chosen manufacturing process. Our algorithms incorporate constraints like non-traditional standard cell libraries, transistor sizing rules, or specialized logic styles.

• Formal Verification and Equivalence Checking: Logic synthesis transformations must preserve functional behavior. We develop robust verification methodologies and tools that leverage satisfiability (SAT) solvers, Binary Decision Diagrams (BDDs), and automated theorem provers to check equivalence between different stages of the synthesis flow. Advanced equivalence checking solutions enable reliable and trustable transformations, forming an integral part of a safe and correct synthesis pipeline.

• Integration with Physical Design Flows: As logic synthesis sits at the frontier between high-level design and layout generation, we research methods that incorporate early physical insight into the synthesis process. By co-optimizing logic and layout, we can preemptively reduce routing congestion, mitigate wire delays, and streamline overall chip design, leading to more predictable performance and lower turnaround times.

Furthermore, we apply our logic synthesis expertise to emerging domains like nanotechnology.

Contact

In case you have any further questions, please do not hesitate to contact us via logic-synthesis.cda@xcit.tum.de.