Very large scale integration (VLSI) circuits typically consist of millions of nets, posing significant challenges for efficient physical design. Interconnect delay has become a critical factor for timing performance in technology nodes at 5nm and beyond. Additionally, the coupling effect among the wires increases the complexity of delay optimization. Moreover, tapering constraints are essential in advanced technology nodes to ensure manufacturability. Furthermore, the ever-increasing scale of modern designs necessitates a high-performance computing (HPC) framework to accelerate delay-driven layer assignment in advanced technology nodes. To address these challenges, we propose ParDelay, a parallel delay-driven layer assignment leveraging hierarchical task graph modeling while considering tapering constraints for advanced technology nodes, which includes the following five key techniques: 1) A general deterministic parallel framework is proposed for delay-driven layer assignment, leveraging a hierarchical task graph to enable both internet and inter-node parallelism. 2) A delay- and overflow-driven tapering repairing strategy is proposed to eliminate tapering violations while further optimizing net delay. 3) A local delay-critical net filtering method is proposed to analyze local delay criticality to guide layer assignment, thereby minimizing delay while eliminating overflow. 4) To mitigate the coupling effect, we propose a net shielding algorithm that reduces wire density for maximum delay candidate nets to optimize maximum delay. 5) A delay-aware refinement strategy is proposed to classify nets by their delay rank and assign distinct non-default-rule (NDR) wire permissions and refinement objectives, thereby reducing delay. Experimental results demonstrate that, compared to existing layer assignment algorithms and parallel routing frameworks, our approach effectively reduces delay, via count, and runtime under the tapering constraints.

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.

With increasingly complex design rules and pin density in advanced technology nodes, achieving a violation-free layout has become more challenging, also making rip-up and reroute (RUR) the most runtime-intensive component of detailed routing. We propose a novel reinforcement learning (RL)based approach to enhance the window-based RUR process. Our method features a dynamic window generation strategy that adjusts window size and position based on the distribution of design rule violations (DRV), enabling efficient targeting of congested areas. By leveraging the predictive capabilities of RL, our approach aims to minimize DRVs and achieve high-quality routing results. Experimental results demonstrate that our method outperforms the state-of-theart detailed routers, TritonRoute, achieving a DRV-free solution, averagely improving wirelength by 0.07%, via count by 2.42%, and consuming almost the same average runtime.

The track assignment has been introduced between global routing and detail routing. Based on the independence and divisibility of track assignment, we propose a GPU-accelerated parallel track assignment algorithm. To estimate routability more accurately, the proposed algorithm simultaneously considers global and local nets, and incorporates several strategies for optimization. Moreover, an asynchronous parallelism strategy is proposed to divide the computation of routing resources and the track assignment into fine-grained tasks. Experimental results show that, compared to related work, our algorithm achieves a significant speedup with a better routability estimation.

Late-stage placement optimization is where real PPA trade-offs surface, and where conventional heuristic passes tend to get trapped in small, local neighborhoods. We frame an invited "Problem C" contest that treats this stage as a global, multi-operator search over gate sizing, buffer/inverter-pair insertion, and legal cell relocation, with strict reproducibility and legality. Our core belief grounded in production experience is that GPU batching and differentiable guidance expand the tractable search space: you can score and steer thousands of coordinated moves per iteration, not just a handful, and do so under tight runtime budgets. Submissions must produce a replayable ECO changelist and a final legal DEF; a standardized evaluation flow computes timing, power, and wirelength and combines them with displacement and runtime into the contest score. The specification is designed to encourage pragmatic use of gradient signals and tensorized batching without mandating any single method, enabling participants to leverage novel GPU tools to deliver industrially deployable PPA gains.

In the physical design flow, detailed placement is critical for wirelength optimization and routability enhancement. While many CPU-based approaches emphasize wirelength reduction, GPU-based approaches primarily focus on accelerating detailed placement without sacrificing quality. However, leveraging GPU parallelism to further improve placement quality remains largely underexplored. As existing optimization steps have approached the practical limits of wirelength optimization, achieving further improvements has become increasingly challenging. In this work, we propose a GPU-based detailed placement flow featuring Simultaneous Row and Order Assignment (SROA) step, a novel step that integrates dynamic programming-based row assignment with heuristic-based cell position adjustment. SROA enables efficient exploration of a significantly larger solution space on GPUs. Experimental results show that our approach preserves routability while reducing detailed routing wirelength and via count by 1.35% and 1.03%, respectively, compared to the ABCDPlace solutions.

Global routing is a critical aspect of VLSI design, significantly impacting timing, power consumption, and routability. The ISPD2024 contest focused on addressing the scalability challenges of global routing by leveraging GPU and machine learning techniques. Building on this foundation, the ISPD2025 contest introduces several important updates to better reflect real-world routing challenges. These updates include the provision of industry-standard input files for more precise modeling and integration with OpenROAD for accurate performance assessment. Collectively, these updates aim to bring the contest closer to practical routing scenarios, fostering the development of scalable and efficient solutions for large-scale chip designs.

The Steiner minimum tree (SMT) serves as an optimal connection model for multiterminal nets in very large scale integration (VLSI). Constructing both rectilinear SMT (RSMT) and octilinear SMT (OSMT) are known to be NP-hard problems. Simultaneously, constructing multiple topologies of SMTs for a given net holds significant importance in alleviating routing constraints such as alleviating congestion and ensuring timing convergence. However, existing efforts predominantly focus on designing specialized methods to construct a specifically structured SMT for a given net, making it challenging to extend to different structures or topologies of SMTs, while also exhibiting insufficient optimization capabilities. In this work, we propose a unified approach based on deep reinforcement learning (DRL) to address both RSMT and OSMT problems while generating diverse routing topologies. First, we design an edge point sequence (EPS) that leverages the structural characteristics of SMT to connect the output of the deep learning model with the SMT structure. Second, we propose a deep learning model tailored for EPS, employing the negative wirelength of SMT as a reward to train the model using DRL. Third, we provide a corresponding rapid and accurate wirelength computation algorithm for evaluating the quality of the construction solution to expedite model training. Finally, we leverage the stochastic nature of machine learning to construct diverse SMT construction solutions. To the best of our knowledge, this is the first unified approach capable of simultaneously addressing both RSMT and OSMT problems while generating diverse solutions. The proposed unified approach demonstrates superior solution quality and higher efficiency compared to specifically designed algorithms.

Routability has always been a significant challenge in Very Large Scale Integration (VLSI) design. To overcome the potential mismatch between the global routing results and the detailed routing requirements, track assignment is introduced to achieve an efficient routability estimation. Moreover, with the increasing scale of circuits, the intricate interconnections among the components on the chip lead to increased timing delay in signal transmission, thereby significantly impacting the performance and reliability of the circuit. Thus, to further improve the routability of the circuit, it is also critical to realize an accurate estimation of the timing delay within the track assignment stage. Existing heuristic track assignment algorithms, however, are prone to local optimality, and thus fail to provide accurate routability estimations. In this article, we propose an enhanced scalable parallel track assignment algorithm called SPTA 2.0 for VLSI design, employing a two-stage partition strategy and considering timing delay. First, the proposed algorithm achieves efficient assignment of all wires by considering the routing information from both the global and local nets. Second, the overlap cost, the blockage cost, and the wirelength cost can be minimized to significantly improve the routability. Third, a critical wire controlling strategy is proposed to optimize signal timing delays inside nets. Finally, a two-stage partition strategy and a panel-subpanel-level parallelism are designed to further reduce the runtime, improving the scalability of the proposed methodology. Experimental results on multiple benchmarks demonstrate that the proposed method provides better routability estimations, and leads to superior track assignment solutions compared with existing algorithms.

Modern VLSI design flows demand scalable global routing techniques applicable across diverse design stages. In response, the ISPD 2024 contest pioneers the first GPU/ML-enhanced global routing competition, selecting advancements in GPU-accelerated computing platforms and machine learning techniques to address scalability challenges. Large-scale benchmarks, containing up to 50 million cells, offer test cases to assess global routers' runtime and memory scalability. The contest provides simplified input/output formats and performance metrics, framing global routing challenges as mathematical optimization problems and encouraging diverse participation. Two sets of evaluation metrics are introduced: the primary one concentrates on global routing applications to guide post-placement optimization and detailed routing, focusing on congestion resolution and runtime scalability. Special honor is given based on the second set of metrics, placing additional emphasis on runtime efficiency and aiming at guiding early-stage planning.

Printed circuit board (PCB) design is typically semi-automated or fully manual. However, in recent years, the scale of PCB designs has rapidly enlarged, such that the engineering effort of manual design has increased dramatically. Therefore, the criticality of automation emerges. PCB houses are looking for productivity improvement that is contributed by automation. In this talk, the speaker will give a short tutorial about how a PCB design is done today and then indicate the challenges and opportunities for PCB design automation.

Package routing is typically done by semi-auto or manual manners in order to meet several customized requests for different design styles. However, in recent years, the scale of package designs rapidly enlarges, and routing rules become more and more complicated, such that the engineering effort of the manual solution increases dramatically. Therefore, the need of full-auto solution becomes necessary and critical. In addition, in order to build an automatic design flow for 3D-IC, full-auto package routing is one of most important pieces. There are many challenges for realizing full-auto package routing solution. Some of the challenges will be introduced in this paper.

Timing optimization has always been a key issue affecting the chip performance. Most of the previous layer assignment algorithms mainly optimize timing from the perspective of interconnect delay, and often ignore the impact of slew on signal integrity. Therefore, this paper proposes LA-SVR, a high-performance layer assignment algorithm with slew violations reduction. The proposed algorithm mainly includes three key techniques: 1) an effective classified reassignment strategy is proposed to re-assign nets in terms of different optimization priorities for overflow avoidance; 2) an effective net adjustment method is adopted to reduce the potential slew violations; 3) a layer restricting strategy is proposed to optimize delay of nets and slew violations simultaneously by restricting the candidate better routing layers of different nets. Experimental results show that the proposed algorithm has a significant effect on slew violations reduction.

Routability has always been a very challenging issue in Very Large Scale Integrated (VLSI) circuit design. The routability is considered in track assignment so that the global routing results can better match the requirements of detailed routing. However, existing heuristic track assignment algorithms are prone to local optimality, which cannot provide the accurate routability estimation. To overcome this limitation, we propose a scalable parallel Integer Linear Programming (ILP)-based track assignment algorithm, called SPTA, which employs a two-stage partition strategy. First, by taking into account both the global and local nets, all wires are assigned to tracks, making full use of the information from the global routing results. Second, an efficient ILP model for track assignment is proposed to minimize the overlap between iroutes1, thus significantly improving routability. Third, a two-stage partition strategy is designed to reduce the runtime. Finally, a panel-subpanel-level parallelism is proposed to further speed up the algorithm without sacrificing the quality of the solutions. Experimental results show that SPTA has a better routability estimation compared with the existing algorithms.

Pin access is increasingly important in advanced nodes. Neighboring or cell-boundary pins can have degraded pin accessibility, causing design rule violations (DRCs) during routing, which are runtime expensive to resolve. Conventional physical design tool flow uses pessimistic and/or inaccurate understanding of pin access during the placement stage and keeps the location of cells fixed during routing. This can leave pin access issues unsolvable and block further routing solution improvement. The timeliness of our present work is confirmed by the recent ICCAD-2020 CAD Contest, Problem B formulation from Synopsys, Inc. (Hu and Yang, 2020). The organizers give a succinct motivation for what we study—to eliminate preserved margins and misalignment issues from conventional placement models. In this work, we develop anin-route, pin access-driven local placement refinement. Experiments across industry designs in a wide range of advanced technology nodes confirm that our optimization can significantly improve routing convergence (i.e., subsequent detailed routing runtime and initial detailed routing DRCs). Our optimization can reduce congestion and wirelength without timing degradation.

Interconnect delay is a key factor that affects the chip performance in layer assignment. Particularly in the advanced process technologies of 5 nm and beyond, interconnect delay has grown significantly due to the increase of circuit scale. Moreover, coupling effect existed in wires reduces the accuracy of delay evaluation. On the other hand, the size of vias is often ignored in layer assignment, which enlarges the mismatch between global routing and detailed routing. To solve these problems, we proposeVPT, a timing-aware layer assignment algorithm considering via pillars, which includes the following five key techniques: 1) via pillar structure combined with nondefault-rule (NDR) wires is adopted to form a net delay optimization system for advanced process technologies; 2) a synthetical model that can adapt to varying types and sizes of both vias and wires is designed to evaluate overflow effectively; 3) a sorting strategy is devised to reduce uncertainty of layer assignment flow and improve stability of the proposed algorithm; 4) an awareness strategy based on multiaspect congestion assessment is designed to reduce overflow significantly; and 5) a net scalpel algorithm is devised to minimize the maximum delay of nets, so that the timing behaviors can be improved systematically. The experimental results on multiple benchmarks confirm that the proposed algorithm leads to lower delay and less overflow, while achieving the best solution quality among the existing algorithms with the shortest runtime.

As the scale of VLSI circuits increases rapidly, multi-FPGA prototyping systems have been widely used for logic verification. Due to the limited number of connections between FPGAs, however, the routability of prototyping systems is a bottleneck. As a consequence, timing division multiplexing (TDM) technique has been proposed to improve the usability of prototyping systems, but it causes a dramatic increase in system delay. In this paper, we propose ALIFRouter, a practical architecture-level inter-FPGA router, to improve the chip performance by reducing the corresponding system delay. ALIFRouter consists of three major stages, including i) routing topology generation, ii) TDM ratio assignment, and iii) system delay optimization. Additionally, a multi-thread parallelization method is integrated into the three stages to improve the efficiency of ALIFRouter. With the proposed algorithm, major performance indicators of multi-FPGA systems such as signal multiplexing ratio can be improved significantly.

Layer assignment, a major step in global routing of integrated circuits, is usually performed to assign segments of nets to multiple layers. Besides the traditional optimization goals such as overflow and via count, interconnect delay plays an important role in determining chip performance and has been attracting much attention in recent years. Accordingly, in this paper, we propose MiniDelay, a timing-aware layer assignment algorithm to minimize delay for advanced technology nodes, taking both wire congestion and coupling effect into account. MiniDelay consists of the following three key techniques: 1) a non-default-rule routing technique is adopted to reduce the delay of timing critical nets, 2) an effective congestion assessment method is proposed to optimize delay of nets and via count simultaneously, and 3) a net scalpel technique is proposed to further reduce the maximum delay of nets, so that the chip performance can be improved in a global manner. Experimental results on multiple benchmarks confirm that the proposed algorithm leads to lower delay and few vias, while achieving the best solution quality among the existing algorithms with the shortest runtime.

As the scale of VLSI circuits and fabrication costs increase rapidly, multi-FPGA prototyping systems are widely adopted in industry to make logic verification faster and cheaper. Since routing signals can usually exceed the number of I/O pins in an FPGA, timing division multiplexing (TDM) technique is required to solve this problem. FPGA routing for developing a prototyping system is a big challenge due to the signal delay of TDM. This paper presents MSFRoute, a multi-stage FPGA routing framework for timing division multiplexing technique, to optimize the signal delay and the routability for prototyping systems. In this work, a TDM ratios assignment algorithm with an efficient parallelization method is proposed to optimize inter-FPGA signal delay. Meanwhile, we propose a practical system clock period optimization method to solve critical signal delay problem. Experimental results show that our routing framework reduces TDM ratios by up to 88.3% with an average reduction rate of 41.8%. With the proposed parallelization method, total flow of MSFRoute can get up to 4.38X speedup with a 2.77X speedup on average.

Closing timing using clock tree optimization (CTO) is a tremendously challenging problem that may require designer intervention. CTO is performed by specifying and realizing delay adjustments in an initially constructed clock tree. Delay adjustments are typically realized by inserting delay buffers or detour wires. In this paper, we propose a latency constraint guided buffer sizing and layer assignment framework for clock trees with useful skew, called the (BLU) framework. The BLU framework realizes delay adjustments during CTO by performing buffer sizing and layer assignment. Given an initial clock tree, the BLU framework first predicts the final timing quality and specifies a set of delay adjustments, which are translated into latency constraints. Next, buffer sizing and layer assignment is performed with respect to the latency constraints using an extension of van Ginneken's algorithm. Moreover, the framework includes a feature of reducing the power consumption by relaxing the latency constraints and a method of improving the timing performance by tightening the latency constraints. The experimental results demonstrate that the proposed framework is capable of reducing the capacitive cost with 13% on the average. The total negative slack (TNS) and worst negative slack (WNS) are reduced with up to 58% and 20%, respectively.

Detailed routing becomes the most complicated and runtime consuming stage in the physical design flow as technology nodes advance. Due to the inaccessibility of advanced routing rules and industrial designs, it is hard to conduct detailed routing academic researches using the modern real-world designs. ISPD18 hosts the first detailed routing contest [1] and releases a set of benchmarks synthesized by industrial tools with practical routing rules. ISPD18 contest spurs detailed routing researches and provides students the opportunity to become familiar with the industrial designs and rules. On top of ISPD18 detailed routing contest, we host another detailed routing contest in ISPD19 [2] to consider several advanced routing rules and make the contest problem one step closer to the real-world routing challenges in advanced technology nodes. ISPD19 detailed routing contest encourages participants to use double-cut vias to improve yield and result quality. In addition, in order to drive the development of efficient routing frameworks, the deterministic multithreading feature is encouraged but optional in this contest.

In advanced technology nodes, detailed routing becomes the most complicated and runtime consuming stage. To spur detailed routing research, ISPD 2018 initial detailed routing contest is hosted and it is the first ISPD contest on detailed routing problem. In this contest, the benchmarks synthesized by industrial tool and library are released, which consider the design rules like spacing table, cut spacing, end-of-line spacing, and min-area rules. In addition, the global routing guide is provided associated to each benchmark, and detailed routers are required to honor the routing guides as much as possible meanwhile minimize design-rule-checking (DRC) violations. The biggest benchmark released in this contest has near-millions of nets, so the runtime and memory scalability for detailed routers need to be well addressed. To reduce routers' runtime, the deterministic multithreading framework is encouraged but optional in this contest.

As very large-scale integration technology shrinks to fewer tracks per standard cell, e.g., from 10 to 7.5-track libraries (and lesser for 7 nm), there has been a rapid increase in the usage of multiple-row cells like two- and three-row flip-flops, buffers, etc., for design closure. Additionally, the usage of multibit flip-flops or flop trays to save power creates large cells that further complicate critical design tasks, such as placement. Detailed placement happens to be a key optimization transform, which is repeatedly invoked during the design closure flow to improve design parameters, such as wirelength, timing, and local wiring congestion. Advanced node designs, with hundreds of thousands of multiple-row cells, require a paradigm change for this critical design closure transform. The traditional approach of fixing multiple-row cells during detailed placement and only optimizing the locations of single-row standard cells can no longer obtain appreciable quality of results. It is imperative to have new techniques that can simultaneously optimize both multiple- and single-row height cell locations during detailed placement. In this paper, we propose a new density-aware detailed placer for heterogeneous-sized netlists. Our approach consists of a chain move scheme that generalizes the movement of heterogeneous-sized cells, a nested dynamic programming-based approach for ordered double-row placement and a network flow-based formulation to solve ordered multiple-row placement for wirelength and density optimization. Experimental results demonstrate the effectiveness of these techniques in wirelength minimization and density smoothing compared with the most recent detailed placers for designs with heterogeneous-sized cells.

This paper addresses a delay-driven layer assignment problem with consideration of via delay and coupling effect in the global routing stage. A negotiation-based framework is proposed to balance delay, congestion, and via count. Coupling capacitance is considered using a probabilistic look-up table. Finally, the proposed algorithm uses both parallel wires and wide wires to reduce wire delay. The effectiveness of our layer assignment algorithm is supported by extensive experimental results.

Routability has become a very challenging issue in a modern VLSI design flow. Many works use global routing to estimate the routability in the early design stages. However, global routing cannot accurately capture local congestion, so it is hard to detect the detailed routability issue. To more accurately estimate the detailed-routing routability, this paper presents a track-assignment-based routability estimator. In this work, wire segments called iroutes are extracted from a global routing result, and then the proposed negotiation-based algorithm assigns these iroutes to proper tracks and minimizes the overlaps between the iroutes. Based on the assignment result, we can judge which regions may have critical routability issues by seeing where more overlaps reside.

As VLSI technology shrinks to fewer tracks per standard cell, e.g., from 10-track to 7.5-track libraries (and lesser for 7nm), there has been a rapid increase in the usage of multiple-row cells like two- and three-row flip-flops, buffers, etc., for design closure. Additionally, the usage of multi-bit flip-flops or flop trays to save power creates large cells that further complicate critical design tasks, such as placement. Detailed placement happens to be a key optimization transform, which is repeatedly invoked during the design closure flow to improve design parameters, such as, wirelength, timing, and local wiring congestion. Advanced node designs, with hundreds of thousands of multiple-row cells, require a paradigm change for this critical design closure transform. The traditional approach of fixing multiple-row cells during detailed placement and only optimizing the locations of single-row standard cells can no longer obtain appreciable quality of results. It is imperative to have new techniques that can simultaneously optimize both multiple- and single-row high cell locations during detailed placement. In this paper, we propose a new density-aware detailed placer for heterogeneous-sized netlists. Our approach consists of a chain move scheme that generalizes the movement of heterogeneous-sized cells as well as a nested dynamic programming based approach for wirelength and density optimization. Experimental results demonstrate the effectiveness of these techniques in wirelength minimization and density smoothing compared with the most recent detailed placer for designs with heterogeneous-sized cells.

To avoid producing unroutable placement solutions, many state-of-the-art routability-driven placers iteratively invoke global routers to evaluate their placement solutions, and then perform routability optimization. However, using a global router to evaluate hard-to-route placement solutions may spend considerable runtime and it cannot guarantee that a placement is truly unroutable to any router. This paper presents an unroutable placement recognizer based on a window-based unroutable region recognition algorithm and a length-bounded unroutable panel recognition (UPR) algorithm, which can confirm some placements that are exactly unroutable among a set of hard-to-route placements. In addition, if a placement is recognized to be unroutable, the recognizer can report a lower bound of total overflow for the placement. The experimental results reveal that the unroutable region recognition algorithm can find out 16 placements that are definitely unroutable among 23 widely used hard-to-route global routing benchmarks. Moreover, when a scenic constraint is considered, the UPR algorithm can find out a few more placements that are also unroutable.

Interposer-based 3D ICs (or known as 2.5D ICs) have been seen as an alternative approach to true 3D stacked ICs, which mount multiple dies on a silicon interposer and route signals between dies by the interconnects in the interposer. However, the floorplan of dies on the interposer and the signal assignment for macro-bumps and TSVs will largely impact the wirelength of the interconnects in a 2.5D IC. Because long interconnects would degrade the performance of 2.5D ICs, the multi-die floorplanning problem and signal assignment problem for 2.5D ICs are critical. This paper presents an enumeration-based algorithm and a network-flow-based algorithm to solve the multi-die floorplanning and signal assignment problems in a 2.5D IC, respectively. Also, to speed up the floorplanning and signal assignment algorithms, several acceleration techniques are proposed. The experimental results reveal that this work can effectively reduce the total wirelength in a 2.5D IC and the acceleration techniques can significantly speed up the proposed algorithms.

Placement consists of three stages: global placement, legalization, and detailed placement (DP). Recently, most research works have concentrated on improving global placement and legalization, but innovations in DP have been rarely seen. ICCAD13 held a DP contest that formulates the emerging placement issues into a bin-utilization metric and maximum cell displacement constraint. This paper presents a detailed placer that can effectively reduce both half-perimeter wirelength and the peak bin-utilization under the displacement constraint. The proposed lazy-update based incremental density profit function supports efficient cell swapping. Combination of lazy-update density profit function and Density-Driven Swap lets our placer achieve AOFP of 0 for the majority of the ICCAD13 test cases. The placer presented produces the best placement results among the top3 teams in the ICCAD13 contest.

A 2.5D IC provides a silicon interposer to integrate multiple dies into a package, which not only offers better performance than 2D ICs but also has lower manufacturing complexity than true 3D ICs. In an interposer, routing wires connect signals between dies or route signals from dies to the package substrate. The number of metal layers in an interposer is one of the critical factors to affect the routability and manufacturing cost of the 2.5D IC. Thus, how to achieve 100% routing completion rate in an interposer using a minimum number of metal layers plays a key role for the success of a 2.5D IC. This paper presents a global-routing-based metal layer planner called VGR to identify a minimal number of metal layers for an interposer with consideration of routability and manufacturing cost. Also, VGR can identify a good stacking order of the horizontal and vertical layers in an interposer such that the routing solution in the interposer costs fewer vias. To our best knowledge, this paper is the first study to solve the metal layer planning problem for silicon interposers.

Wire sizing can be used to reduce the delays of critical nets. However, because of the forbidden pitch issue in sub-20nm designs, wide wires may no longer be an attractive solution because of the restrictive wire spacing requirement from advanced lithography. In this work, we investigate the suitability of the parallel wiring technique, in which multiple parallel wires are used to route the same net, as an alternative to routing a net using a single wide wire. In particular, we study the trade offs between parasitics, timing, power, and routing resources. Our study reveals that wire sizing using both parallel wires and wide wires can be advantageous. Moreover, if high layout densities are required, parallel wiring can be a viable approach in solving timing problems for sub-20nm designs.

Routability has become a challenging issue with designs scaling down. Recently, global-routing-based routing congestion estimators (GRCEs) are widely used to detect the routability problems in the early VLSI design stages. To make GRCEs fast, using parallel routing approaches to speed up GRCEs is a promising direction. However, integrating existing parallel routing approaches into a GRCE may degrade the accuracy of the GRCE, because the routing kernel of the GRCE has to be modified such that its routing behavior changes. This paper presents a resource-level parallel approach (RPA) to accelerate GRCEs. RPA is easy to implement and has no need to change the routing kernels of GRCEs. Thus, GRCEs accelerated by RPA can keep its routing behavior and the estimation accuracy. Moreover, this paper presents an analytical method to quantify the estimation accuracy of a GRCE. Traditionally, the accuracy of a GRCE is manually measured by how they look like between the congestion maps generated by the GRCE and a real router, which may be inaccurate and time-consuming. In contrast, using the proposed quantifying method to evaluate the accuracy of a GRCE is more precise and faster.

To avoid producing unroutable placement solutions, many state-of-the-art routability-driven placers iteratively invoke global routers to evaluate their placement solutions and then perform routability optimization. However, using a global router to evaluate hard-to-route placement solutions may spend considerable runtime and it cannot guarantee that a placement is truly unroutable to any router. This paper presents an unroutable placement recognizer based on a window-based layout scanning algorithm, which can confirm some placements that are exactly unroutable among a set of hard-to-route placements. In addition, if a placement is recognized to be unroutable, the recognizer can point out unroutable regions and report a lower bound of total overflow for the placement. The experimental results reveal that the proposed recognizer can find out 16 placements that are definitely unroutable among 23 widely used hard-to-route global routing benchmarks.

The public release of realistic industrial placement benchmarks by IBM and Intel Corporations from 1998--2013 has been crucial to the progress in physical-design algorithms during those years. Direct comparisons of academic tools on these test cases, including widely publicized contests, have spurred researchers to discover faster, more scalable algorithms with significantly improved quality of results.

Routability has become a critical issue in VLSI design flow. To avoid producing an unroutable design, many placers [4-7] invoke global routers to get a congestion map and then move cells to reduce congestion based on this map. However, as cells move, the accuracy of the congestion map degrades, thereby affecting the effectiveness of the placer in minimizing congestions. Moreover, most global routers [8-13] ignore local congestion. If placers are guided by these routers, it may produce hard-to-route placement solutions in terms of detailed routing. This work develops a routability optimizer, called Ropt, to reduce both global and local routing congestion levels of a given placement. Based on a local-routability-aware routing model, Ropt builds a global routing instance to obtain global and local congestion information for guiding global re-placement. In addition, this work presents a new legalization scheme to preserve the global routing instance after legalization. Finally, local detailed placement further minimizes the local congestion and wirelength. For the evaluation of Ropt, we use an academic global router and a commercial router to obtain both global and detailed routing results, respectively. Experimental results reveal that Ropt can improve the routing quality (in terms of congestion, wirelength, and violation) and routing runtime of a given placement solution.

To address the routability issue, routing congestion estimators (RCE) become essential in industrial design flow. Recently, several RCEs [1-4] based on global routing engines are developed, but they typically ignore the effects of routing on timing so that the identified routing paths may be overlong and thus impractical. To be aware of the timing issues, our proposed global-routing-based RCE obeys the layer directive and scenic constraints to respectively limit the routing layers and the maximum routing wirelength of the potentially timing-critical nets. To handle the scenic constrains, we propose a novel method based on a relaxation-legalization scheme. Also, because the work in [5] reveals that congestion ratio is a better indicator than overflow to evaluate routability, this work focuses on minimizing the congestion ratio rather than overflows. As will be shown, the problem of minimizing congestion ratio is more complicated than minimizing overflows, so we develop a new rip-up and rerouting scheme to reduce congestion and further to approach a target congestion ratio. Moreover, to fit the demands of practical uses, this work presents a control utility to trade off runtime and quality, which is an essential function to an industrial RCE tool. Experiments reveal that the proposed RCE is faster and more accurate than another industrial global-routing-based RCE.

Routability is a critical issue in VLSI design flow. To address this issue, the routability-driven placement contests [1, 2] held at ISPD11 and DAC12 promote the development of routability-driven placers such as those in [4-6]. ISPD11 and DAC12 contests adopt metrics that are based on global routing solutions to evaluate the routability of placement solutions. However, such global-routing-based metrics typically ignore local congestion, and they cannot evaluate the actual routability effectively. In this work, we develop a translator that allows us to feed the placement solutions of mPL [3], NTUplace [4], Ripple [5], and SimPLR [6] into a commercial router for detailed routing. We then analyze the detailed routing result of each placement solution to better understand the issues that may cause routing violations. Moreover, we examine the suitability of using the ISPD11 and DAC12 metrics in predicting routability. Our findings indicated that the metrics might not reliably predict actual routability, in terms of the number of (detailed) routing violations.

Modern global routers employ various routing methods to improve routing speed and quality. Maze routing is the most time-consuming process for existing global routing algorithms. This paper presents two bounded-length maze routing (BLMR) algorithms (optimal-BLMR and heuristic-BLMR) that perform much faster routing than traditional maze routing algorithms. In addition, a rectilinear Steiner minimum tree aware routing scheme is proposed to guide heuristic-BLMR and monotonic routing to build a routing tree with shorter wirelength. This paper also proposes a parallel multithreaded collision-aware global router based on a previous sequential global router (SGR). Unlike the partitioning-based strategy, the proposed parallel router uses a task-based concurrency strategy. Finally, a 3-D wirelength optimization technique is proposed to further refine the 3-D routing results. Experimental results reveal that the proposed SGR uses less wirelength and runs faster than most of other state-of-the-art global routers with a different set of parameters , , , . Compared to the proposed SGR, the proposed parallel router yields almost the same routing quality with average 2.71 and 3.12-fold speedup on overflow-free and hard-to-route cases, respectively, when running on a 4-core system.

Conventional buffer insertion in timing ECO involves only minimizing the arrival time of the most critical sink in one multi-pin net and neglects the obstacles and the topology of routed wire segments, which may worsen the arrival times of other sinks and burden subsequent timing ECO. This work develops a topology-aware ECO timing optimization (TOPO) flow that comprises three phases - buffering pair scoring, edge breaking and buffer connection, and topology restructuring. TOPO effectively improves the arrival times of violation sinks without worsening those of other sinks. Experimental results indicate that TOPO improves the worst negative slack (WNS) and total negative slack (TNS) of benchmarks by an average of 79.2% and 84.3%, respectively. The proposed algorithm improves the arrival time that is achieved using conventional two-pin net-based buffer insertion by an average of 40.4%, at the cost of consuming 19× runtime. To speed up routing and further improve sink slack, a highly scalable massively parallel maze routing on Graphics Processing Unit (GPU) platform is also developed to enable the proposed flow to explore more solution candidates. High scalability and parallelism are realized by block partitioning and staggering. Experiments reveal that the proposed GPU-based parallel maze routing can achieve near 12× runtime speedup for two-pin routings. With parallelized maze routing, WNS violations in four out of five cases can be resolved.

Considering routability issue in the early stages of VLSI design flow can avoid generating an unroutable design. Several recent routablity-driven placers [8--11] adopt a built-in global router to estimate routing congestion. While the routability of the placement solution improves, the performance of these placers degrades. Many of these built-in global router and state-of-the-art academic global routers use maze routing to seek a detoured path. Although very effective, maze routing is relatively slower than other routing algorithms, such as pattern routing and monotonic routing algorithms. This work presents two efficient routing algorithms, called unilateral monotonic routing and hybrid unilateral monotonic routing, to replace maze routing and to realize a highly fast maze-free global router that is suited to act as a built-in routing congestion estimator for placers. Experimental results indicate that RCE achieves similar routing quality when compared with [20], as well as an over 20-fold runtime speedup in large benchmarks.

Traditional solutions to antenna effect, such as jumper insertion and diode insertion peformed at post-route stage may produce extra vias and degrade circuit performance. The work in [1] suggests combining layer assignment, jumper insertion and diode insertion together to achieve a better design quality with less additional cost. Based on our observations on global and local antenna violations, this work proposes a dynamic-programming based single-net layer assignment called NALAR, which first enumerates all antenna-violation-safe layer assignment solutions of a net, and then extracts the minimum-cost one for the net. NALAR can minimize via count and separators as well. In addition, an antenna avoidance layer assignment algorithm (ANLA) adopting NALAR as its kernel not only avoids global antenna violations, but also eliminates local antenna violations. Experimental results reveal that, in 11 benchmarks, ANLA can yield 5 violation-free assignments while the algorithms of other works yield no violation-free assignment. As for the total number of antenna violations in all benchmarks, this work and the works in [2], [3] and [4] yield 21, 43506, 41261 and 29671 antenna violations, respectively. However, ANLA performs about 7 times slower than other antenna-aware layer assignment [4].

The increasing complexity of interconnection designs has enhanced the importance of research into global routing when seeking high-routability (low overflow) results or rapid search paths that report wirelength estimations to a placer. This work presents two routing techniques, namely circular fixed-ordering monotonic routing and evolution-based rip-up and rerouting using a two-stage cost function in a high-performance congestion-driven 2-D global router. We also propose two efficient via-minimization methods, namely congestion relaxation by layer shifting and rip-up and reassignment, for a dynamic programming-based layer assignment. Experimental results demonstrate that our router achieves performance similar to the first two winning routers in ISPD 2008 Routing Contest in terms of both routability and wirelength at a 1.05 × and 18.47 × faster routing speed. Moreover, the proposed layer assignment achieves fewer vias and shorter wirelength than congestion-constrained layer assignment (COLA).

Layer assignment determines on which layer the wires or vias should be placed; and the assignment results influence the circuit's delay, crosstalk, and via counts. How to minimize via count and via overflow during layer assignment has received considerable attention in recent years. Traditional layer assignment to minimize via count tends to produce varying qualities of assignment results using different net orderings. This work develops a negotiation-based via count minimization algorithm (NVM) that can achieve lower via counts than in previous works, and experimental results indicate that net assignment ordering only slightly influences the quality of NVM's results. As for via overflow minimization, we observe via overflow can be well minimized if via overflow minimization is performed following stacked via minimization. The stacked via minimization adopts the proposed NVM, while via overflow minimization adopts a modified NVM by replacing via cost with via overflow cost. Experimental results reveal that the proposed NVM yields a lower additional via cost than and by 10.8%, 2.5%, respectively, in the via count minimization problem. As for via overflow minimization, the proposed two-stage algorithm improves via overflow by 11.5% and lowers the via cost by 6.5% than the one-stage algorithm.

Multiple dynamic supply voltage (MDSV) provides an effective way to reduce dynamic power and is widely used in high-end or low-power designs. The challenge of routing MDSV designs is that the net in MDSV designs needs to be planned carefully to avoid electrical problems or functional failure as a long interconnect path pass through the shutdown power domains. As the first work to address the MDSV global routing problem, power domain-aware routing (PDR) problem is defined and the point-to-point PDR algorithm is also presented herein with look-ahead path selection method and look-up table acceleration approach. For multi-pin net routings, a novel constant-time table-lookup mechanism by invoking four enhanced monotonic routings to fast compute the least-cost monotonic path from every node to the target sub-tree is presented to speed up the query about routing cost (including driven-length slack) to target during multi-source multi-target PDR. Experimental results confirm that the proposed MDSV-based global router can efficiently identify legally optimized routing results for MDSV designs, and can effectively reduce overflow, wire length, inserted level shifters and runtime.

Given the extensive study of clock skew minimization, in the ISPD 2009 Clock Network Synthesis (CNS) Contest, clock latency range (CLR) was initially minimized across multiple supply voltages under capacitance and slew constraints. CLR approximates the summation of the clock skew and the maximum source-to-sink delay variation for multiple supply voltages. This work develops an efficient three-stage clock tree synthesis flow for CLR minimization. Firstly, a balanced clock tree with small skew is generated. Secondly, buffer insertion and wire sizing minimizes delay variation without violating the slew constraint. Finally, skew is minimized by inserting snaking wires. Experimental results reveal that the proposed flow can complete all ISPD'09 benchmark circuits and yield less CLR than the top three winners of ISPD'09 CNS contest by 59%, 52.7% and 35.4% respectively. Besides, the proposed flow can also run 5.52, 1.86, and 7.54 times faster than the top three winners of ISPD'09 CNS contest respectively.

Modern global routers use various routing methods to improve routing speed and the quality. Maze routing is the most time-consuming process for existing global routing algorithms. This paper presents two bounded-length maze routing (BLMR) algorithms (optimal-BLMR and heuristic-BLMR) to perform much faster routing than traditional maze routing algorithms. The proposed sequential global router, which adopts a heuristic-BLMR, identifies less-wirelength routing results with less runtime than state-of-the-art global routers. This study also proposes a parallel multi-threaded collision-aware global router based on a previous sequential global router. Unlike the conventional partition-based concurrency strategy, the proposed algorithm uses a task-based concurrency strategy. Experimental results reveal that the proposed sequential global router uses less wirelength and runs about 1.9X to 18.67X faster than other state-of-the-art global routers. Compared to the proposed sequential global router, the proposed parallel global router yields almost the same routing quality with average 2.71 and 3.12-fold speedup on overflow-free and hard-to-route benchmarks, respectively, when running on an Intel quad-core system.

The increasing complexity of interconnection designs has enhanced the importance of research into global routing when seeking high-routability (low overflow) results or rapid search paths that report wire-length estimations to a placer. This work presents two routing techniques, namely adaptive pseudorandom net-ordering routing and evolution-based rip-up and reroute using a two-stage cost function in a high-performance congestion-driven 2-D global router. We also propose two efficient via-minimization methods, namely congestion relaxation by layer shifting and rip-up and re-assignment, for a dynamic programming-based layer assignment. Experimental results demonstrate that our router achieves performance similar to the first two winning routers in ISPD 2008 Routing Contest in terms of both routability and wire length at a 1.42X and 25.84X faster routing speed. Besides, our layer assignment yields 3.5% to 5.6% fewer vias, 2.2% to 3.3% shorter wirelength and 13% to 27% less runtime than COLA.