Routing (electronic design automation): Difference between revisions

Revision as of 01:43, 25 September 2018

Revision as of 01:44, 25 September 2018

Line 1:

{{About|designing integrated circuits, as part of [[electronic design automation]]|other kinds of routing|routing (disambiguation)}}

In [[electronic design]], '''wire routing''', commonly called simply '''routing''', is a step in the design of [[printed circuit board]]s (PCBs) and [[integrated circuit]]s (ICs). It builds on a preceding step, called [[Placementplacement (EDAelectronic design automation)|placement]], which determines the ___location of each active element of an IC or component on a PCB. After placement, the routing step adds wires needed to properly connect the placed components while obeying all [[design rules]] for the IC. Together, the placement and routing steps of IC design are known as [[place and route]].

The task of all routers is the same. They are given some pre-existing polygons consisting of [[Pinpin (electronics)|pinspin]]s (also called terminals) on cells, and optionally some pre-existing wiring called preroutes. Each of these polygons are associated with a [[net (electronics)|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 connect the nets, routers may also be expected to make sure the design meets timing, has no [[crosstalk]] problems, meets any metal density requirements, does not suffer from [[antenna effect]]s, and so on. This long list of often conflicting objectives is what makes routing extremely difficult.

Almost every problem associated with routing is known to be [[Computational complexity theory|intractable]]. The simplest routing problem, called the [[Steiner tree]] problem, of finding the shortest route for one net in one layer with no obstacles and no design rules is [[NP-hard]] if all angles are allowed and [[NP-complete]] if only horizontal and vertical wires are allowed. Variants of [[Channel router|channel routing]] have also been shown to be NP-complete, as well as routing which reduces [[crosstalk]], number of [[via (electronics)|via]]s, and so on.