Routing algorithms for electronic design automation

In electronic design automation (EDA), routing is one of the most important tasks for both printed circuit boards (PCB) and integration circuits (IC). After placement, which determines the location of each component on a PCB or element of an IC, the routing step adds wires needed to properly connect the placed components/elements while obeying all the design rules. The quality of routing has a great impact on the performance of the board/chip. In this dissertation, we study modern PCB routing and the emerging problems in IC routing.;The high pin density and large net count of modern PCBs make manual design the board an extremely time-consuming and error-prone task. In addition, the bus structure routing style and the planar routing constraint further increase the design complexity. The number of layers used also needs to be minimized in order to reduce the fabrication cost. To the best of our knowledge, no mature commercial automated router can handle these problems well. In this dissertation, both bus-based and net-based PCB routing problems are addressed. We first introduce the Rectangle Escape Problem (REP), which is motivated by bus-based escape routing within one component on a PCB. This problem is basically to determine an escape direction for each bus within the component such that the resultant maximum density (a good indicator of the number of layers needed) is minimized. We prove that REP is NP-complete, and show that it can be formulated as an integer linear program (ILP). A provably good approximation algorithm for the REP is developed by applying linear programming (LP) relaxation and a special rounding technique to the ILP. We further study the optimal layer assignment of a set of buses connecting two components on a PCB. This is a theoretically hard problem and we propose a branch-and-bound based algorithm that optimally solves it. Our algorithm is guaranteed to produce a feasible layer assignment of the buses with a minimum number of layers.;We apply our algorithms on industrial data and the experimental results validate our approach. Net-based PCB routing is also studied. We propose an underlying routing graph which correctly models the routing resources of the pin grids on board. We then build a Negotiated Congestion based Escape Router (NCER) by applying the negotiated congestion routing scheme on the constructed routing graph. We compare the performance of NCER with that of the Cadence PCB router Allegro on industrial test cases, and experimental results show that the two routers have comparable routability but complementary behaviors. Therefore, by using NCER as a supplement to Allegro, we can solve a broader range of net-based PCB routing problems.;The emerging problems in IC routing are also studied. Conventional CMOS devices face an increasing number of challenges as their feature sizes scale down. Graphene nanoribbon (GNR) based devices are shown to be a promising replacement of traditional CMOS at future technology nodes. However, all previous works on GNRs focus at the device level. In order to integrate these devices into electronic systems, routing becomes a key issue. We study the GNR routing problem for the first time. We formulate the GNR routing problem as a minimum hybrid-cost shortest path problem on triangular mesh ("hybrid" means that we need to consider both the length and the bending of the routing path). We show that by graph expansion, this minimum hybrid-cost shortest path problem can be solved by applying the conventional shortest path algorithm on the expanded graph. Experimental results show that our GNR routing algorithm effectively handles the hybrid cost. We then study the related routing reliability problem. In practice, the GNR wire segments can have a connection defective rate. Particularly, each wire segment has a survival probability, and thus has a chance to fail, making traditional routing very unreliable. We introduce the routing reliability problem and propose an algorithm flow to solve it. Given an s-t routing path on a routing graph, we try to reinforce the reliability of the routing path by adding redundant wiring segments in such a way that its survival probability is maximized with a reasonable overhead of routing resources. Our proposed algorithm flow is two-fold: (1) generation of candidate redundancy segment via min-cost max-flow; (2) optimal selection among the candidates by dynamic programming. The results of extensive experiments confirm the effectiveness and efficiency of our approach.;Another emerging problem in IC routing that we study is triple patterning lithography (TPL) aware routing. As technology continues to scale to 14nm node, double patterning lithography (DPL) is pushed to near its limit. TPL is a considerable and natural extension along the paradigm of DPL. With an extra mask to accommodate the features, TPL can be used to eliminate the unresolvable conflicts and minimize the number of stitches, which are pervasive in DPL process, and thus smoothen the layout decomposition step. Considering TPL during the routing stage explores a larger solution space and can further improve the layout decomposability. We propose the first triple patterning aware detailed routing scheme, and compare its performance with the double patterning version in 14nm node. Experimental results show that, using TPL, the conflicts can be resolved much more easily and the stitches can be significantly reduced in contrast to DPL.