Recently, the topic of how to utilize prior knowledge obtained by machine-learning (ML) techniques during the EDA flow has been widely studied. In this article, we study this topic and propose a practical plug-in named PROS for both routability optimization and routed wirelength estimation which can be applied in the state-of-the-art commercial EDA tool or an academic EDA flow with negligible runtime overhead. PROS consists of three parts: 1) an effective fully convolutional network (FCN)-based predictor that only utilizes the data from placement result to forecast global routing (GR) congestion; 2) a parameter optimizer that can reasonably adjust GR cost parameters based on the prediction result to generate a better GR solution for detailed routing (DR); and 3) a convolutional neural network (CNN)-based wirelength estimator which can report accurate routed wirelength at the placement stage by using the predicted GR congestion. Experiments show that on the industrial benchmark suite in the advanced technology node, PROS can achieve high accuracy of GR congestion prediction and significantly reduce design rule checking (DRC) violations by 11.65% on average, and on the DAC-2012 benchmark suite, PROS can achieve a very low error rate (1.82%) for wirelength estimation which greatly outperforms that of FLUTE (21.52%) by 19.70%.

Recently the topic of routability optimization with prior knowledge obtained by machine learning techniques has been widely studied. However, limited by the prediction accuracy, the predictors of the existing related works can hardly be applied in a real-world EDA tool without extra runtime overhead for feature preparation. In this paper, we revisit this topic and propose a practical plug-in for routability optimization named PROS which can be applied in the state-of-the-art commercial EDA tool with negligible runtime overhead. PROS consists of an effective fully convolutional network (FCN) based predictor that only utilizes the data from placement result to forecast global routing (GR) congestion and a parameter optimizer that can reasonably adjust GR cost parameters based on prediction result to generate a better GR solution for detailed routing. Experiments on 19 industrial designs in advanced technology node show that PROS can achieve high accuracy of GR congestion prediction and significantly reduce design rule checking (DRC) violations by 11.65% on average.

In advanced technology nodes, layout decomposition (LD) and mask optimization (MO) are two key stages in integrated circuit design. Due to the inconsistency of the objectives of these two stages, the performance of conventional layout and MO may be suboptimal. To tackle this problem, in this article, we propose a unified framework, which seamlessly integrates LD and MO. We propose a gradient-based approach to solve the unified mathematical formulation, as well as a set of discrete optimization techniques to avoid being stuck in local optimum. The conventional optimization process can be accelerated as some inferior decomposition results can be smartly pruned in early stages. The experimental results show that the proposed unified framework can achieve more than 34× speed-up compared with the conventional two-stage flow, meanwhile, it can dramatically reduce EPE violations by more than 8×, and thus maintain better design quality.

This paper studies the application of fixed-parameter tractable (FPT) algorithms to solve computer-aided design (CAD) problems. Specifically, we focus on layout decomposition problems for four lithography technologies: 1) double patterning lithography (DPL); 2) DPL with e-beam lithography; 3) DPL with directed self-assembly; and 4) DPL with directed self-assembly and e-beam lithography. Layout decomposition for the first three technologies are long-standing open problems without efficient optimal solutions, and the fourth technology is very promising in the future. The proposed approaches use ideas drastically different from all the previous works and can normally get optimal solutions in a short time. We show the great potential of applying FPT algorithms to solve more NP-hard problems efficiently in CAD.

As a good tradeoff between central processing unit (CPU) and application specific integrated circuit (ASIC), field-programmable gate array (FPGA) is becoming more widely used in both industry and academia. The increasing complexity and scale of modern FPGA, however, impose great challenges on the FPGA placement and packing problem. In this paper, we propose RippleFPGA to solve the packing and placement simultaneously through a set of novel techniques: 1) smooth stair-step flow; 2) implicit packing similar to ASIC legalization (LG); and 3) two-level detailed placement (DP). To enable the flow, a generic, efficient, and false-alarm-free legality checking method is also proposed. Besides, due to the insufficiency of ASIC-like congestion alleviation methods, some FPGA-routing-architecture-aware optimization techniques are proposed to improve the routability. When evaluated by ISPD 2016 Contest benchmarks, RippleFPGA has 5.1% better routed wirelength and 5.5× speedup compared to all the state-of-the-art FPGA placers.

Block copolymer directed self-assembly (DSA) is a promising technique to print contacts/vias for the 10 nm technology node and beyond. By using hybrid lithography that incorporates DSA with multiple patterning, multiple masks are used to print the DSA templates and then the templates can be used to guide the self-assembly of the block copolymer. In this paper, we propose approaches to solve the simultaneous template optimization and mask assignment problem for DSA with multiple patterning. We verified in experiments that our approaches remarkably outperform the state-of-the-art work in reducing the manufacturing cost.

1-D gridded design is one of the most promising solutions that can enable the scaling to 10 nm technology node and beyond. Line-end cuts are needed to fabricate 1-D layouts, where two techniques are available to resolve the conflicts between cuts: 1) cut redistribution and 2) cut mask assignment. In this paper, we consider incorporating the two techniques to enable the manufacturing of cut patterns in 1-D gridded design. We consider both 2-mask case (double patterning is performed on the cuts) and 3-mask case (triple patterning is performed on the cuts). We first present an accurate integer linear programming (ILP) formulation that can solve the co-optimization of cut redistribution and mask assignment optimally. In addition, we propose efficient graph-theoretic approaches based on a novel integrated graph model and a longest-path-based refinement algorithm. Experimental results demonstrate that our graphtheoretic approaches are orders of magnitude faster than the ILP-based method and meanwhile it can obtain very comparable results. For 2-mask case, comparing with the method that solves mask assignment and cut redistribution optimally but separately, our graph-theoretic approach that solves the two tasks simultaneously can achieve 95.0× smaller cost on average. We also extend our graph-theoretic approach to 3-mask case. Comparing with the method that reduces the 3-mask problem to 2-mask problem and solves it indirectly, our innovative approach that solves the problem directly based on a novel framework of identifying and solving 4-cliques can achieve 7.6% smaller cost on average.

This paper studies the application of fixed-parameter tractable (FPT) algorithms to solve computer-aided design (CAD) problems. Specifically, we focus on layout decomposition problems for three lithography technologies: double patterning lithography (DPL), DPL with E-beam lithography (DPL+EBL), and DPL+DSA+EBL. Layout decomposition for the first two technologies are long-standing open problems without efficient optimal solutions, and the third technology is very promising in the future. The proposed approaches use ideas drastically different from all the previous works and can get optimal solutions in a short time. We show the great potential of applying FPT algorithms to solve more NP-hard problems efficiently in CAD.

Liquid cooling shows great potential in resolving the huge thermal obstacle in 3D ICs. However, it brings new challenges including large thermal gradient and high pumping requirement. In this paper, liquid cooling networks with flexible topology are investigated to achieve more desirable trade-offs between energy efficiency and thermal profile. Specifically, a fast thermal model for the cooling network is proposed and analyzed, followed by our optimization methodologies to construct cooling networks targeting at pumping power saving and thermal gradient reduction, respectively. Experimental results show that, under the same constraints, the cooling network can save as much as 84.03% pumping power or reduce 37.65% thermal gradient compared to straight microchannels.

In advanced technology nodes, layout decomposition and mask optimization are two key stages in integrated circuit design. Due to the inconsistency of the objectives of these two stages, the performance of conventional layout and mask optimization may be suboptimal. To tackle this problem, in this paper we propose a unified framework, which seamlessly integrates layout decomposition and mask optimization. We propose a gradient based approach to solve the unified mathematical formulation, as well as a set of discrete optimization techniques to avoid being stuck in local optimum. The conventional optimization process can be accelerated as some inferior decompositions can be smartly pruned in early stages. The experimental results show that the proposed unified framework can achieve more than 17 x speed-up compared with the conventional two-stage flow, meanwhile it can reduce EPE violations by 18%, and thus maintain better design quality.

Block Copolymer Directed Self-Assembly (DSA) is a promising technique to print contacts/vias for the 10nm technology node and beyond. By using hybrid lithography that cooperates DSA with multiple patterning, multiple masks are used to print the DSA templates and then the templates can be used to guide the self-assembly of the block copolymer. In this paper, we propose approaches to solve the simultaneous template optimization and mask assignment problem for DSA with multiple patterning. We verified in experiments that our approaches remarkably outperform the state of the art work in reducing the manufacturing cost.

1D gridded design is one of the most promising solutions that can enable the scaling to 10nm technology node and beyond. Line-end cuts are needed to fabricate 1D layouts, where two techniques are available to resolve the conflicts between cuts: cut redistribution and cut mask assignment. In this paper, we consider incorporating the two techniques to enable the manufacturing of cut patterns in 1D gridded design. We first present an accurate integer linear programming (ILP) formulation that can solve the co-optimization of cut redistribution and mask assignment optimally. In addition, we propose an efficient graph-theoretic approach based on a novel integrated graph model and a longest-path-based refinement algorithm. Experimental results demonstrate that our graphtheoretic approach is orders of magnitude faster than the ILP-based method and meanwhile can obtain very comparable results. Comparing with the method that solves mask assignment and cut redistribution optimally but separately, our graph-theoretic approach that solves the two tasks simultaneously can achieve 95.0× smaller cost and 84.8× speedup on average.

As the complexity and scale of FPGA circuits grows, resolving routing congestion becomes more important in FPGA placement. In this paper, we propose a routability-driven placement algorithm for large-scale heterogeneous FPGAs. Our proposed algorithm consists of (1) partitioning, (2) packing, (3) global placement with congestion estimation, (4) window-base legalization, and (5) routing resource-aware detailed placement. Experimental results show that our proposed approach can give routable placement results for all the benchmarks in the ISPD2016 contest and can achieve good result compared to the other wining teams of the ISPD2016 contest.

To reduce chip-scale topography variation, dummy fill is commonly used to improve the layout density uniformity. Previous works either sought the most uniform density distribution or sought to minimize the inserted dummy fills while satisfying certain density uniformity constraint. However, due to more stringent manufacturing challenges, more criteria, like line deviation and outlier, emerge at newer technology nodes. This article presents a joint optimization scheme to consider variation, total fill, line deviation, outlier, overlap, and running time simultaneously. More specifically, first we decompose the rectilinear polygons and partition fillable regions into rectangles for easier processing. After decomposition, we insert dummy fills into the fillable rectangular regions optimizing the fill metrics simultaneously. We propose three approaches, Fast Median approach, LP approach, and Iterative approach, which are much faster with better quality, compared with the results of the top three contestants in the ICCAD Contest 2014.

Triple patterning lithography (TPL) is regarded as a promising technique to handle the manufacturing challenges in the 14nm technology node and beyond. It is necessary to consider TPL in early design stages to make the layout more TPL friendly and reduce the manufacturing cost. In this paper, we propose a flow to co-optimize cell layout decomposition and detailed placement. Our cell decomposition approach can enumerate all coloring solutions with the minimum number of stitches. The experimental results show that our approach can outperform the existing work in all aspects of stitch number, half-perimeter wirelength (HPWL), and running time. We further extend our placer to consider the displacement of cells as a constraint and as an objective, respectively, which can help to preserve the quality of the input placement. Effectiveness of the extensions is verified by the experiments.

Triple Patterning Lithography (TPL) is regarded as a promising technique to handle the manufacturing challenges in 14nm and beyond technology node. It is necessary to consider TPL in early design stages to make the layout more TPL friendly and reduce the manufacturing cost. In this paper, we propose a flow to co-optimize cell layout decomposition and detailed placement. Our cell decomposition approach can enumerate all coloring solutions with the minimum number of stitches. Experimental results show that our approach can outperform the existing work in all aspects of stitch number, HPWL and running time.

E-Beam Lithography (EBL) is a maskless nano-lithography technology that creates features on a wafer by directly shooting a beam of electrons onto the wafer. Different from the current mainstream optical lithography technology, i.e. 193nm ArF immersion lithography, EBL overcomes the limit of light diffraction. As one of the most promising next generation lithography (NGL) technologies, it can achieve very high resolution even for sub-10nm technology node. However, before EBL can be used for High Volume Manufacturing (HVM), its problem of low throughput has to be solved. Character Projection (CP) with a set of pre-defined characters is thought to be an essential technology for throughput improvement. With CP, a key problem is stencil planning, which is to select and place the best characters onto the stencil such that the throughput of the system can be maximized. If the overlapping between characters are awared, the throughput can be further optimized. In this paper, we investigate this 2D overlapping-aware stencil planning problem. Experiments show that our approach can achieve significant throughput improvement and remarkable speed-up comparing with previous works.

Character projection is a key technology to enhance throughput of e-beam lithography, in which characters need to be selected and placed on the stencil. This paper solves the problem of planning for overlapping-aware row-structure stencil, and also considers multi-column cell system for further throughput improvement. We propose an integrated framework to solve the subproblems of character selection, row distribution, single-row ordering and inter-row swapping efficiently. Experiments show that our approach outperforms the existing methods on all the benchmarks. We can achieve significant throughput improvement and up to 1782X speedup comparing with previous works. The average speedup is 704X.

Modern placement process involves global placement, legalization, and detailed placement. Global placement produce a placement solution with minimized target objective, which is usually wire-length, routability, timing, etc. Legalization removes cell overlap and aligns the cells to the placement sites. Detailed placement further improves the solution by relocating cells. Since target objectives like wire-length and timing are optimized in global placement, legalization and detailed placement should not only minimize their own objectives but also preserve the global placement solution. In this paper, we propose a detailed placement algorithm for minimizing wire-length, while preserving the global placement solution by cell displacement constraint and target cell density objective. Our detailed placer involves two steps: Global Move that allocates each cell into a bin/region that minimizes wire-length, while not overflowing the target cell density. Local Move that finely adjust the cell locations in local regions to further minimize the wire-length objective. With large-scale benchmarks from ICCAD 2013 detailed placement contest, the results show that our detailed placer, RippleDP, can improve the global placement results by 13.38% - 16.41% on average under displacement constraint and target placement density objective.

Due to a significant mismatch between the objectives of wirelength and routing congestion, the routability issue is becoming more and more important in VLSI design. In this paper, we present a high quality placer Ripple 2.0 to solve the routability-driven placement problem. We will study how to make use of the routing path information in cell spreading and relieve congestion with tangled logic in detail. Several techniques are proposed, including (1) lookahead routing analysis with pin density consideration, (2) routing path-based cell inflation and spreading and (3) robust optimization on congested cluster. With the official evaluation protocol, Ripple 2.0 outperforms the top contestants on the ICCAD 2012 Contest benchmark suite.

Triple Patterning Lithography (TPL) is widely recognized as a promising solution for 14/10nm technology node. In this paper, we propose an efficient layout decomposition approach for TPL, with the objective to minimize the number of conflicts and stitches. Based on our analysis of actual benchmarks, we found that the whole layout can be reduced into several types of small feature clusters, by some simplification methods, and the small clusters can be solved very efficiently. We also present a new stitch finding algorithm to find all possible legal stitch positions in TPL. Experimental results show that the proposed approach is very effective in practice, which can achieve significant reduction of manufacturing cost, compared to the previous work.