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.

Routing is a critical stage in achieving timing closure in integrated circuit design. Due to the time-consuming flow of detailed routing (DR), the lack of accurate routing information, and the impact of congestion during global routing (GR), rapidly obtaining precise timing information at the global routing stage to guide subsequent timing optimization is a significant challenge. These challenges lead to substantial discrepancies between the estimated timing at GR stage and the actual results after post-DR, resulting in inaccurate evaluations of chip performance. To address this issue, we propose an effective timing prediction and optimization framework, AiTPO. The innovative KAN-UNet heterogeneous timing prediction model effectively combines UNet and KAN networks. By fusing spatial features extracted by UNet with numerical data, the model gains the capability to learn complex relationships across multi-modal data, thereby enhancing robustness and accuracy. Additionally, with the accurate timing evaluation, we introduce two timing optimization strategies during global routing to enhance timing performance. The first strategy involves net ordering based on predicted significant delay nets, prioritizing the routing of more timing-critical nets to reduce detours caused by congestion. The second strategy employs timing estimation to select the most optimal topology from multiple candidates generated by the enhanced A* algorithm, where congestion is considered as a cost factor. Which contributes to optimizing Worst Negative Slack (WNS) and Total Negative Slack (TNS). Experimental results on the real circuits under 28nm process node show that the wire delay prediction accuracy with the proposed KAN-UNet model improves by 34.6% and 25.4% in terms of Mean Absolute Error (MAE) and Max Absolute Error (MaxAE), respectively, compared to GR-based estimations and demonstrate the effectiveness of our timing optimization strategies, which lead to a 2.0% and 4.2% improvement in TNS and WNS, respectively.

As the demand for higher integration density and performance efficiency continues to grow, 3D stacking has emerged as a promising solution. In 3D ICs, the complexity of physical design and the optimization space is significantly increasing. Therefore, researching high-quality 3D native instead of pesudo 3D physical design has become even more important. This paper reviews recent advancements and persistent challenges in 3D physical design, focusing on F2F bonding technologies. Then, this paper discusses several issues that still require further research and some overlooked problems, with the hope of helping researchers develop higher-quality 3D native physical design tools in the future.

Clock skew scheduling (CSS) is a well-known technique that improves design timing slack by adjusting clock latency to flipflops. CSS requires obtaining timing path information between sequential elements (including flip-flops and I/O ports), known as sequential graph extraction, which is the most time-consuming part of advanced CSS. In this paper, to quickly identify the potential of clock skew in slack optimization, we propose an iterative CSS algorithm that leverages timing propagation to facilitate sequential graph extraction. Then, we provide a comprehensive skew calculation method that considers multiple clock latency constraints, obtaining the target latency of each flip-flop. Finally, we present slack optimization techniques to achieve the target latencies. Our algorithm achieves a $49.11 \times$ speedup compared to the advanced CSS algorithm based on partial graph extraction, reducing 90.05% of the extracted edges. Compared to a state-of-the-art CSS-based slack optimization methodology, our algorithm delivers a $27.01 \times$ speedup with superior slack improvement.

Fault simulation targeting functional patterns emerges as an essential mechanism within functional safety, crucial for validating the effectiveness of safety mechanisms. The acceleration of fault simulation for functional patterns is imperative for boosting the efficiency and adaptability of functional safety verification, presenting a significant yet unresolved challenge. In the paper, we propose an efficient fault simulator for functional patterns, utilizing three techniques including fault filtering, fault grouping, and CPU-based parallelism. The integration of these three techniques, tailored to the characteristics of functional patterns, reduces the runtime of fault simulation from different perspectives. The experimental results show that on a 48-core system, an average 79x speedup can be achieved by our parallel fault simulator against a commercial tool.

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.

By leveraging the power of open-source software, the EDA tool offers a cost-effective and flexible solution for designers, researchers, and hobbyists alike. Open-source EDA promotes collaboration, innovation, and knowledge sharing within the EDA community. It emphasizes the role of the toolchain in accelerating the development of electronic systems, reducing design costs, and improving design quality. This paper presents an open-source EDA project, iEDA, aiming to build a basic infrastructure for EDA technology evolution and closing the industrial-academic gap in the EDA area. As the foundation for developing EDA tools and researching EDA algorithms and technologies, iEDA is mainly composed of file system, database, manager, operator and interface. To demonstrate the effectiveness of iEDA, we implement and tape out four chips of different scales (from 700k to 500M gates) on different process nodes (110nm and 28nm) with iEDA. iEDA is publicly available on the project home page https://github.com/OSCC-Project/iEDA.

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.

In modern IC design, routing significantly impacts chip performance, power, area, and design iteration count. Critical challenges in routing include generating a rectilinear Steiner minimum tree (RSMT) for each net and handling routing resources among nets. Due to limited resources and net order, congestion is inevitable in VLSI circuit routing. Most competitive routers address congestion after routing without prior net guidance, leading to difficulty in managing resources among nets. We suggest introducing a net resource allocation step to tackle routing and congestion as a potentially desirable initial routing stage. Firstly, we introduce the net region probability density (NRPD) concept to achieve suitable net resource allocation. Using a prior NRPD, we model the resource allocation problem as linear programming (LP). We solve the LP problem and obtain a posterior NRPD for each net on each grid. Based on the posterior NRPD and congestion map, we introduce a cost scheme to guide net routing. This cost scheme supports a weighted RSMT construction technique for better topological solutions. We propose an iterative method for global routing and track assignment, improving detailed routing quality and optimizing design rule violations. Experimental results show the effectiveness of net resource allocation and demonstrate the superior performance of our router over OpenROAD's router across multiple metrics.

IR drop analysis has become a computationally challenging problem with the shrinking of advanced process nodes. Solving the IR drop problem is time-consuming and an accurate and fast IR drop calculator is crucial for shortening the design cycle. In this work, we introduce an innovative IR drop calculation framework based on the conjugate gradient method and iAFFUNet network. iAFFUNet incorporates the UNet structure with the iterative attention feature fusion (iAFF) blocks to refine conventional approaches of feature concatenation and fusion. iAFF blocks employ multi-scale channel attention modules to enhance feature representation. Furthermore, we leverage intermediate results from the conjugate gradient method as augmented features and utilize graph attention networks for initial value calculation, thereby expediting the iteration process. Alternatively, the matrix operation process can be further accelerated using GPU optimization. During the training phase, we adopt a transfer learning strategy by fine-tuning limited real circuit datasets based on a pre-trained model obtained from training with a substantial amount of synthetic circuit datasets. Experimental results on the ICCAD 2023 contest real hidden testcases under the Nangate 45nm process node show that our model achieves an average improvement of 48.7% and 53.9 % in MAE compared to the contest's champion and the second place, respectively. Additionally, our model achieves a 39.8% reduction in CPU runtime compared to the champion of the contest.

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.

Instance level post-routing timing analysis at the placement stage is of great importance for timing optimization such as gate sizing and cell movement etc. Determining the timing bottlenecks accurately and in a fast way has become significantly meaningful for accelerating the timing closure since the time-consuming iteration cycle. In this work, we propose an instance-level timing prediction framework to identify the critical cells of post-routing at the placement stage, which constructs a pixel level image-to-image timing hotspot map translation task using an encoder-decoder based Res-UNet. The network framework combines the strengths of residual learning and basic U-Net, helping in collecting the local and global features of the entire layout of the circuit over different spatial scales. Experimental results on ISCAS’89 benchmark circuits under the 28nm process node demonstrated that with the proposed model, the average prediction accuracy of the critical cells classification achieves 90.7% for unseen designs in terms of the value of the F1-score. Moreover, the framework has achieved a speedup of three orders of magnitude compared with the conventional design flow.

In advanced process, electromagnetic coupling among interconnect wires plays an increasingly important role in signoff analysis. For VLSI chip design, the requirement of fast and accurate capacitance extraction is becoming more and more urgent. And the critical step of extracting capacitance among interconnect wires is solving electric field. However, due to the high computational complexity, solving electric field is extreme timing-consuming. The Galerkin boundary element method (GBEM) was used for capacitance extraction in [2]. In this paper, we are going to use some mathematical theorems to analysis its error. Furthermore, with the error estimation of the Galerkin method, we design a boundary partition strategy to fit the electric field attenuation. It is worth to mention that this boundary partition strategy can greatly reduce the number of boundary elements on the promise of ensuring that the error is small enough. As a consequence, the matrix order of the discretization equation will also decrease. We also provide our suggestion of the calculation of the matrix elements. Experimental analysis demonstrates that, our partition strategy obtains a good enough result with a small number of boundary elements.

Die-to-die (D2D) placement is a more challenging stage in achieving higher performance with complex constraints, critically impacting timing, power, yield, cost, etc. Existing placers often rely on indirect objectives (e.g., considering cut sizes in tier assignment), which can lead to a loss of the overall solution space utilization and may even deviate from the actual objective. To address this issue, this paper leverages the natural dominance relationship between decision variables to transform the original problem into a bilevel programming problem equivalently. Additionally, an alternating optimization framework is introduced to enhance the exploration of the overall solution space. On the one hand, we propose two tier optimization operators for simultaneous optimization of wirelength and #terminal in global and detailed perspectives; On the other hand, we present a near-optimal terminal legalization algorithm following an efficient multi-tier co-placement. Compared with the top three winners of the ICCAD'22 contest, our placer achieves 4.33%, 4.42%, and 5.88% smaller wire-length, 79.61 %, 16.74%, and 15.76% fewer #terminal and competitive runtime. Moreover, our placer always uses the fewest #terminal and achieves amazing wirelength reduction when the terminal size changes.

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.

Sparse direct solvers provide vital functionality for a wide variety of scientific applications. The dominated part of the sparse direct solver, LU factorization, suffers a lot from the irregularity of sparse matrices. Meanwhile, the specific characteristics of sparse solvers in circuit simulation and unique sparse pattern of circuit matrices provide more design spaces and also great challenges. In this paper, we propose a sparse solver named FLU and re-examine the performance of LU factorization from the perspectives of vectorization, parallelization, and data locality. To improve vectorization efficiency and data locality, FLU introduces a register-level supernode computation method by delicately manipulating data movement. With alternating multiple columns computation, FLU further reduces the off-chip memory accesses greatly. Furthermore, we implement a fine-grained elimination tree based parallelization scheme to fully exploit task-level parallelism. Compared with PARDISO and NICSLU, experimental results show that FLU achieves a speedup up to 19.51 × (3.86 × on average) and 2.56 × (1.66 × on average) on Intel Xeon respectively.

The complexity and diversity of big data and AI workloads make understanding them difficult and challenging. This paper proposes a new approachto modelling and characterizing big data and AI workloads. We consider each big data and AI workload as a pipeline of one or more classes of units of computation performed on different initial or intermediate data inputs. Each class of unit of computation captures the common requirements while being reasonably divorced from individual implementations, and hence we call it a data motif. For the first time, among a wide variety of big data and AI workloads, we identify eight data motifs that take up most of the run time of those workloads, including Matrix, Sampling, Logic, Transform, Set, Graph, Sort and Statistic. We implement the eight data motifs on different software stacks as the micro benchmarks of an open-source big data and AI benchmark suite --- BigDataBench 4.0 (publicly available from http://prof.ict.ac.cn/BigDataBench), and perform comprehensive characterization of those data motifs from perspective of data sizes, types, sources, and patterns as a lens towards fully understanding big data and AI workloads. We believe the eight data motifs are promising abstractions and tools for not only big data and AI benchmarking, but also domain-specific hardware and software co-design.

Sparse Matrix-vector Multiplication (SpMV) is an important computation kernel widely used in HPC and data centers. The irregularity of SpMV is a well-known challenge that limits SpMV’s parallelism with vectorization operations. Existing work achieves limited locality and vectorization efficiency with large preprocessing overheads. To address this issue, we present the Compressed Vectorization-oriented sparse Row (CVR), a novel SpMV representation targeting efficient vectorization. The CVR simultaneously processes multiple rows within the input matrix to increase cache efficiency and separates them into multiple SIMD lanes so as to take the advantage of vector processing units in modern processors. Our method is insensitive to the sparsity and irregularity of SpMV, and thus able to deal with various scale-free and HPC matrices. We implement and evaluate CVR on an Intel Knights Landing processor and compare it with five state-of-the-art approaches through using 58 scale-free and HPC sparse matrices. Experimental results show that CVR can achieve a speedup up to 1.70 × (1.33× on average) and a speedup up to 1.57× (1.10× on average) over the best existing approaches for scale-free and HPC sparse matrices, respectively. Moreover, CVR typically incurs the lowest preprocessing overhead compared with state-of-the-art approaches.

Sparse Matrix-Vector Multiplication (SpMV) is an essential computation kernel for many data-analytic workloads running in both supercomputers and data centers. The intrinsic irregularity in SpMV is challenging to achieve high performance, especially when porting to new architectures. In this paper, we present our work on designing and implementing efficient SpMV algorithms on Sunway, a novel architecture with many unique features. To fully exploit the Sunway architecture, we have designed a dual-side multi-level partition mechanism on both sparse matrices and hardware resources to improve locality and parallelism. On one hand, we partition sparse matrices into blocks, tiles, and slices for different granularities. On the other hand, we partition cores in a Sunway processor into fleets, and further dedicate part of cores in a fleet as computation and I/O cores. Moreover, we have optimized the communication between partitions to further improve the performance. Our scheme is generally applicable to different SpMV formats and implementations. For evaluation, we have applied our techniques atop a popular SpMV format, CSR. Experimental results on 18 datasets show that our optimization yields up to 15.5x (12.3x on average) speedups.