Routing is a crucial step in the design of integrated circuits. The preceeding placement step determines the location of each active element of an IC. Routing is then the process of creating all the wires needed to properly connect all the placed components, while obeying the design rules of the process. From the user point of view, place and route are often lumped together as necessary physical operations. From an algorithm point of view, placement and routing are very different. Optical Microscope image of an integrated circuit showing defects in the aluminium layer deposition. ... Placement is an essential step in electronic design automation - the portion of the physical design flow that assigns exact locations for various circuit components within the chip’s core area. ... Place and Route is a stage in design of: Printed circuit boards at which components are graphically placed on the board and the wires drawn between them. ... Placement is an essential step in electronic design automation - the portion of the physical design flow that assigns exact locations for various circuit components within the chip’s core area. ...

Routing is the blue-collar work of IC design. There are no conceptual difficulties and very little use of higher mathematics. Almost everything is based on a few basic techniques which have been known for a long time — the papers describing these were published before most readers of this work were born. The success of a router is determined by hard work, heuristics, and implementation — reducing memory usage, increasing speed, and dealing with a multitude of obscure but necessary design rules. Perhaps as a result, almost all state-of-the-art routers are built in industry, and relatively little is published about them. In contrast, the placement problem can be attacked using a wide variety of techniques, some quite sophisticated, and many academic groups develop their own placers. A placement contest at ISPD in 2005, using state-of-the-art examples, drew nine contestants from academia. A similar contest for routing would probably not find even one academic router that can solve a state-of-the-art routing problem.

Almost every problem associated with routing is known to be intractable. The simplest routing problem, finding the shortest route for one net in one layer with no obstacles and no design rules, is called the Steiner tree problem. It is NP-hard if all angles are allowed and NP-complete using horizontal and vertical wires. Variants of channel routing are shown to be NP-complete, as is routing considering crosstalk, via minimization, and so on. Routers therefore, seldom attempt to find an optimum result. Instead, almost all routing is based on heuristics trying to find a solution that is good enough. In computer science, computational complexity theory is the branch of the theory of computation that studies the resources required during computation to solve a given problem. ... The Steiner tree problem is a problem in combinatorial optimization. ... In computational complexity theory, NP-hard (Non-deterministic Polynomial-time hard) refers to the class of decision problems that contains all problems H such that for all decision problems L in NP there is a polynomial-time many-one reduction to H. Informally this class can be described as containing... In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use... In computer science, besides the common use as rule of thumb (see heuristic), the term heuristic has two well-defined technical meanings. ...

A specific concern for IC routers is that the design rules vary considerably from layer to layer. The allowed width and spacing on the lower layers may be four or more times smaller than the legal widths and spacings on the upper layers. This introduces many additional complications not faced by routers for other applications such as PC boards or MCMs. Particular difficulties ensue if the rules are not simple multiples of each other, and when vias must traverse between layers with different rules.

Types of Routers

The task of all routers is the same. They are given some pre-existing polygons consisting of pins (also called terminals) on cells, and (optionally) some pre-existing wiring called preroutes. Each of these polygons is associated with a net, usually by name or number. The primary task of the router is to create geometries such that all terminals assigned to the same net are connected, no terminals assigned to different nets are connected, and all design rules are obeyed. A router can fail by not connecting terminals that should be connected (an open), by mistakenly connecting two terminals that should not be connected (a short), or by creating a design rule violation. In addition to correctly connecting the nets, routers may also be expected to make sure the design meets timing, has no crosstalk problems, meets any metal density requirements, and so on. This long list of often conflicting objectives is what makes routing difficult.

The four main types of routers are:

• Maze routers.
• Line probe routers
• Channel routers
• Area routers

References

• Electronic Design Automation For Integrated Circuits Handbook, by Lavagno, Martin, and Scheffer, ISBN 0849330963 A survey of the field, from which this summary was derived, with permission.

• C.Y. Lee, An algorithm for path connections and its applications, IRE Trans. Electronic Comput., EC-10, 346–365, 1961. One of the first descriptions of a maze router.

• D.W. Hightower, A solution to line-routing problems on the continuous plane, DAC’69: Proceedings of the 6th Annual Conference on Design Automation, ACM Press, 1969, pp. 1-24. One of the first descriptions of a line probe router.

• J. Reed, A. Sangiovanni-Vincentelli, and M. Santamauro, A new symbolic channel router: YACR2, IEEE Trans. CAD, pp. 203–219, 1985. Probably the most widely known channel router.