With the advancement of 3D IC technology, multilayer chip stacking enables improved performance and reduced power consumption, albeit at the cost of increased design complexity. In 3D IC designs, soft modules are also adopted to enable flexible floorplanning across multiple dies. To preserve module integrity and simplify interconnects, the standard cells and macros within the same module are typically constrained to be placed on the same layer and thus using the same technology. In addition, determining an appropriate shape and placement location for each soft module is critical for minimizing wirelength. This paper presents the first technology-aware 3D placement framework for mixed-size designs that incorporates region planning for soft modules. It combines an analytical placement engine with an integer linear programming (ILP)-based region planning strategy to handle the flexible nature of soft modules. To further enhance placement flexibility while limiting region complexity, the ILP formulation identifies an optimal L-shaped or rectangular region for each soft module. Experimental results demonstrate that, compared to a baseline approach, our flow achieves over 21% wirelength reduction, with only a 5% overhead compared to placement without the soft module constraint.

Despite significant advancements in deep classification techniques and in-lab automatic optical inspection (AOI) models for long-tailed or highly imbalanced data, applying these approaches to real-world IC defect classification tasks remains challenging. This difficulty stems from two primary factors. First, real-world conditions, such as the high yield-rate requirements in the IC industry, result in data distributions that are far more skewed than those found in general public imbalanced datasets. Consequently, classifiers designed for open imbalanced datasets often fail to perform effectively in real-world scenarios. Second, real-world samples exhibit a mix of class-specific attributes (e.g., defect types) and class-agnostic, domain-related features (e.g., design characteristics of product lines). This complexity adds significant difficulty to the classification process, particularly for highly imbalanced datasets. To address these challenges, this paper introduces the IC-Defect-14 dataset, a large, highly imbalanced IC defect image dataset sourced from AOI systems deployed in real-world IC production lines. This dataset is characterized by its unique “intra-class clusters” property, which presents two major challenges: large intra-class diversity and high inter-class similarity. These characteristics, rarely found simultaneously in existing public datasets, significantly degrade the performance of current state-of-the-art classifiers for highly imbalanced data. To tackle this challenge, we propose the Regional Channel Attention-based Multi-Expert Network (ReCAME-Net). This network follows a multi-expert classifier framework and integrates a regional channel attention module, metric learning losses, a hard category mining strategy, and a knowledge distillation procedure. Extensive experimental evaluations demonstrate that ReCAME-Net outperforms previous state-of-the-art models on the IC-Defect-14 dataset while maintaining comparable performance and competitiveness on general public datasets. Our resources can be found at https://github.com/YoursEver/ReCAME-Net.

Mixed-cell-height VLSI circuits are widely used to meet various design requirements. Due to design for manufacturability (DFM) considerations such as layout-dependent effects (LDEs), drain-to-drain abutment (DDA), and pattern coloring for multiple patterning, different spacings between adjacent cells affect performance, modeled as discrete spacing costs. A state-of-the-art dynamic programming (DP) approach can address this problem but can only handle a few cell rows simultaneously due to its high complexity. In this article, we propose a novel DP algorithm that can solve the problem optimally and more efficiently. Additionally, several optimality-preserving reduction techniques are employed to derive full-chip optimal solutions for large-scale designs. Experimental results demonstrate that the proposed approach significantly outperforms existing methods in terms of total spacing cost and total displacement.

Optical networks-on-chips (ONoCs), which adopt optical waveguides, microring resonators (MRRs), and the wavelength division multiplexing (WDM) scheme to transmit optical signals, serve as promising solutions for integrating multi- and many-core systems to provide high-bandwidth, low-latency, and low-power on-chip communication. To minimize the insertion loss of a wavelength-routed ONoC (WRONoC) during physical implementation, existing studies either adopt conventional standard cell placement techniques or maximally avoid waveguide crossings; however, all of them ignore the fact that the critical path suffering from the maximum insertion loss dominates the overall power efficiency and system performance. In this work, we propose CPONoC, a critical-path-aware physical implementation tool for WRONoCs. Different from existing studies, CPONoC focuses on minimizing the insertion loss of the critical path using an iterative crossing-aware force-directed method, and it is compatible with different representative logic schemes and input configurations. Compared to the state-of-the-art design automation tools, CPONoC achieves an average reduction of 9.6% in maximum insertion loss.

Package design has become increasingly complex with the evolution of technology nodes and heterogeneous integration. To optimize timing performance and signal integrity, it is essential to separate different pairs of geometrically adjacent nets with distinct spacing values, which is referred to as the paired-spacing constraint. This paper presents the first free-assignment package routing algorithm flow considering the paired-spacing constraint. To minimize the routing resource demand and overall wirelength, we propose a dynamic programming-based net ordering method to maximize the number of nets with the same/similar spacing rules positioned next to each other. In addition, the free-assignment routing problem is elegantly solved with a minimum-cost maximum-flow problem on a delicately designed graph model. Experimental results show that the proposed flow can achieve 100% routability for the adopted industrial-modified benchmarks. In contrast, even with modifications to superficially consider paired spacings, a classic model experiences significant routability degradation.

As technology nodes advance and feature sizes shrink, wire resistance grows significantly, resulting in a substantial rise in circuit delays and reliability risks. Via pillars made up of multiple layers of parallel metals and vias can mitigate delay and electromigration by offering lower resistance and current density. However, it has become more and more challenging due to the increasing demand for inserting via pillars and the increasing density of power and ground (P/G) stripes in the lower layers. Moreover, an improperly designed via pillar structure can also block access to adjacent pins and worsen routability. In this paper, we propose comprehensive via pillar design strategies simultaneously considering flexible pin base selection, obstacle avoidance, and pin accessibility optimization. In addition, due to the high via pillar insertion rates advanced nodes target, we propose a congestion-aware via pillar design flow for high-density and closely positioned via pillars. Experimental results show that compared with a state-of-the-art work, our flow eliminates the design rule violations (DRVs) by 99% after via pillar insertion. In addition, by considering the pin accessibility of neighboring pins, our work also reduces over 98% DRVs after detailed routing.

Directed self-assembly (DSA) using block copolymers (BCP) has become a very promising technique for the fabrication of via layers in integrated circuits with the dramatic shrink of feature sizes and great increase in circuit complexity. Since the cylindrical DSA suffers from the drawbacks of fixed via pitch in a single template and great displacement error due to process variation, lamellar DSA in combination with the self-aligned via (SAV) process becomes an alternative that may lead to better manufacturability. Many studies have investigated design methodologies for via/contact layer fabrication with cylindrical block copolymers, but there is only one existing work focusing on the guiding template design problem for lamellar DSA. However, this work only considers one-dimensional lamellar guiding templates, while adopting two-dimensional templates can resolve more template conflicts. This paper presents the first work of multi-row guiding template design for lamellar DSA with SAV technology and multiple patterning lithography (MPL). To tackle the problem, we enumerate all guiding template shapes for a given via layout by considering the design constraints in the target process and design flexibility with dummy vias. Two methods are proposed afterward. The first one is a method based on integer linear programming (ILP), and the second one is a heuristic method. The experimental results show that the optimal solutions can be obtained by solving the ILP formulation, and the heuristic method can obtain near-optimal solutions with much less runtime.

Using multiple power domains is a common technique to achieve significant power savings in modern designs. However, providing power to cross-domain cells is challenging at advanced technology nodes, due to strict IR drop constraints and competition for routing resources between secondary power routing and signal routing. Despite its importance, this issue has received limited attention in recent literature. In this paper, we propose a detailed placement method that accounts for secondary power routing. Our approach employs an integer linear programming (ILP) model, complemented by targeted adjustments to the placement of cross-domain cells, to optimize the efficiency of secondary power routing. We validate our results with commercial design tools, showing that our approach effectively improves secondary power routing performance by reducing the wirelength of the secondary power distribution network (PDN) and decreasing violations due to secondary PDN constraints.

FinFlex standard cells have been proposed in sub-3 nm process nodes by TSMC to offer great design flexibility and a good trade-off between performance, power, and area efficiency. In the FinFlex technology, each cell type has a number of versions, varying in cell heights and threshold voltages, enabling flexible cell substitution for placement optimization. This paper presents the first work in the literature on standard cell legalization for the FinFlex technology, addressing cell version substitution, power efficiency, and minimum implant area (MIA) constraints. Our proposed algorithm comprises three stages: intra-row violationaware pre-processing considering timing and power levels, directed acyclic graph-based initial legalization with cell version substitution, and dynamic programming-based inter-row violation removal. Experimental results show the superior performance of our approach over a baseline using state-of-the-art techniques.

The "CAD Contest at ICCAD" is a challenging, multi-month, research and development competition, focusing on advanced, real-world problems in the field of electronic design automation (EDA). Since 2012, the contest has been publishing many sophisticated circuit design problems, from system-level design to physical design, together with industrial benchmarks and solution evaluators. Contestants can participate in one or more problems provided by EDA/IC industry. The winners will be awarded at an ICCAD special session dedicated to this contest. Every year, the contest attracts more than a hundred teams, fosters productive industry-academia collaborations, and leads to hundreds of publications in top-tier conferences and journals. The 2025 CAD Contest has 247 teams from all over the world, which generates the highest participation record. Moreover, the problems of this year cover state-of-the-art EDA research trends such as hardware trojan detection, design optimization with multibit flip-flops, and performance-driven incremental placement optimization from well-known EDA/IC companies. We believe the contest keeps enhancing impact and boosting EDA researches.

Dynamic programming (DP) plays a crucial role as the backbone of many core optimization algorithms across the physical design flow, including placement, clock tree synthesis, and routing. However, DP methods with quadratic or higher time complexities often face scalability challenges in large-scale designs. In this work, we propose a novel GPU-accelerated DP technique that can be broadly adaptable to various DP-based algorithms. As a case study, we present a GPU-accelerated detailed placement framework targeting mixed-cell-height designs, built upon an optimal DP formulation. By leveraging the massive parallelism of modern GPUs and incorporating advanced cost accumulation strategies, our approach consistently delivers optimal placement solutions while achieving an average runtime reduction of 96.6% and peak speedups exceeding 1600×. This work demonstrates the potential of GPU acceleration not only to overcome runtime bottlenecks but also to enhance design quality in advanced physical design tasks.

Traditional packaging routers are typically limited to 90- and 135-degree routing angles. However, with the advancement in advanced packaging technologies and the increasing demand for a higher number of I/Os, any-angle routing has become a promising solution thanks to its ability to explore a larger solution space and reduce overall wirelength. Therefore, we proposed an any-angle routing framework for die-to-substrate connections. First, the proposed routing graph enables accurate estimation of routing resource utilization in the global routing stage. After the global routing stage, we introduce two wire-length optimization strategies: (1) a concurrent adjustment of access points to reduce total wirelength by considering all nets simultaneously, and (2) a dynamic programming-based method to minimize the number of wire segments in each single net. Experimental results demonstrate that our two-stage refinement strategies achieve superior routing quality compared to the global routing result.

Recent advances in VLSI fabrication technology have led to die shrinkage and increased layout density, creating an urgent demand for advanced hotspot detection techniques. However, by taking an object detection network as the backbone, recent learning-based hotspot detectors learn to recognize only the problematic layout patterns in the training data. This fact makes these hotspot detectors difficult to generalize to real-world scenarios. We propose a novel lithography simulator-powered hotspot detection framework to overcome this difficulty. Our framework integrates a lithography simulator with an object detection backbone, merging the extracted latent features from both the simulator and the object detector via well-designed cross-attention blocks. Consequently, the proposed framework can be used to detect potential hotspot regions based on 1) the variation of possible circuit shape deformation estimated by the lithography simulator and 2) the problematic layout patterns already known. To this end, we utilize RetinaNet with a feature pyramid network as the object detection backbone and leverage LithoNet as the lithography simulator. Extensive experiments demonstrate that our proposed simulator-guided hotspot detection framework outperforms the previous state-of-the-art methods on real-world data.

State-of-the-art studies on quantum layout synthesis have proposed various approaches based on the assumption that the input circuit is only composed of single-qubit and two-qubit gates. This assumption greatly simplifies the layout synthesis problem, and thus they only require ensuring that all controlled-NOT (CNOT) gates satisfy the hardware constraints imposed by a given coupling graph. However, during the design of quantum circuits, multi-controlled Toffoli (MCT) gates are usually used to better characterize the function of the circuits. Directly decomposing them into single and two-qubit gates with a fixed routine ignores the flexibility and optimization opportunity provided by various decomposition (i.e., logic synthesis) possibilities and thus suffers from sub-optimal results. This article proposes a co-optimization approach for quantum logic and layout synthesis. The MCT gates are first decomposed into Toffoli gates, and an efficient qubit mapping checking process is proposed to optimally solve the SWAP-free layout synthesis problem by automatically determining the decomposition result of each Toffoli gate. If a SWAP-free result cannot be found, the proposed algorithm flow is then used to obtain a solution that minimizes the total cost that simultaneously counts the cost caused by the different decomposition methods for Toffoli gates and the cost induced by SWAP gates. Compared with a state-of-the-art method, the proposed approach reduces the number of additional CNOT gates by 16% with around 25X runtime speedup for the cases with SWAP-free solutions, which cannot be obtained without the co-optimization approach.

Pin access has become one of the most significant challenges in large-scale full-chip routing due to the continuous reduction in feature sizes and the increasing complexity of designs. The conventional standard cell layout synthesis approaches usually optimize pin accessibility by maximizing pin lengths and access points. However, these predetermined pin patterns greatly occupy routing resources and may contrarily degrade routability. To address this problem, this paper proposes the first work of concurrent detailed routing with pin pattern re-generation to achieve ultimate pin access optimization. A pseudopin extraction and routing technique is proposed that can secure one access point for each input/output pin while allowing the remaining access points to be routable by other nets. The experimental results demonstrate that the proposed method can resolve 89% of local regions that are unroutable with original layout patterns without compromising power and timing performances.

The "CAD Contest at ICCAD" is a challenging, multi-month, research and development competition, focusing on advanced, real-world problems in the field of electronic design automation (EDA). Since 2012, the contest has been publishing many sophisticated circuit design problems, from system-level design to physical design, together with industrial benchmarks and solution evaluators. Contestants can participate in one or more problems provided by EDA/IC industry. The winners will be awarded at an ICCAD special session dedicated to this contest. Every year, the contest attracts more than a hundred teams, fosters productive industry-academia collaborations, and leads to hundreds of publications in top-tier conferences and journals. The 2024 CAD Contest has 221 teams from all over the world, which generates the highest participation record. Moreover, the problems of this year cover state-of-the-art EDA research trends such as logic optimization, multibit flip-flop, and Machine Learning (ML) for EDA from well-known EDA/IC companies. We believe the contest keeps enhancing impact and boosting EDA researches.

With the announcement of the most advanced silicon spin quantum-bit (qubit) chip by Intel, silicon-based quantum circuit manufacturing technology has shown the superior potential to realize quantum computing to other technologies because of the mature semiconductor manufacturing technologies and the compatibility with electronics. Due to the bottleneck in scalability caused by interconnections in silicon-based quantum circuits, crossbar architectures serve as one of the most promising solutions for circuitry implementation. This paper proposes the first satisfiability modulo theories (SMT) formulation to optimally solve the layout synthesis problem by simultaneously performing scheduling, mapping, and routing for silicon-based quantum systems with a specific crossbar architecture. The experiments demonstrate that the proposed method can effectively generate layout synthesis results with minimal usage of swap and shuttle gates within the shortest circuit depths, and the solutions greatly outperform those derived from a state-of-the-art work.

Propelled by aggressive technology scaling, adopting mixed-cell-height design in VLSI circuits has made conventional single row-based cell legalization techniques obsolete. Furthermore, the vertical abutment constraint (VAC) among cells on consecutive rows emerges as an advanced design requirement, which has rarely been considered because the power/ground rails were sufficiently tall in conventional process nodes to isolate cells on different rows. Although there have been a number of studies on mixed-cell-height legalization, most of them cannot be trivially extended to well-tackle the general VAC due to the analytical optimization scheme. To address these issues, this work proposes the first mixed-cell-height legalization algorithm that addresses the general inter-row cell abutment constraint (i.e., VAC). The experimental results show that the proposed algorithm outperforms previous mixed-cell-height legalization works, even in the absence of the VAC. Upon applying the VAC, our algorithm offers superior performance and delivers promising results.

As the feature size decreases, leakage power consumption becomes an important target in the design. Using multiple threshold voltages (VTs) in cell-based designs is a popular technique to simultaneously optimize circuit timing and minimize leakage power. However, an arbitrary cell placement result of a multi-VT design may suffer from many design rule violations induced by the Minimum-Implant-Area (MIA) rule, and thus it is necessary to take the MIA rules into consideration during the detailed placement stage. The state-of-the-art works on detailed placement comprehensively tackling MIA rules either disallow VT change or only allow reducing cell VTs to avoid timing degradation. However, these limitations may either result in larger cell displacement or cause overhead in leakage power. In this paper, we propose an optimization framework of VT reassignment and detailed placement to simultaneously consider MIA rules and leakage power minimization under timing constraints. Experimental results show that compared with the state-of-the-art works, the proposed framework can efficiently achieve better trade-off between leakage power and cell displacement.

With continuous shrinking of process nodes, semiconductor manufacturing encounters more and more serious inconsistency between designed layout patterns and resulted wafer images. Conventionally, examining how a layout pattern can deviate from its original after complicated process steps, such as optical lithography and subsequent etching, relies on computationally expensive process simulation, which suffers from incredibly long runtime for large-scale circuit layouts, especially in advanced nodes. In addition, being one of the most important and commonly adopted resolution enhancement techniques, optical proximity correction (OPC) corrects image errors due to process effects by moving segment edges or adding extra polygons to mask patterns, while it is generally driven by simulation or time-consuming inverse lithography techniques (ILTs) to achieve acceptable accuracy. As a result, more and more state-of-the-art works on process simulation or/and OPC resort to the fast inference characteristic of machine/deep learning. This paper reviews these data-driven approaches to highlight the challenges in various aspects, explore preliminary solutions, and reveal possible future directions to push forward the frontiers of the research in design for manufacturability.

With the advance of technology nodes, via fabrication in a dense design becomes a difficult challenge, and the directed self-assembly (DSA) technology has shown its great potential in contact/via layer manufacturing. As many studies consider the guiding template design problem for cylindrical DSA, lamellar DSA with the self-aligned via process emerges as an alternative with better yield and design flexibility. However, the new process also imposes new constraints on template design, making an arbitrary contact/via layout suffer from unsatisfactory manufacturability. In this paper, we present the first work on detailed routing considering lamellar DSA guiding template design and mask assignment with double patterning lithography (DPL) to minimize the numbers of unmanufacturable vias and short templates. In the proposed router, we construct a conflict graph and a via forbidden map for routing guidance and via mask assignment. A prerouting methodology is developed to obtain better via distribution in critical areas and preserve routing space for further detailed routing. After that, a short template-aware detailed routing approach routes the rest of the nets and an existing template design engine is adopted for optimal template design and mask assignment. The experimental results indicate that compared to a conventional A*search-based router, our approach can generate conflict-free template design results and achieve 35% reduction in short templates.

With the development of advanced process technology, the electrical characteristic variation of MOSFET transistors has been seriously influenced by layout dependent effect (LDEs). Due to these LDEs, two cells of specific cell types may suffer from timing degradation when they are adjacently and closely placed with specific orientations. To mitigate the timing risk of critical paths and thus optimize the performance of a target design, this work proposes a dynamic programming (DP)-based method for multi-row-height detailed placement with cell flipping and cell shifting. Experimental results shows the efficiency and effectiveness of the proposed DP-based approach.

Mixed-cell-height VLSI circuits have been popularly adopted to meet different design requirements. Due to various design for manufacturability (DFM)-related considerations, such as layout dependent effects (LDEs), drain-to-drain abutment (DDA), and pattern coloring for multiple patterning, different spacings in terms of placement sites between each pair of adjacent cells may result in different performances, which are usually modeled as discrete spacing costs. To tackle such a discrete and spacing cost-aware detailed placement problem for mixed-cell-height designs, a state-of-the-art dynamic programming (DP)-based approach can only tackle few cell rows simultaneously due to its extremely high complexity. In this paper, we propose a novel DP algorithm that can optimally and much efficiently solve the problem. In addition, several optimality-preserving reduction techniques are also proposed to enable the possibility of full-chip optimal solution derivation for large-scale designs. Experiments considering two DFM considerations show that the proposed approach greatly outperforms existing studies in terms of the total spacing cost, the total displacement, and runtime.

Directed self-assembly (DSA), which uses the segregation nature after an annealing process of block co-polymer (BCP) to generate tiny feature shapes, becomes one of the most promising next generation lithography technologies. According to the different proportions of the two monomers in an adopted BCP, either cylinders or lamellae can be generated by removing one of the two monomers, which are respectively referred to as cylindrical DSA and lamellar DSA. In addition, guiding templates are required to produce trenches before filling BCP such that the additional forces from the trench walls regulate the generated cylinders/lamellae. Both the two DSA technologies can be used to generate contact/via patterns in circuit layouts, while the practices of designing guiding templates are quite different due to different manufacturing principles. This paper reviews the existing studies on the guiding template design problem for contact/via hole fabrication with the DSA technology. The design constraints are differentiated and the design methodologies are respectively introduced for cylindrical DSA and lamellar DSA. Possible future research directions are finally suggested to further enhance contact/via manufacturability and the feasibility of adopting DSA in semiconductor manufacturing.

Due to continuously shrunk feature sizes and increased design complexity, the difficulty in pin access becomes one of the most critical challenges in large-scale full-chip routing. State-of-the-art pin access-aware detailed routing techniques suffer from either the ordering problem of the sequential routing scheme or the inflexibility of pre-determining an access point for each pin. Some other routing-related studies create pin extensions with Metal-2 metal segments to optimize pin accessibility; however, this strategy may not be practical without considering the contemporary routing flow. This paper presents a pin access-oriented concurrent detailed routing approach conducted after the track assignment stage. The core detailed routing engine is based on an integer linear programming (ILP) formulation, which has lower complexity and can flexibly tackle multi-pin nets compared to an existing formulation. Besides, to maximize the free routing resource and to keep the problem size tractable, a pre-processing flow trimming redundant metals and inserting assistant metals is developed. The experimental results show that compared to a state-of-the-art academic router, the proposed concurrent scheme can effectively derive good results with fewer design rule violations and less runtime.

Lamellar directed self-assembly (DSA) technology in combination with the self-aligned via (SAV) process has emerged as a novel and promising choice for via/contact layer fabrication, where a via between Metal-$x$and Metal-$(x+1)$is generated at the intersection of a wire segment on Metal-$(x+1)$and a rectangular and perpendicular guiding template. Compared to the highly investigated cylindrical DSA, lamellar DSA does not suffer from the overlay error of generated holes and thus can have better yield, and it also benefits from the better flexibility of various via pitches a single template can produce. A state-of-the-art work has addressed the guiding template design problem for the new process, and an integer linear programming (ILP) formulation that can optimally solve the problem as well as a simple heuristic approach are proposed. However, solving the ILP formulation is time consuming, and the heuristic method suffers from unignorable degradation in solution quality due to several algorithm deficiencies. In this article, we propose an enhanced and efficient template design algorithm flow for the lamellar DSA and SAV process by using graph monomorphism for pattern conflict check in multiple patterning lithography. Experimental results show that the proposed flow can greatly reduce the numbers of conflicts and short templates and is almost as efficient as the existing heuristic approach.

Two-dimensional (2-D) global routing followed by layer assignment is a common and popular strategy to obtain a good tradeoff between runtime and routing performance. Yet, the huge gap between 2-D routing patterns and the final 3-D routing paths often results in inevitable overflow after layer assignment. State-of-the-art (SOTA) studies on layer assignment usually adopt dynamic programming-based approaches to sequentially find an optimal solution for each net in terms of overflow or/and the number of vias. However, a fixed assignment ordering severely restricts the solution space, and the distributed overflows can hardly be resolved with any existing refinement approach. This article proposes a novel layer assignment framework that concurrently considers all the wire segments of nets and iteratively assigns them from the lowest available layer to the highest one. The concurrent scheme facilitates the maximal utilization of routing resource on each layer, contributing to an effective rerouting procedure that greatly reduces inevitable overflows. Based on the proposed framework, we further propose an obstacle-aware strategy that can mitigate obstacle-induced inevitable overflows in the original framework. Experimental results show that compared to an implemented sequential layer assignment approach based on SOTA techniques and refined by the well-known overflow/congestion reduction rip up and rerouting procedure, the proposed concurrent layer assignment framework (COALA) brings great improvements in the overflow reduction and runtime efficiency, which shows the significant advantage of the concurrent layer assignment scheme over sequential methods. The improvement is also verified in detailed routing, where the proposed COALA framework contributes to sparser routing results with fewer vias and design rule violations (DRVs).

Learning-based presimulation (i.e., layout-to-fabrication) models have been proposed to predict the fabrication-induced shape deformation from an IC layout to its fabricated circuit. Such models are usually driven by pairwise learning, involving a training set of layout patterns and their reference shape images after fabrication. However, it is expensive and time consuming to collect the reference shape images of all layout clips for model training and updating. To address the problem, we propose a deep-learning-based layout novelty detection scheme to identify novel (unseen) layout patterns, which cannot be well predicted by a pretrained presimulation model. We devise a global–local novelty scoring mechanism to assess the potential novelty of a layout by exploiting two subnetworks: 1) an autoencoder and 2) a pretrained presimulation model. The former characterizes the global structural dissimilarity between a given layout and training samples, whereas the latter extracts a latent code representing the fabrication-induced local deformation. By integrating the global dissimilarity with the local deformation boosted by a self-attention mechanism, our model can accurately detect novelties without the ground-truth circuit shapes of test samples. Based on the detected novelties, we further propose two active-learning strategies to sample a reduced amount of representative layouts most worthy to be fabricated for acquiring their ground-truth circuit shapes. Experimental results demonstrate: 1) the effectiveness of our layout novelty detection algorithm and 2) the ability of our active-learning strategies in selecting representative novel layouts for keeping a learning-based presimulation model updated.

Layout synthesis in quantum circuits maps the logical qubits of a synthesized circuit onto the physical qubits of a hardware device (coupling graph) and complies with the hardware limitations. Existing studies on the problem usually suffer from intractable formulation complexity and thus prohibitively long runtimes. In this paper, we propose an efficient layout synthesizer by developing a satisfiability modulo theories (SMT)-based qubit mapping checker. The proposed qubit mapping checker can efficiently derive a SWAP-free solution if one exists. If no SWAP-free solution exists for a circuit, we propose a divide-and-conquer scheme that utilizes the checker to find SWAP-free sub-solutions for sub-circuits, and the overall solution is found by merging sub-solutions with SWAP insertion. Experimental results show that the proposed optimization flow can achieve more than 3000× runtime speedup over a state-of-the-art work to derive optimal solutions for a set of SWAP-free circuits. Moreover, for the other set of benchmark circuits requiring SWAP gates, our flow achieves more than 800× speedup and obtains near-optimal solutions with only 3% SWAP overhead.

Microfluidic lab-on-chips offer promising technology for the automation of various biochemical laboratory protocols on a minuscule chip. Sample preparation (SP) is an essential part of any biochemical experiments, which aims to produce dilution of a sample or a mixture of multiple reagents in a certain ratio. One major objective in this area is to prepare dilutions of a given fluid with different concentration factors, each with certain volume, which is referred to as the demand-driven multiple-target (DDMT) generation problem. SP with microfluidic biochips requires proper sequencing of mix-split steps on fluid volumes and needs storage units to save intermediate fluids while producing the desired target ratio. The performance of SP depends on the underlying mixing algorithm and the availability of on-chip storage, and the latter is often limited by the constraints imposed during physical design. Since DDMT involves several target ratios, solving it under storage constraints becomes even harder. Furthermore, reduction of mix-split steps is desirable from the viewpoint of accuracy of SP, as every such step is a potential source of volumetric split error. In this article, we propose a storage-aware DDMT algorithm that reduces the number of mix-split operations on a digital microfluidic lab-on-chip. We also present the layout of the biochip with -storage cells and their allocation technique for . Simulation results reveal the superiority of the proposed method compared to the state-of-the-art multi-target SP algorithms.

With the development of semiconductor technology nodes, the sizes of standard cells become smaller and the number of standard cells is dramatically increased to bring into more functionality in integrated circuits (ICs). However, the shrinking of standard cell sizes causes many problems of ICs such as timing, power, and electromigration (EM). To tackle these problems, a new style structural pre-route (SPR) is proposed. Such type of pre-route is composed of redundant parallel metals and vias so that the low resistance and the redundant sub-structures can improve timing and yield. But the large area overhead becomes the major problem of inserting such pre-routes all over a design. In this paper, we propose a machine learning-based approach to predict the insertability of SPRs for placed designs. In addition, we apply a pattern visualization method by using a guided backpropagation technique to see in depth of our model and identify the problematic layout features causing SPR insertion failures. The experimental results not only show the excellent performance of our model, but also show that avoiding generating the identified critical features during legalization can improve SPR insertability compared to a commercial SPR-aware placement tool.

The directed self-assembly and multiple patterning (DSA-MP) lithography has shown its great potential in fabricating via/contact layers in sub-10-nm technology nodes. Existing studies have shown that using two different block copolymer (BCP) materials can reduce conflict numbers among guiding templates compared with those only using a single BCP material. However, given an arbitrary via/contact layout, there may still be many conflicts in an optimized template design and mask assignment solution. In this article, we explore the possibility of via manufacturability improvement with dummy via insertion for DSA-MP. We also propose a post-decomposition optimization flow composed of four heuristics to further resolve conflicts. The experimental results show that our flow can efficiently and effectively reduce conflicts by inserting dummy vias.

We propose a deep learning-based data-driven framework consisting of two convolutional neural networks: 1) LithoNet that predicts the shape deformations on a circuit due to IC fabrication and 2) OPCNet that suggests IC layout corrections to compensate for such shape deformations. By learning the shape correspondences between pairs of layout design patterns and their scanning electron microscope (SEM) images of the product wafer thereof, given an IC layout pattern, LithoNet can mimic the fabrication process to predict its fabricated circuit shape. Furthermore, LithoNet can take the wafer fabrication parameters as a latent vector to model the parametric product variations that can be inspected on SEM images. Besides, traditional optical proximity correction (OPC) methods used to suggest a correction on a lithographic photomask is computationally expensive. Our proposed OPCNet mimics the OPC procedure and efficiently generates a corrected photomask by collaborating with LithoNet to examine if the shape of a fabricated circuit optimally matches its original layout design. As a result, the proposed LithoNet-OPCNet framework can not only predict the shape of a fabricated IC from its layout pattern but also suggests a layout correction according to the consistency between the predicted shape and the given layout. Experimental results with several benchmark layout patterns demonstrate the effectiveness of the proposed method.

With the continuous scaling down of process nodes, standard cells become much smaller and cell counts are dramatically increased. Pin accessibility becomes one of the major issues causing design rule violations (DRVs). To tackle this problem, many recent works apply machine-learning-based techniques to predict whether a local region has DRV or not by regarding global routing (GR) congestion and local pin density as the main features during the training process. Empirically, however, DRV occurrence is not necessary to be strongly correlated with the two features in advanced nodes. In this article, we propose the first work of deep-learning-based DRV prediction using pin pattern as our major feature to directly identify whether a DRV will exist or not due to bad pin accessibility of the given pin pattern. Unlike most of the existing models that can only be used for DRV prediction, the proposed models can be applied to guide detailed placement for pin accessibility optimization during physical design. Experimental results show that the proposed models are greatly superior than those of previous studies in terms of all quantitative metrics. Additionally, the numbers of DRVs can be dramatically reduced by applying the proposed model-guided detailed placement flow.

Design flow parameters are of utmost importance to chip design quality and require a painfully long time to evaluate their effects. In reality, flow parameter tuning is usually performed manually based on designers' experience in an ad hoc manner. In this work, we introduce a machine learning-based automatic parameter tuning methodology that aims to find the best design quality with a limited number of trials. Instead of merely plugging in machine learning engines, we develop clustering and approximate sampling techniques for improving tuning efficiency. The feature extraction in this method can reuse knowledge from prior designs. Furthermore, we leverage a state-of-the-art XGBoost model and propose a novel dynamic tree technique to overcome overfitting. Experimental results on benchmark circuits show that our approach achieves 25% improvement in design quality or 37% reduction in sampling cost compared to random forest method, which is the kernel of a highly cited previous work. Our approach is further validated on two industrial designs. By sampling less than 0.02% of possible parameter sets, it reduces area by 1.83% and 1.43% compared to the best solutions hand-tuned by experienced designers.

Two-dimensional (2D) global routing followed by layer assignment is a common and popular strategy to obtain a good trade-off between runtime and routing performance. Yet, the huge gap between 2D routing patterns and the final 3D routing paths often results in inevitable overflow after layer assignment. State-of-the-art studies on layer assignment usually adopt dynamic programming-based approaches to sequentially find an optimal solution for each net in terms of overflow or/and the number of vias. However, a fixed assignment ordering severely restricts the solution space, and the distributed overflows can hardly be resolved with any existing refinement approach. This paper proposes a novel layer assignment framework that concurrently considers all the wire segments of nets and iteratively assigns them from the lowest available layer to the highest one. The concurrent scheme facilitates the maximal utilization of routing resource on each layer, contributing to an effective re-routing procedure that greatly reduces inevitable overflows. Experimental results show that compared to the sequential layer assignment solutions that also refined by the same re-routing procedure, the proposed framework can averagely reduce the maximum overflow in a tile by 32% and reduce the number of tiles with overflows by 28% with much less runtime, which shows the significant advantage of concurrent layer assignment over sequential methods.

Directed self-assembly (DSA) with block copolymers (BCP) has become a promising lithography technology for generating tiny features in integrated circuits. There have been many existing studies investigating the design methodologies using cylinder-forming BCP for via/contact layer manufacturing. However, cylindrical DSA suffers from the limited natural pitch of generated holes and the displacement errors due to guiding template distortions. Consequently, only few feasible hole patterns are manufacturable with a template and the unsatisfactory yield is still one of the major concerns. On the other hand, lamellar DSA using lamella-forming BCP emerges as another solution for hole generation, which in combination with the self-aligned via (SAV) process is immune to hole displacement errors and able to produce various linear hole patterns. In this paper, we propose the first work of guiding template design for lamellar DSA by using the SAV process and multiple patterning lithography (MPL). An integer linear programming (ILP)-based approach and a heuristic method are respectively proposed that consider the design constraints induced by lamellar DSA with SAV. Experimental results demonstrate the optimality of the ILP-based approach, and the heuristic method can also efficiently derive near-optimal solutions.

In advanced semiconductor processes, the dramatic shrink of layout features has made a significant impact on circuit delay and electromigration (EM). Recently, meshed stack vias (MSVs) have been proposed as a solution to improve circuit timing and signal integrity, each of which is a multi-layer mesh structure composed of parallel metal shapes and vias. Due to the introduced MSV rules and more and more complicated design rules, MSV design becomes a very challenging problem, while no previous work has addressed this issue. In this paper, we propose the first work of MSV design by developing two different methods: an integer linear programming (ILP)-based and a dynamic programming (DP)-based methods. Unlike most previous works devoting themselves to formulating sophisticated constraints for each complicated design rule, we propose an automatic constraint generation (ACG) framework to iteratively resolve design rule violations (DRVs) without any effort in understanding all design rules, which contributes to a general MSV design methodology applicable to different technology nodes. Experimental results show that both the ILP-based and DP-based approaches can averagely achieve 92% MSV insertion rate for a set of industrial benchmarks. In addition, by adopting the proposed ACG framework, 100% MSV insertion rate can be achieved without causing any DRV.

With the development of advanced process nodes of semiconductor, the problem of pin access has become one of the major factors to impact the occurrences of design rule violations (DRVs) due to complex design rules and limited routing resource. Many state-of-the-art works address the problem of DRV prediction by adopting supervised machine learning approaches. However, those supervised learning approaches extract the labels of training data by generating a great number of routed designs in advance, giving rise to large effort on training data preparation. In addition, the pre-trained model could hardly predict unseen data and thus may not be applied to predict other designs containing cells that are not used in the training data. In this paper, we propose the first work of cell library-based pin accessibility prediction (PAP) by using active learning techniques. A given set of standard cell libraries is served as the only input for model training. Unlike most of existing studies that aim at design-specific training, we propose a library-based model which can be applied to all designs referencing to the same standard cell library set. Experimental results show that the proposed model can be applied to predict two different designs with different reference library sets. The number of remaining DRVs and M2 shorts of the designs optimized by the proposed model are also much fewer than those of design-specific models.

With the feature size shrinking down to 7 nm and beyond, the impact of wire resistance is significantly growing, and the circuit delay incurred by metal wires is noticeably raising. To address this issue, a new technique called via pillar insertion is developed. However, the poor success rate of the via pillar insertion process immediately becomes an important problem. In this paper, we explore the causes of via pillar insertion failures by experiments on the ISPD 2015 benchmarks, which are embedded with a real industrial cell library. The results show that the reasons for the low success rate may be due to track misalignment, power and ground stripe overlapping, and insufficient margin area. Therefore, we propose the first detailed placement flow which is aware of via pillars to maximize the success rate of via pillar insertion. In the proposed flow, we first filter out infeasible cell rows and then move the via pillar-inserting cells to their eligible positions. Next, we adopt a two-stage legalization method with high flexibility on cell ordering based on a dynamic programming-based detailed placement algorithm. Finally, we improve congested rows with a global moving process. Experiment results show that our algorithm improves the insertion rates by 54-58%, and achieves over 99% insertion rate on average.

At the end of digital integrated circuit (IC) design flow, some nets may still be left open due to engineering change order (ECO). Resolving these opens could be quite challenging for some huge nets such as power ground nets because of a large number of obstacles and greatly distributed net components. Existing studies on multilayer obstacle-avoiding rectilinear Steiner trees may not be applicable to solve this problem because they assume the pins of an input net is a set of points, while the discrete net components in this problem can be regarded as a set of rectilinear pins. In this paper, we develop an efficient open-net connector that can deal with rectilinear pins. The proposed algorithm flow minimizes the total connection cost based on precise estimation of the shortest distance between each pair of rectilinear net components with the presence of complex obstacles. The experimental results show that the proposed flow can outperform the top-three teams of 2017 CAD contest at ICCAD and a state-of-the-art work in terms of total connection cost or runtime efficiency.

Due to the rapid advance of integrated circuit (IC)-related technologies, design complexity is dramatically increasing in printed circuit boards (PCBs). Nowadays, a dense PCB contains thousands of pin shapes and signal nets, and such a huge net count makes the manual design of PCBs an extremely time-consuming task, especially in the routing phase. Bus routing, which consists of assigning all the buses to routing layers and topologically routing them on each layer while satisfying some constraints, is one of the most difficult steps in PCB routing. In addition, to take timing into consideration, all bits of a bus are highly preferred to have approximately the same length which are referred to as the length-matching issue. In advanced technology nodes, moreover, routing tracks are provided to help router adhere to design rules and help mask coloring. In this article, we develop a sophisticated bus router which optimizes routability, wirelength, as well as length-matching while simultaneously considering track resources, obstacles, and other design constraints. Experimental results show that the proposed algorithm flow can outperform the state-of-the-art bus routers in terms of the total routing cost and the min-max length difference for the benchmarks provided by the 2018 CAD contest at ICCAD.

With the dramatically increase of design complexity and the advance of semiconductor technology nodes, huge difficulties appear during design for manufacturability with existing lithography solutions. Sub-resolution assist feature (SRAF) insertion and optical proximity correction (OPC) are both inevitable resolution enhancement techniques (RET) to maximize process window and ensure feature printability. Conventional model-based SRAF insertion and OPC methods are widely applied in industrial application but suffer from the extremely long runtime due to iterative optimization process. In this paper, we propose the first work developing a deep learning framework to simultaneously perform SRAF insertion and edge-based OPC. In addition, to make the optimized masks more reliable and convincing for industrial application, we employ a commercial lithography simulation tool to consider the quality of wafer image with various lithographic metrics. The effectiveness and efficiency of the proposed framework are demonstrated in experimental results, which also show the success of machine learning-based lithography optimization techniques for the current complex and large-scale circuit layouts.

With the continuous scaling down of process nodes, standard cells become much smaller and cell counts are dramatically increased. Pin accessibility becomes one of the major issues causing design rule violations (DRVs). To tackle this problem, many recent works apply machine learning-based techniques to predict whether a local region has DRV or not by regarding global routing (GR) congestion and local pin density as the main features during the training process. Empirically, however, DRV occurrence is not necessary to be strongly correlated with the two features in advanced nodes. In this paper, we propose the first work of deep learning-based DRV prediction using pin pattern as our major feature to directly identify whether a DRV will exist or not due to bad pin accessibility of the given pin pattern. Unlike most of existing models that can only be used for DRV prediction, the proposed models can be applied to guide detailed placement for pin accessibility optimization during physical design. Experimental results show that the proposed models are greatly superior than those of previous studies in terms of all quantitative metrics. Additionally, the numbers of DRVs can be dramatically reduced by applying the proposed model-guided detailed placement flow.

With the dramatic shrink of feature size and the advance of semiconductor technology nodes, numerous and complicated design rules need to be followed, and a chip design can only be taped-out after passing design rule check (DRC). The high design complexity seriously deteriorates design routability, which can be measured by the number of DRC violations after the detailed routing stage. In addition, a modern large-scaled design typically consists of many huge macros due to the wide use of intellectual properties (IPs). Empirically, the placement of these macros greatly determines routability, while there exists no effective cost metric to directly evaluate a macro placement because of the extremely high complexity and unpredictability of cell placement and routing. In this paper, we propose the first work of routability-driven macro placement with deep learning. A convolutional neural network (CNN)-based routability prediction model is proposed and embedded into a macro placer such that a good macro placement with minimized DRC violations can be derived through a simulated annealing (SA) optimization process. Experimental results show the accuracy of the predictor and the effectiveness of the macro placer.

In order to support the pad-limited application-specific integrated circuit (ASIC) designs, the flip chip package is used and provides the highest chip density compared to other packaging technologies. In this paper, we propose the first work of peripheral-input and -output (I/O) free-assignment flip-chip routing considering practical bump pad and I/O pad constraints and flexibilities. Unlike previous studies regarding all nets as the same, we differentiate signal and power/ground nets and set different bump pad assignment constraints for substrate layout optimization. In our flow, a global routing-based I/O-bump assignment algorithm is proposed with a multicommodity flow network model. Afterward, two detailed routing algorithms minimizing the total wirelength are presented. Finally, a dynamic programming (DP)-based I/O pad planning technique is applied to further reduce the number of wire bends. Experimental results based on modified industrial cases show that our algorithm flow not only achieves 100% routability of all testcases but also minimizes total wirelength, total wire bends, and bump utilization.

In order to support the pad-limited Application-Specific Integrated Circuit (ASIC) designs, the flip chip package is used and provides the highest chip density compared to other packaging technologies. In this paper, we propose the first work of free-assignment flip-chip routing considering practical bump/IO pad constraints and flexibilities. Unlike previous studies regarding all nets as the same, we differentiate signal and power/ground nets and set different bump pad assignment constraints for substrate layout optimization. In our flow, a global routing-based IO-bump assignment algorithm is proposed with a multi-commodity flow network model. After that, a detailed routing algorithm minimizing total wirelength is presented, which determines optimal relay points with a linear programming (LP) formulation. Finally, a dynamic programming (DP)-based IO pad planning technique is applied to further reduce the number of wire bends. Experimental results based on modified industrial cases show that our algorithm flow not only achieves 100% routability of all testcases but also minimizes total wirelength and bump utilization.

Optical networks-on-chips (ONoCs) have become a promising solution for the on-chip communication of multi-and many-core systems to provide superior communication bandwidths, efficiency in power consumption, and latency performance compared to electronic NoCs. Serving as the critical part of ONoCs, an optical router composed of waveguides and photonic switching elements (PSEs) routes signals between two hubs or between a hub and a memory controller. Many studies focus on developing efficient architectures of optical routers, while their physical implementation that can seriously deteriorate the quality of the architectures is rarely addressed. The existing automatic place-and-route tools suffer from considerable insertion loss due to many waveguide crossings outside of PSEs, which leads to huge power consumption of laser sources. By observing that the logic schemes of most optical routers are actually planar, we develop a concurrent PSE placement and waveguide routing flow, called PlanarONoC, that guarantees optimal solutions in terms of crossings for planar logic schemes. Experimental results show that the proposed flow reduces the maximum insertion loss by 37% on average, guarantees no waveguide crossing outside of PSEs, and performs much more efficient compared to the state-of-the-art work.

At the end of digital integrated circuit (IC) design flow, some nets may still be left open due to engineering change order (ECO). Resolving these opens could be quite challenging for some huge nets such as power ground nets because of a large number of obstacles and greatly distributed net components. Existing studies on multilayer obstacle-avoiding rectilinear Steiner trees may not be applicable to solve this problem because they assume the pins of an input net is a set of points, while the discrete net components in this problem can be regarded as a set of rectilinear pins. In this paper, we develop an efficient open-net connector that can deal with rectilinear pins. The proposed algorithm flow minimizes the total connection cost based on precise estimation of the shortest distance between each pair of rectilinear net components with the presence of complex obstacles. Experimental results show that the proposed flow can outperform the top three teams of 2017 CAD Contest at ICCAD in terms of total connection cost or runtime efficiency.

Early routability prediction helps designers and tools perform preventive measures so that design rule violations can be avoided in a proactive manner. However, it is a huge challenge to have a predictor that is both accurate and fast. In this work, we study how to leverage convolutional neural network to address this challenge. The proposed method, called RouteNet, can either evaluate the overall routability of cell placement solutions without global routing or predict the locations of DRC (Design Rule Checking) hotspots. In both cases, large macros in mixed-size designs are taken into consideration. Experiments on benchmark circuits show that RouteNet can forecast overall routability with accuracy similar to that of global router while using substantially less runtime. For DRC hotspot prediction, RouteNet improves accuracy by 50% compared to global routing. It also significantly outperforms other machine learning approaches such as support vector machine and logistic regression.

Mismatches caused by random and systematic variations among identical designed devices usually dominate the performance of analog circuits, where the former can be controlled by increasing area, while the latter should be tackled by careful layout design. Most of existing studies propose analog placement methodologies with the common centroid constraint to mitigate the linear systematic gradient effect. However, nonlinear gradient error compensation should also be addressed for circuits requiring high performance. This paper presents a current source placement algorithm considering quadratic (second order) gradient error for a high-accuracy current-steering digital-to-analog converter to pursue excellent linearity. A new switching scheme and a submatrix swapping technique are proposed to maximize quadratic gradient compensation, and a simulated annealing-based matrix perturbation algorithm is also proposed to directly minimize integral nonlinearity (INL). In addition, to tackle the extremely high complexity of current source interconnections, we model the routing instance as a branch assignment problem and propose an optimal greedy-based algorithm, which is inspired by the well-known left-edge algorithm. The experimental results show an order of magnitude reduction in INL compared to a state-of-the-art nonlinear gradient-aware current source placement approach and better dynamic performance in post-layout simulation.

Electron beam lithography (EBL) has been used for high-resolution photomask fabrication; its successive heating process in a certain region, however, may cause critical dimension (CD) distortion. As a result, subfield scheduling, which reorders a sequence of subfields in the writing process, is desirable to avoid the heating problem and thus CD distortion. To consider longer range heat dissipation, this paper models a subfield scheduling problem with blocked region consideration as a constrained max–min$m$-neighbor traveling salesman problem (called constrained$m$-nTSP). To solve the constrained$m$-nTSP which is NP-complete in general, we decompose a constrained$m$-nTSP into subproblems conforming to a special case with points on two parallel lines, solve each of them with a provably good linear-time approximation algorithm, and merge them into a complete scheduling solution. In particular, our algorithm can also minimize the distances between successive subfields to alleviate the throughput degradation of EBL writing due to moving a writing head, while minimizing the heating problem. Average reductions of 10% in the maximum temperature and 14% in the distances between successive subfields over the state-of-the-art work can be achieved.

The directed self-assembly (DSA) technology has shown its great potential in via/contact layer fabrication for sub 10-nm technology nodes. To guarantee sufficient overlay accuracy of generated vias, only a few guiding templates with simple shapes are feasible, and thus manufacturable via patterns are limited. In addition, redundant via insertion has become a necessary step in the circuit design flow to improve reliability and yield. However, routing by only considering redundant vias or DSA may either deteriorate the redundant via insertion rate or damage via manufacturability. This paper presents the first work on detailed routing that simultaneously considers guiding template feasibility and redundant via insertion. Since different wiring patterns result in various via patterns and redundant via candidates, we develop a sophisticated routing graph model to avoid generating undesired wiring patterns. A trunk assignment method and several rip-up and rerouting techniques are also proposed for better via planning and layout optimization. Experimental results show that our router can significantly improve the redundant via insertion rate compared to a state-of-the-art DSA-aware detailed router.

With the rapid advance of semiconductor process technologies, layout features in integrated circuits (ICs) become highly prone to process variations. Lithography hotspots are a set of problematic layout patterns with poor printability even if they pass design rule checking (DRC). These hotspots need to be detected and fixed as early as possible in the design flow to improve manufacturability and yield. While most of existing studies focus on hotspot detection, hotspot pattern classification is rarely addressed but plays an important role in determining the efficiency of hotspot detection. In hotspot pattern classification, similar hotspots are classified into a cluster with tolerance constraints, and a representative hotspot is chosen for each cluster for future application. To minimize the problem size of subsequent hotspot detection, the number of clusters, and thus the number of representative hotspots, should be minimized. In this paper, a clip shifting method is adopted to further reduce the cluster number during hotspot classification. We propose a two-stage pattern matching algorithm flow and derive optimal solutions by solving a set cover problem. Experiment results show that our flow can reduce the cluster number by about 30% compared to reference results in 2016 CAD Contest at ICCAD.

In sub 10-nm technology nodes, the directed self-assembly technology with multiple patterning lithography (DSA-MP) is a promising solution for contact/via layer fabrication. However, previous studies using multiple patterning with a single block copolymer (BCP) material still suffer from low via manufacturability due to limited types of feasible guiding templates. To mitigate the problem, multiple patterning in combination with two different BCP materials has been proposed, which contributes to more flexible DSA-compatible pattern matching. In this paper, we propose the first work of simultaneous guiding template assignment and layout decomposition with multiple BCP materials for general via layouts in DSA-MP. An optimal integer linear programming (ILP) formulation and a practical and sophisticated heuristic algorithm are proposed. Experimental results indicate that adopting two different BCP materials can greatly reduce conflict numbers compared with existing works using a single BCP material, and the proposed heuristic method can efficiently obtain good solutions.

In sub-10 nm technology nodes, next generation lithography technologies are urgently required, and the diblock copolymer directed self-assembly (DSA) technology has shown its strong potential for contact/via layer fabrication. In addition, post-layout redundant via insertion has become a necessary step to guarantee sufficient yield and circuit reliability. However, existing redundant via insertion algorithms are not suitable for DSA since they could seriously deteriorate via manufacturability. In contrast, a sophisticated DSA-aware redundant via insertion algorithm may not only enhance circuit reliability but also improve DSA manufacturability. In this paper, we propose the first work of simultaneous guiding template optimization and redundant via insertion for DSA. Two integer linear programming (ILP)-based algorithms and an efficient graph-based approach are provided. The two ILP-based algorithms optimally maximize via manufacturability and the redundant via insertion rate. In addition, reduction techniques are presented to greatly improve the computational efficiency of ILP. For the graph-based approach, all feasible via patterns composed of original vias and redundant vias are identified. Then, the original problem is transformed into a graph formulation and efficiently optimized. Experimental results show that the ILP-based algorithms can find optimal solutions with reasonable computation time, and the graph-based algorithm can solve the problem much more efficiently and derive near-optimal solutions.

Because of the delay of the next-generation lithography technologies, self-aligned double patterning (SADP) has become one of the major lithography solutions for sub-20-nm technology nodes. For advanced sub-10-nm nodes, self-aligned quadruple patterning (SAQP) or even self-aligned octuple patterning will be required. Due to considerable design complexity and unmanageable process variation, 1-D grid-based layout structure will be adopted, which can be achieved with sophisticated self-aligned multiple patterning (SAMP) process with the use of a cut mask. However, cut masks for arbitrary layouts are hardly manufacturable, because cut mask rules are limited by conventional 193-nm lithography. To the best of our knowledge, most of the existing SADP- and SAQP-aware detailed routers would fail to generate cut mask-friendly routing results for general SAMP. In this paper, we propose the first work of cut mask optimization with wire planning in SAMP full-chip routing. We first identify cut mask-aware routing rules to guide our router. Then, cut mask-aware wire planning, detailed routing, and postlayout modification techniques are proposed in the routing flow. Experimental results show that the proposed routing algorithms are effective in generating routing results with optimized cut masks.

Self-aligned double patterning (SADP) is one of the most promising techniques for sub-20 nm technology. Spacer-is-dielectric SADP using a cut process is getting popular because of its higher design flexibility; for example, it can decompose odd cycles without the need of inserting any stitch. This paper presents the first work that applies the cut process for decomposing odd cycles during routing. For SADP, further, overlay control is a critical issue for yield improvement; while published routers can handle only partial overlay scenarios, this paper identifies all the scenarios that induce overlays and proposes a novel constraint graph to model all overlays. With the developed techniques, our router can achieve high-quality routing results with significantly fewer overlays (and thus better yields). Compared with three state-of-the-art studies, our algorithm can achieve the best quality and efficiency, with zero cut conflicts, smallest overlay length, highest routability, and fastest running time.

Because of the delay of next generation lithography technologies, self-aligned double patterning (SADP) has become one of the major lithography solutions for sub-20nm technology nodes. For advanced sub-10nm nodes, self-aligned quadruple patterning (SAQP) or even self-aligned octuple patterning (SAOP) will be required. Due to considerable design complexity and unmanageable process variation, one-dimensional grid-based layout structure will be adopted, which can be achieved with sophisticated self-aligned multiple patterning (SAMP) process with the use of a cut mask. However, cut masks for arbitrary layouts are hardly manufacturable because cut mask rules are limited by conventional 193nm lithography. To the best of our knowledge, existing SADP- and SAQP-aware detailed routers would fail to generate cut mask-friendly routing results for general SAMP. In this paper, we propose the first work of cut mask optimization with wire planning in SAMP full-chip routing. We first identify cut mask-aware routing rules to guide our router. Then, cut mask-aware wire planning, detailed routing, and post-layout modification techniques are proposed in the routing flow. Experimental results show that the proposed routing algorithms are effective in generating routing results with optimized cut masks.

Self-aligned double patterning (SADP) has become a preferred double patterning technology, due to its better overlay controllability. Two types of layout decomposition schemes are used to define two-dimensional layout patterns in SADP: Spacer-is-Metal (SIM) and Spacer-is-Dielectric (SID), and SIM-type layout decomposition typically has higher decomposition flexibility (especially for gridless designs). While SID-type layout decomposition has been studied extensively, however, only one previous work extended a satisfiability-based SID-type decomposer to SIM-type layout decomposition; this SAT-based method is inefficient for large-scale designs and not applicable to non-decomposable layouts. This paper introduces an efficient graph-based SIM-type layout decomposition heuristic. The decomposition problem is first transformed into a constrained set-covering problem. Then, an efficient algorithm composed of a greedy heuristic followed by a partition-based solution refinement scheme is proposed to simultaneously minimize the conflicts on both core masks and cut masks. Experimental results show that the algorithm can efficiently derive a good decomposition solution with minimized pattern conflicts.

As process nodes continue to shrink, the semiconductor industry faces severe manufacturing challenges. Two most expected technologies may push the limits of next-generation lithography: extreme ultraviolet lithography (EUVL) and electron beam lithography (EBL). EUVL works by emitting intense beams of ultraviolet light that are reflected from a reflective mask into a resist for nanofabrication, while EBL scans focused beams of electrons to directly draw high-resolution feature patterns on a resist without employing any mask. Each of the two technologies encounters unique design challenges and requires solutions for a breakthrough. In this paper, we focus on the design-for-manufacturability issues for EUVL and EBL. We investigate the most critical design challenges of the two technologies, flare and shadowing effects for EUVL, and heating, stitching, fogging, and proximity effects for EBL. Preliminary solutions for these effects are explored, which can contribute to the continuing scaling of the CMOS technology. Finally, we provide future research directions for these key effects.

In sub-10 nm technology nodes, next generation lithography technologies are urgently required, and the diblock copolymer directed self-assembly (DSA) technology has shown its strong potential for contact/via layer fabrication. In addition, post-layout redundant via insertion has become a necessary step to guarantee sufficient yield and circuit reliability. However, existing redundant via insertion algorithms are not suitable for DSA since they could seriously deteriorate via manufacturability. In contrast, a sophisticated DSA-aware redundant via insertion algorithm may not only enhance circuit reliability but also improve DSA manufacturability. In this paper, we propose the first work of simultaneous guiding template optimization and redundant via insertion for DSA. An optimal integer linear programming (ILP)-based algorithm and an efficient graph-based approach are provided. To facilitate the development of the ILP formulation, a systematic approach is proposed to determine whether a via is manufacturable with DSA. In addition, reduction techniques are presented to greatly reduce the computational complexity of ILP. For the graph-based approach, all feasible via patterns composed of original vias and redundant vias are identified. Then, the original problem is transformed into a graph formulation and efficiently optimized. Experimental results show that both of our two algorithms can effectively optimize via manufacturability and maximize the redundant via insertion rate within reasonable computation time.

Electron beam lithography (EBL) has been used for high-resolution photomask fabrication; its successive heating process in a certain region, however, may cause critical dimension (CD) distortion. As a result, subfield scheduling which reorders a sequence of subfields in the writing process is desirable to avoid the heating problem and thus CD distortion. To consider longer-range heat dissipation, this paper models a subfield scheduling problem with blocked region consideration as a constrained max-min m-neighbor travelling salesman problem (called constrained m-nTSP). To solve the constrained m-nTSP which is NP-complete in general, we decompose a constrained m-nTSP into subproblems conforming to a special case with points on two parallel lines, solve each of them with a provably good linear-time approximation algorithm, and merge them into a complete scheduling solution. In particular, our algorithm can also minimize the distances between successive subfields to alleviate the throughput degradation of EBL writing due to moving a writing head, while minimizing the heating problem. Average reductions of 10% in the maximum temperature and 14% in the distances between successive subfields over the state-of-the-art work can be achieved.

Multiple e-beam lithography (MEBL) is one of the most promising next generation lithography technologies for high volume manufacturing, which improves the most critical issue of conventional single e-beam lithography, throughput, by simultaneously using thousands or millions of e-beams. For parallel writing in MEBL, a layout is split into stripes and patterns are cut by stripe boundaries, which are defined as stitching lines. Critical patterns cut by stitching lines could suffer from severe pattern distortion or even yield loss. Therefore, considering the positions of stitching lines and avoiding stitching line-induced bad patterns are required during layout design. In this paper, we propose the first work of stitch-aware routing framework for MEBL based on a two-pass bottom-up multilevel router. We first identify three types of stitching line-induced bad patterns which should not exist in an MEBL-friendly routing solution. Then, stitch-aware routing algorithms are, respectively, developed for global routing, layer/track assignment, and detailed routing. Experimental results show that our stitch-aware routing framework can effectively reduce stitching line-induced bad patterns and thus may not only improve the manufacturability but also facilitate the development of MEBL.

Self-aligned double patterning (SADP) is one of the most promising techniques for sub-20nm technology. Spacer-is-dielectric SADP using a cut process is getting popular because of its higher design flexibility; for example, it can decompose odd cycles without the need of inserting any stitch. This paper presents the first work that applies the cut process for decomposing odd cycles during routing. For SADP, further, overlay control is a critical issue for yield improvement; while published routers can handle only partial overlay scenarios, our work identifies all the scenarios that induce overlays and proposes a novel constraint graph to model all overlays. With the developed techniques, our router can achieve high-quality routing results with significantly fewer overlays (and thus better yields). Compared with three state-of-the-art studies, our algorithm can achieve the best quality and efficiency, with zero cut conflicts, smallest overlay length, highest routability, and fastest running time.

While double patterning lithography (DPL) has been widely recognized as one of the most promising solutions for the sub-22 nm technology node to enhance pattern printability, triple patterning lithography (TPL) will be required for gate, contact, and metal-1 layers which are too complex and dense to be split into only two masks, for the 15 nm technology node and beyond. Nevertheless, there is very little research focusing on the layout decomposition for TPL. Recent work proposed the first systematic study on the layout decomposition for TPL. However, the proposed algorithm extending a stitch-finding method used in DPL may miss legal stitch locations and generate conflicts that can be resolved by inserting stitches for TPL. In this paper, we point out two main differences between DPL and TPL layout decompositions. Based on the two differences, we propose a novel TPL layout decomposition algorithm. We first present two new graph reduction techniques to reduce the problem size without degrading overall solution quality. We then propose a stitch-aware mask assignment algorithm, based on a heuristic that finds a mask assignment such that the conflicts among the features in the same mask are more likely to be resolved by inserting stitches. Finally, stitches are inserted to resolve as many conflicts as possible. Experimental results show that the proposed layout decomposition algorithm can achieve around 56% reduction of conflicts and more than 40X speed-up, as compared to the previous work.

Multiple e-beam lithography (MEBL) is one of the most promising next generation lithography (NGL) technologies for high volume manufacturing, which improves the most critical issue of conventional single e-beam lithography, throughput, by simultaneously using thousands or millions of e-beams. For parallel writing in MEBL, a layout is split into stripes and patterns are cut by stripe boundaries, which are defined as stitching lines. Critical patterns cut by stitching lines could suffer from severe pattern distortion or even yield loss. Therefore, considering the positions of stitching lines and avoiding stitching line-induced bad patterns are required during layout design. In this paper, we propose the first work of stitch-aware routing framework for MEBL based on a two-pass bottom-up multilevel router. We first identify three types of stitching line-induced bad patterns which should not exist in an MEBL-friendly routing solution. Then, stitch-aware routing algorithms are respectively developed for global routing, layer/track assignment and detailed routing. Experimental results show that our stitch-aware routing framework can effectively reduce stitching line-induced bad patterns and thus may not only improve the manufacturability but also facilitate the development of MEBL.

As the process technology advances to the nanometer nodes, Optical Proximity Correction (OPC) is the most popular Resolution-Enhancement Technique (RET) in industry for subwavelength lithography, and the inter-level dielectric (ILD) thickness variation caused by the planarization step of the Chemical-Mechanical Polishing (CMP) process also plays a key role for interconnect yield. Considering the OPC and CMP effects simultaneously during the routing stage can significantly alleviate the width and thickness variations (and thus the whole 3D geometry variations) of post-layout RET and CMP operations. In this paper, we first present an efficient, yet sufficiently accurate closed-form formula for printed width computation and dummy-insertion-aware routing cost derivation. The formula provides a cost modeling for post-layout OPC and CMP optimization during routing. Incorporating the OPC and CMP costs, the router can be guided to optimize the effects of layout correction and planarization. Compared with the state-of-the-art OPC-friendly router, QL-MGR (which does not consider CMP), the experimental results show that our approach can achieve respective 19% and 6% reductions in the maximum and average layout distortions. Compared with the state-of-the-art CMP-aware router, TTR (which does not consider OPC), the experimental results show that our approach can achieve respective 19% and 25% reductions in the peak-to-peak thickness and thickness variance. These results indicate that our simultaneous OPC- and CMP-aware router contributes a significant improvement for layout integrity.

Electron beam lithography has shown great promise in photomask fabrication; however, its successive heating process centralizing in a small region may cause a severe problem of critical dimension (CD) distortion. Consequently, subfield scheduling that reorders the sequence of the writing process is needed to avoid successive writing of neighboring subfields. In addition, the writing process of a subfield raises the temperature of neighboring regions and may block other subfields for writing. This paper presents the first work to solve the subfield scheduling problem while considering blocked regions by formulating the problem into a constrained maximum scatter traveling salesman problem (constrained MSTSP). To tackle the constrained MSTSP that can be shown to be NP-complete in general, we identify a special case thereof with points on two parallel lines and solve it optimally in linear time. We then decompose the constrained MSTSP into subproblems conforming to the special case, solve each subproblem optimally and efficiently by a graph-based algorithm, and then merge the subsolutions into a complete scheduling solution. We also extend our algorithm to handle the cases when the moving time of an e-beam writing head is comparable with the writing time of a subfield. Experimental results show that our algorithms are effective and efficient in finding good subfield scheduling solutions that can alleviate the successive heating problem (and thus reduce CD distortion) for e-beam photomask fabrication.

Extreme Ultraviolet Lithography (EUVL) is one of the most promising Next Generation Lithography (NGL) technologies. Due to the surface roughness of the optical system used in EUVL, the rather high level of flare (i.e., scattered light) becomes one of the most critical issues in EUVL. In addition, the layout density non-uniformity and the flare periphery effect (the flare distribution at the periphery is much different from that in the center of a chip) also induce a large flare variation within a layout. Both of the high flare level and the large flare variation could worsen the control of critical dimension (CD) uniformity. Dummification (i.e., tiling or dummy fill) is one of the flare compensation strategies to reduce the flare level and the flare variation for the process with a clear-field mask in EUVL. However, existing dummy fill algorithms for Chemical-Mechanical Polishing (CMP) are not adequate for the flare mitigation problem in EUVL due to the flare periphery effect. This paper presents the first work that solves the flare mitigation problem in EUVL with a specific dummification algorithm flow considering global flare distribution. The dummification process is guided by dummy demand maps, which are generated by using a quasi-inverse lithography technique. In addition, an error-controlled fast flare map computation technique is proposed and integrated into our algorithm to further improve the efficiency without loss of computation accuracy. Experimental results show that our flow can effectively and efficiently reduce the flare level and the flare variation, which may contribute to the better control of CD uniformity.

While double patterning lithography (DPL) has been widely recognized as one of the most promising solutions for the sub-22nm technology node to enhance pattern printability, triple patterning lithography (TPL) will be required for gate, contact, and metal-1 layers which are too complex and dense to be split into only two masks, for the 15nm technology node and beyond. Nevertheless, there is very little research focusing on the layout decomposition for TPL. The recent work [16] proposed the first systematic study on the layout decomposition for TPL. However, the proposed algorithm extending a stitch-finding method used in DPL may miss legal stitch locations and generate conflicts that can be resolved by inserting stitches for TPL. In this paper, we point out two main differences between DPL and TPL layout decompositions. Based on the two differences, we propose a novel TPL layout decomposition algorithm. We first present two new graph reduction techniques to reduce the problem size without degrading overall solution quality. We then propose a stitch-aware mask assignment algorithm, based on a heuristic that finds a mask assignment such that the conflicts among the features in the same mask are more likely to be resolved by inserting stitches. Finally, stitches are inserted to resolve as many conflicts as possible. Experimental results show that the proposed layout decomposition algorithm can achieve around 56% reduction of conflicts and more than 40X speed-up compared to the previous work.

Electron beam lithography (EBL) has shown great promise for photomask fabrication; however, its successive heating process centralizing in a small region may cause a severe problem of critical dimension (CD) distortion. Consequently, subfield scheduling which reorders the sequence of the writing process is needed to avoid successive writing of neighboring subfields. In addition, the writing process of a subfield raises the temperature of neighboring regions and may block other subfields for writing. This paper presents the first work to solve the subfield scheduling problem while taking into account blocked regions by formulating the problem into a constrained maximum scatter travelling salesman problem (constrained MSTSP). To tackle the constrained MSTSP which can be shown to be NP-complete in general, we identify a special case thereof with points on two parallel lines and solve it optimally in linear time. We then decompose the constrained MSTSP into subproblems conforming to the special case, solve each subproblem optimally and efficiently by a graph-based algorithm, and then merge the sub-solutions into a complete scheduling solution. Experimental results show that our algorithm is effective and efficient in finding good subfield scheduling solutions that can alleviate the successive heating problem (and thus reduce CD distortion) for e-beam photomask fabrication.

Double patterning technology (DPT), in which a dense layout pattern is decomposed into two separate masks to relax its pitch, is the most popular lithography solution for the sub-22 nm node to enhance pattern printability. Previous work focused on stitch insertion to improve the decomposition success rate. However, there exist native conflicts (NCs) which cannot be resolved by any kind of stitch insertion. A design with NCs is not DPT-compliant and may fail the decomposition, resulting in design for manufacturability redesign and longer design cycles. In this paper, we give a sufficient condition for the NC existence and propose a geometry-based method for NC prediction to develop an early-stage analyzer for DPT decomposability checking. Then, a wire perturbation algorithm is presented to fix as many NCs in the layout as possible. The algorithm is based on iterative 1-D compaction and can easily be embedded into existing industrial compaction systems. The algorithm is then further applied to further reduce the number of stitches required for the decomposition process. Experimental results show that the proposed algorithm can significantly reduce the number of NCs by an average of 85% and reduce the number of stitches by an average of 39%, which may effectively increase the decomposition success rate for the next stage.

Spare cells are often used in engineering change order (ECO) timing optimization. By applying spare-cell rewiring techniques, timing-violated paths in a design can be fixed. In addition, mask re-spin cost economization has become a critical challenge for modern IC design, and it can be achieved by reducing the number of layers used to rewire spare cells. This paper presents the first work for the problem of ECO timing optimization considering redundant wires (unused wires or dummy metals) to minimize the number of rewiring layers. We first propose a multi-commodity flow model for the spare-cell selection problem and apply integer linear programming (ILP) to simultaneously optimize all timing-violated paths. The ILP formulation minimizes the number of used spare cells and considers the routability of the selected spare cells. Then, we develop a tile-based ECO router which minimizes the number of rewiring layers by reusing redundant wires. Experimental results based on five industry benchmarks show that our algorithm not only effectively resolves timing violations but also reduces the number of rewiring layers under reasonable runtime.