In global routing, both timing and routability are critical criteria to measure the performance of a design. However, these two objectives naturally conflict with each other during routing. In this paper, we propose reconnection approaches to fix timing. We first formulated a quadratic program (QP), which adjusts routing topologies of all the nets by only reconnecting critical sinks and takes congestion into consideration to tradeoff timing and routability objectives. A machine learning (ML)-based technique is applied to accelerate our algorithm, which offers a fast and effective way to solve the problem. By exploring more reconnection candidates, we then formulated a QP to reconnect any sink of a net and utilized a multilabel classifier to accelerate the process. The experimental results on ICCAD 2015 benchmarks show that our algorithms can achieve timing improvement with no significant degradation in routability and wirelength. With ML-based acceleration, our results can be obtained in almost negligible runtime.

Dummy fill insertion is a mandatory step in modern semiconductor manufacturing process to reduce dielectric thickness variation, and provide nearly uniform pattern density for the chemical mechanical planarization (CMP) process. However, with the continuous shrinking of the VLSI technology nodes, the coupling effects between the inserted metal fills and signal tracks can severely affect the original timing closure of the layout design. In this paper, we propose a robust, efficient and high-performance framework for timing-aware dummy fill insertion, which simultaneously minimizes the coupling capacitance of critical signal wires and other wires. The experimental results on IC/CAD 2018 contest benchmarks shows that our proposed framework outperforms contest winner by 8% on critical coupling capacitance with 3.3× runtime speedup.

Boolean matching is one of the most widely used engines in industrial applications. However, existing Boolean matching researches mainly focus on NPNP-equivalence. In this paper, we study a more practical problem of Boolean matching, which is Non-exact Projective NPNP (NP3). A two-step search engine is used to solve the problem and several heuristics and constraints are proposed to accelerate the whole process. In particular, we explore a new kind of symmetry properties in NP3 equivalence checking which helps to prune the solution space efficiently. Experimental results show that our proposed approach can achieve the best results among the winning teams of the ICCAD 2016 contest in quality within a given time limit.

In global routing, both timing and routability are critical criterions to measure the performance of a design. However, these two objectives naturally conflict with each other during routing. In this paper, a tree surgery technique is presented to adjust routing tree topologies in global routing to fix timing. We formulate the problem as a quadratic program(QP), which adjusts routing topologies of all the nets from a global perspective and takes congestion into consideration to trade off timing and routability objectives. We also apply machine learning-based techniques to accelerate our algorithm, which offers a fast and effective way to solve the problem. Experimental results on ICCAD~2015 benchmarks show that our algorithms can achieve 10.12% timing improvement with no significant degradation in routability and wirelength. With machine learning-based acceleration (MLA), our results can be obtained in almost negligible runtime.

In a weighted undirected graph, a spanning/Steiner shallow-light tree (SLT) simultaneously approximates (i) shortest distances from a root to the other vertices, and (ii) the minimum tree weight. The Steiner SLT has been proved to be exponentially lighter than the spanning one [1], [2]. In this paper, we propose a novel Steiner SLT construction method called SALT (Steiner shAllow-Light Tree), which is efficient and has the tightest bound over all the state-of-the-art SLT algorithms. Applying SALT to Manhattan space offers a smooth trade-off between rectilinear Steiner minimum tree (RSMT) and rectilinear Steiner minimum arborescence (RSMA) for VLSI routing. In addition, the adaption further reduces the time complexity from O(n2) to O(n log n). The experimental results show that SALT can achieve not only short path lengths and wirelength but also small delay, compared to both classical and recent routing tree construction methods.

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.