Deep learning is a promising approach to early DRV (Design Rule Violation) prediction. However, non-deterministic parallel routing hampers model training and degrades prediction accuracy. In this work, we propose a stochastic approach, called LGC-Net, to solve this problem. In this approach, we develop new techniques of Gaussian random field layer and focal likelihood loss function to seamlessly integrate Log Gaussian Cox process with deep learning. This approach provides not only statistical regression results but also classification ones with different thresholds without retraining. Experimental results with noisy training data on industrial designs demonstrate that LGC-Net achieves significantly better accuracy of DRV density prediction than prior arts.

As the semiconductor process technology advances into sub-10-nm regime, cell pin accessibility, which is a complex joint effect from the pin shape and nearby blockages, becomes a main cause for design rule violations (DRVs). Therefore, a machine-learning model for DRV prediction needs to consider both very high-resolution pin shape patterns and low-resolution layout information as input features. A new convolutional neural network technique, J-Net, is introduced for the prediction with mixed resolution features. This is a customized architecture that is flexible for handling various input and output resolution requirements. It can be applied at placement stage without using global routing information. This technique is evaluated on 12 industrial designs at a 7-nm technology node. The results show that the J-Net-based binary classifier can improve the true positive rate by 37%, 40%, and 7%, respectively, compared to extensions of three recent works, with similar false positive rates.

EDA tools provide a large spectrum of parameters to help designers achieve the maximized PPA of designs. The corresponding enormous solution space, however, hinders designers from navigating towards optimal solutions. In this paper, we propose a multi-stage automatic flow tuning tool, named FlowTuner, for efficient and effective parameter tuning of VLSI design flow. It utilizes both exploitation using transferred parameter knowledge from archival design data and exploration via a multi-stage cooperative co-evolutionary framework. Furthermore, novel flow jump-start and early-stop techniques are developed to reduce the overall runtime for tuning. Experiments on a set of IWLS 2005 benchmark circuits through a commercial tool flow demonstrate that FlowTuner produces considerably better design outcomes in 50 % shorter turnaround time compared to the state-of-the-art flow tuning techniques.

Double patterning is a widely used technique for sub-22nm. Among various double patterning techniques, Self-Aligned Double Patterning (SADP) is a promising technique for good mask overlay control. Based on SADP, a new set of standard cells (T-cells) are developed using thicker metal wires for stronger drive strength. By applying this kind of gates on critical paths, it helps to improve the design performance. However, a mixed design with T-cells and normal cells (N-cells) requires that T-cells are placed on circuit rows with thicker metal, and the normal cells are on the normal circuit rows. Therefore, a placer is needed to adjust the cells to the matched circuit rows. In this paper, a two-stage min-cost max-flow based legalization flow is presented to adjust N/T gate locations for a legal placement. The experimental results demonstrate the effectiveness and efficiency of our approach.

Interconnect spacing is getting increasingly smaller in advanced technology nodes, which adversely increases the capacitive coupling of adjacent interconnect wires. It makes crosstalk a significant contributor to signal integrity and timing, and it is now imperative to prevent crosstalk-induced noise and delay issues in the earlier stages of VLSI design flow. Nonetheless, since the crosstalk effect depends primarily on the switching of neighboring nets, accurate crosstalk evaluation is only viable at the late stages of design flow with routing information available, e.g., after detailed routing. There have also been previous efforts in early-stage crosstalk prediction, but they mostly rely on time-expensive trial routing. In this work, we propose a machine learning-based routing-free crosstalk prediction framework. Given a placement, we identify routing and net topology-related features, along with electrical and logical features, which affect crosstalk-induced noise and delay. We then employ machine learning techniques to train the crosstalk prediction models, which can be used to identify crosstalk-critical nets in placement stages. Experimental results demonstrate that the proposed method can instantly classify more than 70% of crosstalk-critical nets after placement with a false-positive rate of less than 2%.

As the semiconductor process technology advances into sub-10nm regime, cell pin accessibility, which is a complex joint effect from the pin shape and nearby blockages, becomes a main cause for DRC violations. Therefore, a machine learning model for DRC hotspot prediction needs to consider both very high-resolution pin shape patterns and low-resolution layout information as input features. A new convolutional neural network technique, J-Net, is introduced for the prediction with mixed resolution features. This is a customized architecture that is flexible for handling various input and output resolution requirements. It can be applied at placement stage without using global routing information. This technique is evaluated on 12 industrial designs at 7nm technology node. The results show that it can improve true positive rate by 37%, 40% and 14% respectively, compared to three recent works, with similar false positive rates.

Power consumption has become a major consideration in nanometer chip design. Since the dynamic power is proportional to V dd2, and the static power is proportional to V dd, lowering power supply voltage is an efficient method to reduce the power usage.

In this paper, we present a novel algorithm for latch placement, LatchPlanner which enables a placement engine to deliver high quality placement for datapath-oriented design. Datapath-oriented VLSI designs are in general hand-crafted by human at high cost, as understanding and capturing datapath structure is critical for the performance. The conventional placement algorithms by itself cannot exploit the underlying datapath due to lack of logic structure recognition and inaccurate/approximated wirelength estimation. LatchPlanner addresses such drawbacks by placing and fixing latches in the datapath context, a key element in datapath structure. By taking placed/fixed latches as constraints, a placer can find a more datapath-friendly placement effectively, which results in higher-quality hardware. LatchPlanner begins latch clustering/sizing/ordering to prepare the following steps, a) global latch placement based on linear programming to place latch clusters, and b) local latch placement based on network flow optimization to place latches within each cluster. Experimental results on eighteen industrial benchmarks show that LatchPlanner improves total wirelength by 32%, total negative slack by 25%, and area by 3% without CPU overhead over a commercial placement engine, and delivers near semi-custom-quality solutions.

A symmetric-function fanin tree (SFFT) is a fanout-free cone of logic that computes a symmetric function such as AND, OR and XOR. These trees are usually created during logic synthesis, when there is no knowledge of the tree gate locations. Because of this, large SFFTs present a challenge to placement algorithms. The consequence is that the tree placements are generally far from optimal, leading to wiring congestion, excess buffering, and timing problems. [10] proposed a fanin-tree restructure algorithm to reduce the SFFT wirelength. However, [10] was based on Steiner trees and might cause serious timing problems due to the high Steiner tree depth. In this paper, we extend the SFFT tree identification algorithm to allow both positive and negative tree inputs. Contrary to the Steiner-tree based approach, we propose a new tree restructure flow to build SFFTs from bottom to top level by level at the physical design stage. The tree restructure algorithm is in a transaction mode so that only improved trees are accepted, and the new tree won't cause any placement legal issue. A new partitioning algorithm is proposed to serve for gate creation. In addition, various optimization techniques are developed to reduce tree wirelength On tested designs, the total tree wirelength is reduced by 31% with similar tree gates and tree depths.

In deep sub-micro designs, more functions are integrated into one chip, and datapath has become a critical part of the design. Typical datapath consists an array of bit slices. The inherent high degree regularity of datapaths is especially attractive to the placement and routing to achieve regular layout with high density and high performance. However, the current design methodology may generate inferior datapath designs because the datapath regularity cannot be well understood by the traditional design tools. In previous works, several techniques are proposed to preserve/re-identify datapath structures. However, they either restrict the datapath optimization or have little tolerance on bit slice difference.

In VLSI placement, legalization is an essential step where the overlaps between gates/macros must be removed. In this paper, we introduce a history-based legalization algorithm with min-cost network flow optimization. We find a legal solution with the minimum deviation from a given placement to fully honor/preserve the initial placement, by solving a gate-centric network flow formulation in an iterative manner. In order to realize a flow into gate movements, we develop efficient techniques which solve an approximated Subset-sum problem. Over the iterations, we factor into our formulation the history which captures a set of likely-to-fail gate movements. Such a history-based scheme enables our algorithm to intelligently legalize highly complex designs. Experimental results on over 740 real cases show that our approach is significantly superior to the existing algorithms in terms of failure rate (no failure) as well as quality of results (55% less max-deviation).

A symmetric-function fan-in tree (SFFT) is a fanout-free cone of logic that computes a symmetric function, so that all of the leaf nets in its support set are commutative. Such trees are frequently found in designs, especially when the design originated as two-level logic.These trees are usually created during logic synthesis, when there is no knowledge of the locations of the tree root or of the source gates of the leaf nets. Because of this, large SFFTs present a challenge to placement algorithms. The result is that the tree placements are generally far from optimal, leading to wiring congestion, excess buffering, and timing problems. Restructuring such trees can produce a more placeable and wire-efficient design.In this paper, we propose algorithms to identify and to restructure SFFTs during physical design. The key feature of an SFFT is that it can be implemented with various structures of a uniform set of gates with commutative inputs, i.e. AND, OR, or XOR. Drawing on the flexibility of SFFT logic structures, the proposed tree restructuring algorithm uses existing placement information to rebuild the SFFTs with reduced tree wire lengths. The experimental results demonstrate the efficiency and effectiveness of the algorithms.

In this paper, we propose track routing and optimization for yield (TROY), the first track router for the optimization of yield loss due to random defects. As the probability of failure (POF), which is an integral of the critical area and the defect size distribution, strongly depends on wire ordering, sizing, and spacing, track routing can play a key role in effective wire planning for yield optimization. However, a straightforward formulation of yield-driven track routing can be shown to be integer nonlinear programming, which is a nondeterministic polynomial-time complete problem. TROY overcomes the computational complexity by combining two effective techniques, i.e., the minimum Hamiltonian path (MHP) from graph theory and the second-order cone programming (SOCP) from mathematical optimization. First, TROY performs wire ordering to minimize the critical area for short defects by finding an MHP. Then, TROY carries out optimal wire sizing/spacing through SOCP optimization based on the given wire order. Since the SOCP can be optimally solved in near linear time, TROY efficiently achieves globally optimal wire sizing/spacing for the minimal POF.

As the device shapes keep shrinking, the designs are more sensitive to manufacturing processes. In order to improve performance predictability and yield, mask-layout uniformity/evenness is highly desired, and it is usually measured by the feature densities within defined feasible ranges determined by the manufacturing-process design rules. To address the density-control problem, one fundamental problem is how to calculate density accurately and efficiently. In this paper, we propose a fast exact algorithm to identify the maximum/minimum density for a given layout. Compared with the existing exact algorithms, our algorithm reduces the running time from days/long hours to a few minutes/seconds. Moreover, it is even faster than the existing approximate algorithms in the literature.

In modern very large scale integration manufacturing processes, dummy fills are widely used to adjust local metal density in order to improve layout uniformity and yield optimization. However, the introduction of a large amount of dummy features also affects wire electrical properties. In this paper, we propose the first coupling-constrained dummy-fill analysis algorithm which identifies feasible locations for dummy fills such that the fill-induced coupling capacitance can be bounded within the given coupling threshold of each wire segment. A speedup approach is presented based on the cache concept. The algorithm also makes efforts to maximize ground dummy fills, which are more robust and predictable. The output of the algorithm can be treated as the upper bound for dummy-fill insertion, and it can be easily adopted in density models to guide dummy-fill insertion without disturbing the existing design.

As integrated circuits manufacturing technology is advancing into 65nm and 45nm nodes, extensive resolution enhancement techniques (RETs) are needed to correctly manufacture a chip design. The widely used RET called off-axis illumination (OAI) introduces forbidden pitches which lead to very complex design rules. It has been observed that imposing uniformity on layout designs can substantially improve printability under OAI. For metal layers, uniformity can be achieved simply by inserting dummy metal wire segments at all free spaces. Simulation results indeed show significant improvement in printability with such a dummy metal insertion approach. To minimize mask cost, it is advantageous to use dummy metal segments that are of the same size as regular metal wires due to their simple geometry. But these dummy wires are printable and hence increase coupling capacitances and potentially affect yield. The alternative is to use a set of parallel sub-resolution thin wires (which is not printed) to replace a printable dummy wire segment. These invisible dummy metal segments do not increase coupling capacitances but bring a higher lithography cost, which includes mask cost and RET/process expense. This paper presents a strategy for dummy metal insertion that can optimally trade off lithography cost and coupling capacitance. In particular, we present an optimal algorithm that can minimize lithography cost subject to any given coupling capacitance bound. Moreover, this dummy metal insertion achieves a highly uniform density because of the locality of coupling capacitance, which automatically ameliorates chemical mechanical polish (CMP) problem.

In this paper, we propose TROY, the first track router with yield-driven wire planning to optimize yield loss due to random defects. As the probability of failure (POF) computed from critical area analysis and defect size distribution strongly depends on wire ordering, sizing, and spacing, track routing plays a key role in effective wire planning for yield optimization. TROY formulates wire ordering into a preference-aware minimum Hamiltonian path problem. For simultaneous wire sizing and spacing optimization, TROY solves it optimally by formulating the problems into a second order conic programming (SOCP). Experimental results show that TROY can reduce the random-defect yield loss by 18% on average without any overhead in wirelength, compared with the widely used greedy approach.

As the device shapes keep shrinking, the designs are more sensitive to manufacturing processes. In order to improve performance predictability and yield, mask layout uniformity/evenness is highly desired, and it is usually measured by the feature density with defined feasible range in manufacture process design rules. To address the density control problem, one fundamental problem is how to calculate density accurately and efficiently. In this paper, we propose a fast exact algorithm to identify the maximum density for a given layout. Compared with the existing exact algorithms, our algorithm reduces the running time from days/hours to a few minutes/seconds. And it is even faster than the existing approximate algorithms in literature.

In modern VLSI manufacturing processes, dummy fills are widely used to adjust local metal density in order to improve layout uniformity and yield optimization. However, the introduction of a large amount of dummy features also affects wire electrical properties. In this paper, we propose the first Coupling constrained Dummy Fill (CDF) analysis algorithm which identifies feasible locations for dummy fills such that the fill induced coupling capacitance can be bounded within the given coupling threshold of each wire segment. The algorithm also makes efforts to maximize ground dummy fills, which are more robust and predictable. The output of the algorithm can be treated as the upper bound for dummy fill insertion, and it can be easily adopted in density models to guide dummy fill insertion without disturbing the existing design.

In this paper, we propose the first wire density driven global routing that considers CMP variation and timing. To enable CMP awareness during global routing, we propose a compact predictive CMP model with dummy fill, and validate it with extensive industry data. While wire density has some correlation and similarity to the conventional congestion metric, they are indeed different in the global routing context. Therefore, wire density rather than congestion should be a unified metric to improve both CMP variation and timing. The proposed wire density driven global routing is implemented in a congestion-driven global router [5] for CMP and timing optimization. The new global router utilizes several novel techniques to reduce the wire density of CMP and timing hotspots. Our experimental results are very encouraging. The proposed algorithm improves CMP variation and timing by over 7% with negligible overhead in wirelength and even slightly better routability, compared to the pure congestion-driven global router [5].

Engineering change order changes are almost inevitable in the late stages of a design process. Based on an existing design, incremental change is favored since it can avoid considerable efforts of redoing the whole process and can minimize the disturbance on the existing converged design. The coupling-capacitance violation elimination (CVE) problem is addressed. Due to the changes in the multiple layer routing design, the total coupling capacitance on some signal wire segments on a layer may be larger than their allowable bounds after postlayout timing/noise analysis. The target is to find a new routing solution without coupling-capacitance violations under certain constraints, which helps to keep the new design close to the original one. This paper proposes a two-stage algorithm to solve CVE problems, and present optimization strategies to speed up the execution. Experimental results demonstrate the efficiency and effectiveness of this algorithm

The buffer block methodology has become increasingly popular as more and more buffers are needed in deep-submicron design, and it leads to many challenging problems in physical design. In this article, we present a polynomial-time exact algorithm for integrated pin assignment and buffer planning for all two-pin nets from one macro block (source block) to all other blocks of a given buffer block plan, while minimizing the total cost α ˙ W + β ˙ R for any positive α and β where W is the total wirelength, and R is the number of buffers. By applying this algorithm iteratively (each time, pick one block as the source block), it provides a polynomial-time algorithm for pin assignment and buffer planning for nets among multiple macro blocks. Experimental results demonstrate its efficiency and effectiveness.

ECO changes are almost inevitable in late stages of a design process. Based on an existing design, incremental change is favored since it can avoid considerable efforts of re-doing the whole process and can minimize the disturbance on the existing converged design. In this paper, we address the CVE (Crosstalk Violation Elimination) problem. Due to the changes in a multiple layer routing design, the total capacitive crosstalk on some signal wire segments on a layer may be larger than their allowable bounds after post-layout timing/noise analysis. The target is to find a new routing solution without crosstalk violations under certain constraints which help to keep the new design close to the original one. We propose a two-stage algorithm to solve CVE problems, and present optimization strategies to speed up the execution. Experimental results demonstrate the efficiency and effectiveness of our algorithm.

The antenna problem is a phenomenon of plasma-induced gate-oxide degradation. It directly affects manufacturability of very large scale integration (VLSI) circuits, especially in deep submicron technology using high-density plasma. Diode insertion is a very effective way to solve this problem. Ideally, diodes are inserted directly under the wires that violate antenna rules. But in today's high-density VLSI layouts, there is simply not enough room for "under-the-wire" diode insertion for all wires. Thus, it is necessary to insert many diodes at legal "off-wire" locations and extend the antenna-rule violating wires to connect to their respective diodes. Previously, only simple heuristic algorithms were available for this diode insertion and routing problem. In this paper, we show that the diode insertion and routing problem for an arbitrary given number of routing layers can be optimally solved in polynomial time. Our algorithm guarantees finding a feasible diode insertion and routing solution whenever one exists. Moreover, we can guarantee to find a feasible solution to minimize a cost function of the form /spl alpha//spl times/L+/spl beta//spl times/N, where L is the total length of extension wires and N is the total number of vias on the extension wires. Experimental results show that our algorithm is very efficient.

In this paper, we present an integrated approach for floorplanning and bus planning, i.e., bus-driven floorplanning (BDF). We are given a set of circuit blocks and the bus specifications (i.e., the net list of blocks for the buses). A feasible BDF solution is a placement of all circuit blocks such that each bus can be realized as a rectangular strip (horizontal or vertical) going through all the blocks connected by the bus. The objective is to determine a feasible BDF solution that minimizes the floorplan area and the total bus area. Our approach is based upon the sequence-pair floorplan representation. After a careful analysis of the relationship between bus ordering and block ordering in the floorplan represented by a sequence pair, we derive feasibility conditions on sequence pairs that give feasible BDF solutions. Experimental results demonstrate the efficiency and effectiveness of our algorithm.

The routing channels of an FPGA consist of wire segments of various types providing the tradeoff between performance and routability. In the routing architectures of recently developed FPGAs (e.g., Virtex-II), there are more versatile wire types and richer connections between them than those of the older generations of FPGAs (e.g. XC4000). To fully exploit the potential of the new routing architectures, it is beneficial to perform wire type assignment for all channels as an intermediate stage between global routing and detailed routing. In this paper, we present a wire-type assignment algorithm that is based on iteratively applying min-cost max-flow technique to simultaneously route many nets. At each stage of the network flow computation, we have guaranteed optimal result in terms of routability and delay cost. We use the routing architecture of the Virtex-II FPGAs from Xilinx as a target architecture in our experiments. Experimental results show that our algorithm outperforms the traditional sequential net-by-net approach.

Macroblock pin assignment and routing are important tasks in physical design. Existing algorithms for these problems can be classified into two categories: 1) a two-step approach where pin assignment is followed by routing and 2) a net-by-net approach where pin assignment and routing for a single net are performed simultaneously. However, none of the existing algorithms is "exact" in the sense that they may fail to route all of the nets even though a feasible solution exists. This remains to be true even if only two-pin nets with fixed pins between two blocks are concerned. In this paper, we consider the problem of two-pin net connections from one macroblock to all of the other blocks, and present the first polynomial-time exact algorithm for simultaneous pin assignment and routing for all of the two-pin nets between one block (source block) and all of the other blocks. In addition to finding a feasible solution whenever one exists, it guarantees to find a pin-assignment/routing solution with minimum cost /spl alpha//spl middot/W+/spl beta//spl middot/V, where W is the total wire length and V is the total number of vias. Our algorithm has various applications. 1) It is suitable in engineering change order (ECO) situations where the existing solution is modified incrementally. 2) Given any pin assignment and routing solution obtained by any existing method, our algorithm can be used to increase the number of routed nets and reduce the routing cost. Furthermore, it provides an efficient algorithm for the pin assignment and routing problem of all of the blocks. The method is applicable to both global and detailed routing with arbitrary routing obstacles on multiple layers. Experimental results demonstrate its efficiency and effectiveness.

The buffer block methodology has become increasingly popular as more and more buffers are needed in deep-submicron design, and it leads to many challenging problems in physical design. In this paper, we present a polynomial-time exact algorithm for integrated pin assignment and buffer planning for all two-pin nets from one macro block (source block) to all other blocks of a given buffer block plan as well as minimizing the total cost α ċ W + Β ċ R for any positive α and Β where W is the total wire length and R is the number of buffers. By applying this algorithm iteratively (each time pick one block as the source block), it provides a polynomial-time algorithm for pin assignment and buffer planning for nets among multiple macro blocks. Experimental results demonstrate its efficiency and effectiveness.

Antenna problem is a phenomenon of plasma induced gate oxide degradation. It directly affects manufacturability of VLSI circuits, especially in deep-submicron technology using high density plasma. Diode insertion is a very effective way to solve this problem Ideally diodes are inserted directly under the wires that violate antenna rules. But in today's high-density VLSI layouts, there is simply not enough room for "under-the-wire" diode insertion for all wires. Thus it is necessary to insert many diodes at legal "off-wire" locations and extend the antenna-rule violating wires to connect to their respective diodes. Previously only simple heuristic algorithms were available for this diode insertion and routing problem. In this paper we show that the diode insertion and routing problem for an arbitrary given number of routing layers can be optimally solved in polynomial time. Our algorithm guarantees to find a feasible diode insertion and routing solution whenever one exists. Moreover we can guarantee to find a feasible solution to minimize a cost function of the form /spl alpha/ /spl middot/ L + /spl beta/ /spl middot/ N where L is the total length of extension wires and N is the total number of Was on the extension wires. Experimental results show that our algorithm is very efficient.

Design ECO commonly happens in industry due to constraints or target changes from manufacturing, marketing, reliability, or performance. At each step, designers usually want to modify the existing solution incrementally and keep the design as close as possible to the existing one. In this paper, we address the PSO (Power rail - Signal wire Overlap) problem which solves overlaps between power rails and signal wires due to the changes in power rail design on the top layer of a multiple layer routing region. PSO problems are frequently caused by changes from power delivery system or package design. The new routing solution satisfies the following constraints: 1) Keep the routing of power rails in the new design unchanged. 2) Only the routing of the top two layers is changed. 3) Horizontal (vertical) signal wire segments on the top layer can only move up/down (left/right). At the same time, the new routing solution keeps the routing pattern unchanged. This requires: a) If one end point of a horizontal (vertical) wire segment on the top layer is a fixed pin, this segment can not move. b) If vertical (horizontal) projections of two horizontal (vertical) signal wire segments have overlaps, then the up/down (left/right) relationship should not be changed. c) If two horizontal (vertical) segments belonging to different nets are on the same track, their left/right (up/down) relationship should not be changed as long as the two segments still exist in the new solution. 4) For each signal wire segment, the deviation (i.e., the difference between its new position and the old one) should not exceed the user-defined allowable deviation bound. Different bounds can be set on different segments. We propose two algorithms to solve the PSO problem. Both algorithms guarantee to find a feasible solution as long as one exists. One is faster, while the other makes effort to minimize the total deviation as well as the max deviation. According to time and quality requirements, users can choose an appropriate algorithm to solve the problem. For a set of industrial test circuits, we were able to remove all overlaps between power rails and signal wires with minimal wire deviation.

Buffer insertion and wire sizing are critical in deep submicron VLSI design. This paper studies the problem of constructing routing trees with simultaneous buffer insertion and wire sizing in the presence of routing and buffer obstacles. No previous algorithms consider all these factors simultaneously. Previous dynamic programming based algorithm is first extended to solve the problem. However, with the size of routing graph increasing and with wire sizing taken into account, the time and space requirement increases enormously. Then a new approach is proposed to formulate the problem as a series of graph problems. The routing tree solution is obtained by finding shortest paths in a series of graphs. In the new approach, wire sizing can be handled almost without any additional time and space requirement, Moreover, the time and space requirement is only polynomial in terms of the size of routing graph. Our algorithm differs from traditional dynamic programming, and is capable of addressing the problem of inverter insertion and sink polarity. Both theoretical and experimental results show that the graph-based algorithm outperforms the DP-based algorithm by a large margin. We also propose a hierarchical approach to construct routing tree for a large number of sinks.

Macro-block pin assignment and routing are important tasks in physical design planning. Existing algorithms for these problems can be classified into two categories: 1) a two-step approach where pin assignment is followed by routing, and 2) a net-by-net approach where pin assignment and routing for a single net are performed simultaneously. None of the existing algorithms is "exact" in the sense that the algorithm may fail to route all nets even though a feasible solution exists. This remains to be true even if only 2-pin nets between two blocks are concerned. In this paper, we present the first polynomial-time exact algorithm for simultaneous pin assignment and routing for 2-pin nets from one block (source block) to all other blocks. In addition to finding a feasible solution whenever one exists, it guarantees to find a pin-assignment/routing solution with minimum cost /spl alpha//spl middot/W + /spl beta//spl middot/V, where W is the total wirelength and V is the total number of vias. Our algorithm has various applications and is applicable to both global and detailed routing with arbitrary routing obstacles on multiple layers. Experimental results demonstrate its efficiency and effectiveness.