Logic optimization constitutes a critical phase within the Electronic Design Automation (EDA) flow, essential for achieving desired circuit power, performance, and area (PPA) targets. These logic circuits are typically represented as Directed Acyclic Graphs (DAGs), where the structural depth, quantified by node level, critically correlates with timing performance. Modern optimization strategies frequently employ iterative, local transformation heuristics (\emph{e.g.,} \emph{rewrite}, \emph{refactor}) directly on this DAG structure. As optimization continuously modifies the graph locally, node levels require frequent dynamic updates to guide subsequent decisions. However, a significant gap exists: existing algorithms for incrementally updating node levels are unbounded to small changes. This leads to a total of worst complexity in $O(|V|^2)$ for given local subgraphs $\{ΔG_i\}_{i=1}^{|V|}$ updates on DAG $G(V,E)$. This unbounded nature poses a severe efficiency bottleneck, hindering the scalability of optimization flows, particularly when applied to large circuit designs prevalent today. In this paper, we analyze the dynamic level maintenance problem endemic to iterative logic optimization, framing it through the lens of partial topological order. Building upon the analysis, we present the first bounded algorithm for maintaining level constraints, with $O(|V| Δ\log Δ)$ time for a sequence $|V|$ of updates $\{ΔG_i\}$, where $Δ= \max_i \|ΔG_i\|$ denotes the maximum extended size of $ΔG_i$. Experiments on comprehensive benchmarks show our algorithm enables an average 6.4$\times$ overall speedup relative to \rw and \rf, driven by a 1074.8$\times$ speedup in the level maintenance, all without any quality sacrifice.

Boolean equivalence allows Boolean networks with identical functionality to exhibit diverse graph structures. This gives more room for exploration in logic optimization, while also posing a challenge for tasks involving consistency between Boolean networks. To tackle this challenge, we introduceBoolSkeleton, a novel Boolean network skeletonization method that improves the consistency and reliability of design-specific evaluations.BoolSkeletoncomprises two key steps: preprocessing and reduction. In preprocessing, the Boolean network is transformed into a defined Boolean dependency graph, where nodes are assigned the functionality-related status. Next, the homogeneous and heterogeneous patterns are defined for the node-level pattern reduction step. Heterogeneous patterns are preserved to maintain critical functionality-related dependencies, while homogeneous patterns can be reduced. ParameterKof the pattern further constrains the fanin size of these patterns, enabling fine-tuned control over the granularity of graph reduction. To validateBoolSkeleton’s effectiveness, we conducted four analysis/downstream tasks around the Boolean network: compression analysis, classification, critical path analysis, and timing prediction, demonstrating its robustness across diverse scenarios. Furthermore, it improves above 55% in the average accuracy compared to the original Boolean network for the timing prediction task. These experiments underscore the potential ofBoolSkeletonto enhance design consistency in logic synthesis.

Logic Optimization (LO) is a critical stage in the chip design process, focused on improving the Quality of Results (QoR) by optimizing circuit designs to minimize area and delay. During logic optimization, evaluating the QoR after each iteration requires completing logic optimization and technology mapping. The evaluation process is highly time-consuming, restricting the number of optimization iterations possible within a given time. To address this, the AI-aided logic optimization framework (AiLO) is developed to explore more optimization operator sequences (recipes). AiLO framework consists of two core components: AI-based metric evaluation and optimization exploration. To achieve accurate evaluation, different prediction models can be integrated. A multi-scale cross-attention Transformer (CrossLO) is introduced to simulate the optimization structure of recipes across circuit at various scales to enhance the prediction accuracy. Moreover, the AI evaluation module can effectively maintain the recipe ranking, even when prediction accuracy is biased. The logic optimization exploration algorithm integrated with CrossLO (AI evaluation) shows an average improvement of 14.75% over the initial version. NSGA-II (optimization module) integrated with CrossLO achieves a significant lead over other algorithms in the same time. In addition, the AiLO framework continues to grow with the performance of the two components, demonstrating strong adaptability and flexibility.

The increasing complexity of digital circuits and the limitations of heuristic methods have led to growing interest in applying Machine Learning (ML) to Logic Synthesis (LS). ML provides a promising paradigm shift by implementing automated, scalable, and data-driven optimization strategies. This survey provides a comprehensive overview of the latest studies on ML approaches in LS, offering a deep understanding of the fundamental ML methods, and analyzing their strengths and limitations through systematic comparisons. We categorize existing works into two main types: ML-Assistance methods aiming at predicting performance metrics and reducing the cost of traditional simulations, and ML-Agent methods directly replacing heuristic processes in the LS flow. We further analyze ML methods and applications in different LS stages, including Boolean circuit generation, Boolean circuit analysis, logic optimization, and technology mapping, showing great achievements and improvement in exploring non-linear design spaces and discovering new optimization strategies. Finally, we discuss the challenges and limitations in the current situation and further provide a vision of future directions in LS.

Technology mapping is the pivotal synthesis step that translates abstract logical models into technology-dependent implementations using the designated library, e.g., standard cells for ASICs. The efficient solutions heavily rely on the gate selection guided by estimated delay. However, estimating these delays is sophisticated due to the absence of actual interconnect load and transition time during the mapping. In this article, we revisit the difficulties of the delay-driven mapping problem and explore three key insights to address these. Inspired by the insights, we first design a structure-aware load-slew model that integrates input transitions and output loads for gate delay estimations. Benefiting from the model, we propose a delay-iterative framework that progressively reduces the overall circuit delay by further aligning library characteristics with logical network structures. Finally, experiments with 130 nm and 7 nm libraries show its superiority, which averagely reduces circuit delay by 10% with nonlinear delay model, and 6% in delay after P&R, as compared to ABC.

This article introduces OpenLS-DGF, an adaptive logic synthesis dataset generation framework, to enhance machine-learning (ML) applications within the logic synthesis process. Previous dataset generation flows were tailored for specific tasks or lacked integrated ML capabilities. While OpenLS-DGF supports various ML tasks by encapsulating the three fundamental steps of logic synthesis: 1) Boolean representation; 2) logic optimization; and 3) technology mapping. It preserves the original information in both Verilog and ML-friendly GraphML formats. The Verilog files offer semi-customizable capabilities, enabling researchers to insert additional steps and incrementally refine the generated dataset. Furthermore, OpenLS-DGF includes an adaptive circuit engine that facilitates the final dataset management and downstream tasks. The generated OpenLS-D-v1 dataset comprises 46 combinational designs from established benchmarks, totaling over 966 000 Boolean circuits. OpenLS-D-v1 supports integrating new data features, making it more versatile for new tasks. This article demonstrates the versatility of OpenLS-D-v1 through four distinct downstream tasks: circuit classification, circuit ranking, quality of results (QoR) prediction, and probability prediction. Each task is chosen to represent essential steps of logic synthesis, and the experimental results show the generated dataset from OpenLS-DGF achieves prominent diversity and applicability. The source code and datasets are available athttps://github.com/Logic-Factory/ACE/blob/master/OpenLS-DGF.

Open-source electronic design automation (EDA) shows promising potential in unleashing EDA innovation and lowering the cost of chip design. The open-source EDA toolchain is a comprehensive set of software tools designed to facilitate the design, analysis, and verification of electronic circuits and systems. We developed a physical design EDA toolchain (named iPD) from netlist to GDS-II, including design, analysis, and verification. iPD now covers the whole flow of physical design (including floorplan, placement, clock tree synthesis, routing, timing optimization etc.), part of the analysis tools (timing analysis and power analysis), and part of the verification tools (design rule check). For more friendly support EDA research and development and chip design, we design a reliability, extendibility, ease-of-use, and feature richness physical design toolchain. This paper introduces the software structure, functions, and metrics of the iPD toolchain.

Algorithm parallelization to leverage multi-core platforms for improving the efficiency of Electronic Design Automation (EDA) tools plays a significant role in enhancing the scalability of Integrated Circuit (IC) designs. Logic optimization is a key process in the EDA design flow to reduce the area and depth of the circuit graph by finding logically equivalent graphs for substitution, which is typically time-consuming. To address these challenges, in this paper, we first analyze two types of conflicts that need to be handled in the parallelization framework of refactoring And-Inverter Graph (AIG). We then present a fine-grained parallel AIG refactoring method, which strikes a balance between the degree of parallelism and the conflicts encountered during the refactoring operations. Experiment results show that our parallel refactor is 28x averagely faster than the sequential algorithm on large benchmark tests with 64 physical CPU cores, and has comparable optimization quality.

NPN classification is an essential problem in the design and verification of digital circuits. Most existing works explored variable symmetries and cofactor signatures to develop their classification methods. However, cofactor signatures only consider the face characteristics of Boolean functions. In this paper, we propose a new NPN classifier using both face and point characteristics of Boolean functions, including cofactor, influence, and sensitivity. The new method brings a new perspective to the classification of Boolean functions. The classifier only needs to compute some signatures, and the equality of corresponding signatures is a prerequisite for NPN equivalence. Therefore, these signatures can be directly used for NPN classification, thus avoiding the exhaustive transformation enumeration. The experiments show that the proposed NPN classifier gains better NPN classification accuracy with comparable speed.

NPN classification has many applications in the synthesis and verification of digital circuits. The canonical-form-based method is the most common approach, designing a canonical form as representative for the NPN equivalence class first and then computing the transformation function according to the canonical form. Most works use variable symmetries and several signatures, mainly based on the cofactor, to simplify the canonical form construction and computation. This paper describes a novel canonical form and its computation algorithm by introducing Boolean influence to NPN classification, which is a basic concept in analysis of Boolean functions. We show that influence is input-negation-independent, input-permutation-dependent, and has other structural information than previous signatures for NPN classification. Therefore, it is a significant ingredient in speeding up NPN classification. Experimental results prove that influence plays an important role in reducing the transformation enumeration in computing the canonical form. Compared with the state-of-the-art algorithm implemented in ABC, our influence-aided canonical form for exact NPN classification gains up to 5.5x speedup.

Technology mapping is an essential process in the EDA flow which aims to find an optimal implementation of a logic network from a technology library. In ASIC designs, the estimated cell delay w.r.t. the cut has a significant impact on both area and delay of the mapped network. In this work, we first propose formulating cell delay estimation as a regression learning task by incorporating multiple perspective features, such as the structure of logic networks and non-linear cell delays, to guide the mapper search. We design a learning model that incorporates a customized attention mechanism to be aware of the pin delay and jointly learns the hierarchy between the logic network and library, with the help of proposed parameterizable strategies to generate learning labels. Experimental results show that our proposed method noticeably improves area by 12% and delay by 1%, compared with ABC.

Rewriting is a common procedure in logic synthesis aimed at improving the performance, power, and area (PPA) of circuits. The traditional reconvergence-driven And-Inverter Graph (AIG) rewriting method focuses solely on optimizing the reconvergence cone through Boolean algebra minimization. However, there exist opportunities to incorporate other node-rewriting algorithms that are better suited for specific cones. In this paper, we propose an adaptive reconvergence-driven AIG rewriting algorithm that combines two key techniques: multi-strategy-based AIG rewriting and strategy learning-based algorithm selection. The multi-strategy-based rewriting method expands upon the traditional approach by incorporating support for multi-node-rewriting algorithms, thus expanding the optimization space. Additionally, the strategy learning-based algorithm selection method determines the most suitable node-rewriting algorithm for a given cone. Experimental results demonstrate that our proposed method yields a significant average improvement of 5.567% in size and 5.327% in depth.

Boolean matching is significant to digital integrated circuits design. An exhaustive method for Boolean matching is computationally expensive even for functions with only a few variables, because the time complexity of such an algorithm for an n-variable Boolean function is O(2n+1n!). Sensitivity is an important characteristic and a measure of the complexity of Boolean functions. It has been used in analysis of the complexity of algorithms in different fields. This measure could be regarded as a signature of Boolean functions and has great potential to help reduce the search space of Boolean matching. In this paper, we introduce Boolean sensitivity into Boolean matching and design several sensitivity-related signatures to enhance fast Boolean matching. First, we propose some new signatures that relate sensitivity to Boolean equivalence. Then, we prove that these signatures are prerequisites for Boolean matching, which we can use to reduce the search space of the matching problem. Besides, we develop a fast sensitivity calculation method to compute and compare these signatures of two Boolean functions. Compared with the traditional cofactor and symmetric detection methods, sensitivity is a series of signatures of another dimension. We also show that sensitivity can be easily integrated into traditional methods and distinguish the mismatched Boolean functions faster. To the best of our knowledge, this is the first work that introduces sensitivity to Boolean matching. The experimental results show that sensitivity-related signatures we proposed in this paper can reduce the search space to a very large extent, and perform up to 3x speedup over the state-of-the-art Boolean matching methods.