text: We present a deep, fully convolutional neural network that learns to route a circuit layout net with appropriate choice of met al tracks and wire class combinations. Inputs to the network are the encoded layouts containing spatial location of pins to be routed. After 15 fully convolutional stages followed by a score comparator, the network outputs 8 layout layers (corresponding to 4 route layers, 3 via layers and an identity-mapped pin layer) which are then decoded to obtain the routed layouts. We formulate this as a binary segmentation problem on a per-pixel per-layer basis, where the network is trained to correctly classify pixels in each layout layer to be 'on' or 'off'. To demonstrate learnability of layout design rules, we train the network on a dataset of 50,000 train and 10,000 validation samples that we generate based on certain pre-defined layout constraints. Precision, recall and @math score metrics are used to track the training progress. Our network achieves @math on the train set and @math on the validation set. We use PyTorch for implementing our model. Code is made publicly available at this https URL .
  @cite_18: 
  @cite_14: Three-dimensional (3D) integration technology packs together multiple active device dies, achieving a higher level of integration within a given footprint. However, due to an increase in the design volume and complexity, routing has become a challenging problem in 3D IC designs. In this paper, we propose a timing driven routing algorithm for 3D IC with a load balancing method that distributes the capacitance of the interconnections including TSV. In the load balancing step, the sink pins are partitioned to balance the loads within the routing tree. The routing trees are then created by merging the sub-trees that are generated with the balanced group.
  @cite_4: 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.
  @cite_22: 
  @cite_9: In deep sub-micron regime, interconnect delays dominate VLSI circuit design. Thus, construction of cost-effective global routing trees is key to such designs. In order to reduce the interconnect delay, traditional Manhattan (M-) routing architectures are currently being replaced by the diagonal X architectures. A recent routing architecture is based on Y interconnects, involving the pervasive use of 0 spl deg , 60 spl deg , and 120 spl deg oriented global and semi-global wirings. Unlike the X-routing, Y-routing Is observed to support regular routing grid, which as important for simplifying manufacturing processes and routing and design rule checking algorithms. In this paper, we propose a novel Y-routing algorithm which can solve reasonably sized problems in nominal time. The proposed method is capable of finding routing solutions for problem instances which could not be solved in reasonable time by some recently reported methods. Moreover, it can be easily extended for routing with any uniform orientation.
  @cite_1: 
  @cite_17: We present an algorithm for simultaneously finding a rectilinear Steiner tree T and buffer insertion points into T. The objective of the algorithm is to minimize a cost function (e.g., total area or power) subject to given timing constraints on the sinks of the net. An interesting side-effect of our approach is that we are able to derive an entire cost delay tradeoff curve for added flexibility. The solutions produced by the algorithm are optimal subject to the constraint that the routing topology be induced by a permutation on the sinks of the net. We show that high quality sink permutations can be derived from a given routing structure such as the minimum spanning tree. This derivation provides an error bound on the minimum area solution induced by the permutation. The effectiveness of our algorithm is demonstrated experimentally.
  @cite_6: The channel routing problem is a special care of the wire routing problem when interconnections have to be performed within a rectangular strip having no obstructions, between terminals located on opposite sides of the rectangle. We present here a new channel routing algorithm, based on reduction of the problem to the case of a (2 x n) grid and on consistent utilization of a "divide and conquer" approach. For the current implementation of the algorithm, the running time is proportional to N x n x log (m), where N is the number of nets, n is the length of the channel (number of columns) and m is the width of the channel (number of tracks). Traditional technological restrictions are assumed, i.e. net terminals are located on vertical grid lines, two wiring layers are available for interconnections - one layer is used exclusively for vertical segments, another for horizontal and vias are introduced for each layer change. This algorithm consistently outperforms several known routers in quality of wiring. We tested the algorithm on several benchmark problems. One of them - Deutsch's "difficult example" - was routed with only 19 horizontal wiring tracks (the absolute minimum for this case), whereas all other known routers required 20 or more tracks.
  @cite_0: 
  @cite_19: 
  @cite_27: 
  @cite_24: A program, called Spider, for routing of interconnections between cells in integrated circuits is presented. It is based on hierarchical algorithms. Special attention is paid to doglegging as the most sensitive part of the routing process. Experimental results obtained on several examples demonstrate the efficiency of the system. >
  @cite_2: During recent days, the large problem space of very large scale integrated (VLSI) circuits has led global routing problem to a NP Complete one. With the advent of three dimensional integrated circuits (3D IC) the problem has become more complex. In this paper, a multi-objective global routing technique is formulated using fuzzy logic to get rid of the limitations of deterministic approaches. During global routing the decision is taken from a fuzzy logic expert system depending upon some generated pre-routing guiding information. Proposed approach is mainly focused on the modern generation 3D ICs. This primary work is mainly incorporated in the standard cell design for 3D ICs. A two-pin global router tool is designed based on the proposed algorithm resulting 85-97 routability in negligible time for ISPD'98 benchmarks.
  @cite_5: Interconnecting two rows of points across an intervening channel is an important problem in the design of LSI circuits. The most common methodology for producing such interconnections uses two orthogonal layers of parallel conductors and allows wires to "dogleg" arbitrarily. Although effective heuristic procedures are available for routing channels with this methodology, no efficient optimal algorithm has yet been discovered for the general case problem. We show that such an algorithm is unlikely to exist by establishing that this problem is NP-complete.
  @cite_16: We present a new, “greedy”, channel-router that is quick, simple, and highly effective. It always succeeds , usually using no more than one track more than required by channel density. (It may be forced in rare cases to make a few connections “off the end” of the channel, in order to succeed.) It assumes that all pins and wiring lie on a common grid, and that vertical wires are on one layer, horizontal on another. The greedy router wires up the channel in a left-to-right, column-by-column manner, wiring each column completely before starting the next. Within each column the router tries to maximize the utility of the wiring produced, using simple, “greedy” heuristics. It may place a net on more than one track for a few columns, and “collapse” the net to a single track later on, using a vertical jog. It may also use a jog to move a net to a track closer to its pin in some future column. The router may occasionally add a new track to the channel, to avoid “getting stuck”.
  @cite_20: Motivated by analysis of distributed RC delay in routing trees, a new tree construction is proposed for performance-driven global routing which directly trades off between Prim's minimum spanning tree algorithm and Dijkstra's shortest path tree algorithm. This direct combination of two objective functions and their corresponding optimal algorithms contrasts with the more indirect 'shallow-light' methods. The authors' method achieves routing trees which satisfy a given routing tree radius bound while using less wire than previous methods. Detailed simulations show that these wirelength savings translate into significantly improved delay over standard MST routing in both IC and multichip module (MCM) interconnect technologies. >
  @cite_11: Electrical Engineering Circuits and Electron Devices Routing in the Third Dimension From VLSI to MCMs Naveed Sherwani, Siddharth Bhingarde, and Anand Panyam A volume in the IEEE Press Series on Microelectronic Systems Stuart K. Tewksbury, Series Editor The complex computer chips of tomorrow will consist of not just one or two but several layers of met al interconnect. This makes the interconnect within a chip or a multichip module a three-dimensional problem. This book addresses the algorithmic and cell design issues in chip and MCM routing, with an emphasis on techniques for eliminating routing area. Key features include:a wealth of algorithmsover-the-cell (OTC) routingmulti-layer VLSI thin film MCM routingMCM routinghow to reduce chip sizecoverage of fabrication-specific issues.This book will be of interest to CAD engineers, fabrication engineers, layout engineers, or anyone involved in integrated circuit design. It is also appropriate for use as an advanced-level text on the subject. Books of Related Interest from IEEE Press Microelectronic System Interconnections: Performance and Modeling Edited by Stuart Tewksbury 1994 Hardcover 528 pp IEEE Order No.: PC3004 ISBN 0-7803-0405-5 BiCMOS Integrated Circuit Design with Analog, Digital, and Smart Power Applications Edited by M.I. Elmasry 1994 Hardcover 528 pp IEEE Order No.:PC3467 ISBN 0-7803-0430-6 Codesign: Computer-Aided Hardware Software Engineering Edited by Jerzy Rozenblit and Klaus Buchenreider 1995 Hardcover 464 pp IEEE Order No.:PC4028 ISBN 0-7803-1049-7
summary: The task of producing routes using orthogonal layers of parallel channels and vias at intersections is often tackled heuristically, since an optimal solution does not exist for this NP-complete problem @cite_11 @cite_0 @cite_18 @cite_5 . Previous work in this field @cite_22 @cite_16 @cite_6 @cite_19 @cite_27 @cite_24 mostly rely on explicit rule-based algorithms to tackle parts of this complex task. For instance, Zajc al @cite_24 proposed using hierarchical algorithms for automatic routing of interconnects in two layer channels. Rivest al @cite_16 show a "greedy" heuristic channel router assuming all pins and wiring sit on a common grid. The other class of routers, which have received attention lately, are objective function based. Alpert al @cite_20 proposed a combination of minimum spanning tree (Prim) and shortest path tree (Dijkstra) objectives for performance driven global routing. Constructing routing tree with different objectives was also explored, such as timing objective @cite_14 , buffer insertion @cite_17 and wire sizing objective @cite_4 , congestion and thermal objective @cite_2 @cite_1 . A completely different objective for diagonal routing as opposed to the orthogonal (Manhattan) routing was also proposed @cite_9 .