PCB routing methods continue to evolve, and flexible routing techniques can reduce wire length and free up space on a PCB.
Traditional PCB routing is limited by fixation of coordinates of wires and by the absence of any-angle traces. Removing these restrictions, we can significantly improve quality of routing. Including real-world examples, this article covers the advantages of any-angle routing, the advantages of flexible routing, and a new algorithm for constructing Steiner trees.
Background
First, we would like to introduce some terms [1 – 3]. Let's define any-angle routing as wire routing that uses both segments and arcs at any angle. It is wire routing, but is not limited to using only line segments with 90 and 45-degree angles. Topological routing is wire routing without snapping to a grid and coordinates. No regular or irregular grids like shape-based routers are used. And let's use the term flexible routing for wire routing without shape fixing and with the following possibility of their shift with real-time wire shape recalculation. Only the arcs of circles from obstacles and common tangents to them are used to form the shape of wires [4, 5]. (Obstacles include contacts, coppers, keepouts, vias and other objects.)
Figure 1 shows parts of two PCB models. There are green wires and red wires on different layers of the PCB model. Blue circles are vias. A red component is highlighted. In addition, there are some red circle contacts. There is a model using only line segments and 90 degree angles between them in the Figure 1a. And there is PCB model using arcs and any-angles in Figure 1b. Maybe any-angle routing looks unusual, but it has a lot of advantages. It is routed similarly to how engineers did it manually half a century ago.
Figure 2 shows a real manually routed PCB which was developed by an American company Digibarn in 1972. This is a PCB of a computer based on the Intel 8088. Virtually the same any-angle routing is shown in Figure 2 as in the Figure 1b. Why did people use any-angle routing. Because it has many advantages.
Advantages of Any-Angle Routing
There are several advantages to any-angle routing. First, space can be saved on a PCB by not using the angles between the segments. (A polygon always takes up more space than the inscribed circle.)
Conventional auto-routers can route only three wires between closely spaced components (on the left and in the center in the Figure 3). The space we have during any-angle routing is enough to route four wires on the same path without violating design rules checking (DRC), on the right in the Figure 3.
Suppose we have a square chip and want to connect the chip contacts with two other lines of contacts (see Figure 4). It takes a large area using only 90 degree angles (see Figure 4 top).
Using any-angle routing we can shorten the distances between the chip and other contacts (Figure 4 middle). And, it reduces the area. In this example, area shrinks from 30 cm2 to 23 cm2.
Any-angle turning of the chip delivers even greater effect. In this example, the area was reduced from 23 cm2 to 10 cm2 (Figure 4 bottom). Figure 5 shows a real PCB. The any-angle routing with chip turning was the only way to route this board. This is not just a theory but it is actually applied solution (sometimes the only possible).
Figure 6 shows an example of a simple PCB. The result of a topological router is shown in Figure 6a while the result of the best shape-based auto-router is in Figure 6b. There is a picture of a real PCB in the figure 6c. The best auto-routers cannot route this board because the components are turned at an arbitrary angle. You need more area, and the device will be larger without turned components.
Electromagnetic Interference (EMI)
Layout is greatly improved if there are no parallel wire segments, which are often the source of crosstalk. The rate of crosstalk increases linearly as the parallel segments get longer, and it increases inverse quadratic as the distance between them increases. Let e be the crosstalk rate generated by two parallel 1mm-long segments with distance d between them (see Figure 7).
If the segments are at an angle, the cross-talk rate goes down as the angle increases. It does not depend on the wire length and is limited by the value
where α is the angle between the segments.
Consider three kinds of wire routing. On the left in Figure 8 (the layout at 90 degrees), there is a maximum wire length and a maximum level of EMI due to the parallel segments. In the middle of Figure 8 (the layout at 45 degrees), wire length and the EMI level are decreased. On the right in the Figure 8 (any-angle), we have minimum wire length, there are no parallel segments, and the level of interference is negligible.
It follows that any-angle routing helps decrease the total wire length and reduce significantly electromagnetic crosstalk. Moreover you should remember the influence on the signal delay (wire direction should not be parallel and not perpendicular to the PCB glass fabric directions).
Flexible Routing Advantages
Manual and automatic movement of components is carried out without damaging the wiring in flexible routing. The router automatically calculates the optimum shape of the wire (subject to necessary clearances). It significantly reduces the time to edit the topology, enabling multiple rerouting of wires for control compliance with the restrictions. Figure 9a shows a PCB design and the result of shifting vias and branching points can be seen in Figure 9b.
In the process of an automatic movement, branching points of wires and vias are adjusted to the optimal positions (as in Figure 9c).
In most computer-aided design (CAD) systems, the route interconnection problem is reduced to the problem of sequential search for paths between pairs of points in the maze formed by pads, keepouts, and routed wires. When a path is found, it is fixed and becomes part of the maze. Sequential routing has the disadvantage that the result may depend on the order in which wires are routed.
The problem of "getting stuck" in a local minimum occurs when the quality of the topology is still far from perfect, but no matter which single wire you reroute, this cannot improve the quality of the wiring. This is a very serious issue in all CAD systems that use sequential optimization.
It is useful to apply a procedure for clinch elimination [6]. A clinch of wires is a situation where a wire from one net goes around an object from another net if a wire is incident to the object. Rerouting of one wire does not correct the situation.
Figure 10a shows an example of a clinch. A lit red wire goes around a contact from another net and an unlit red wire is incident to the object. Figure 10b shows the result of automatic procedures. In a second situation (on another layer) a lit green wire was automatically refined (rerouted) with a change of a layer (from the green-colored layer to the red-colored layer).
In the Steiner tree, all connections must be segments connecting the vertices (terminal and additional). At the top of each additional vertex, three segments must converge, and in the terminal there must be no more than three. The angle should not be less than 120 degrees between the segments converging at one vertex. To construct a Steiner tree with the performance of these sufficient conditions is not difficult, but it will not necessarily be minimal. The gray Steiner tree is not optimal in the Figure 11 but the black one is.
In the design of real communications, the presence of different kinds of obstacles must be taken into account. They limit the ability to use both algorithms for constructing a minimum spanning tree (Figure 12a) and geometric methods for constructing Steiner trees (Figure 12b). Obstacles are shown in a grid.
We suggest starting from any final vertex. If there is more than one adjacent final vertex, you should choose the one that will allow you to continue to work with the second one. This is determined by angles.
The main mechanism is a force-based algorithm that calculates the forces acting on additional vertices and iteratively moves them to a point of equilibrium (magnitudes and directions of forces depend on wires in the vicinity of branch points). If the angle between a pair of segments that are incident to a vertex (terminal or additional) is less than 120 degrees (Figures 13a and 13b), you can add a branch point (Figures 13b and 13d). Optimize the position of the vertices using the force-based algorithm (Figures 13c and 13d). The result is in the Figure 13e.
It should be noted that just sorting all angles in descending order and adding new vertices in this order cannot work. The result will be worse. After adding a new node, you should check the minimality of a four-contacts subnet:
1. If the vertex was added adjacent to the other additional vertex, check the minimum four-contacts network (Figure 14a).
2. If the four-contacts network is not minimal, choose a pair of "diagonal" (belonging to the diagonal of the quadrilateral) terminal or virtual terminal nodes (virtual terminal node – wire bending).
3. A segment connecting the terminal (virtual terminal) to the nearest added vertex is replaced by a segment connecting the terminal (virtual terminal) to a far-added vertex (Figure 14b).
4. Optimize the position of the vertices using the force-based algorithm (Figure 14c).
This method does not guarantee the construction of a minimal network, but, in contrast to other approaches, it allows minimization of the network length without enumeration. Moreover it takes into account the area in which the terminal connection is prohibited and also the number of terminal nodes can be arbitrary.
Other Advantages
There are also some interesting advantages of any-angle flexible routing. For instance, you can create serpents in parallel if you can automatically shift many objects with automatically real-time wire shape recalculation. It allows for better use of space, minimizes the number of iterations, and allows the use of tolerances flexibly (see Figure 15). If there are two serpents that intersect each other, the auto-router decreases the size of one of them or both. It depends on rule priority.
BGA Components Routing
Next, consider BGA components routing [7]. In the traditional approach "from the periphery to the center" the number of channels to the periphery decreases by 8 with each successive layer (due to the reduction of the perimeter). For example, 10 layers are required for the component 28 x 28 with 784 contacts. There is escape routing for some layers in the figures. A quarter of a BGA is shown in Figure 16.
At the same time, when there is routing "from the center to the periphery" the number of channels required to exit to the periphery does not change from layer to layer. This can save a significant number of layers. For a component 28 x 28 size, 7 layers are enough, and for even greater sizes, a double win can be achieved. A quarter of a BGA is shown in Figure 17.
Figure 18 shows an example of BGA routing. When there is routing "from the center to the periphery" we can route all nets (Figure 18b). An any-angle topological auto-router can do this. A traditional auto-router cannot route this example (Figure 18a).
Real PCB Example
Figure 19 shows an example of a PCB where an engineer has reduced the number of signal layers from six to four (in comparison to the specification). In addition, the engineer spent only half a day on the routing of this PCB.
Conclusions
This paper introduces methods to speed up and improve PCB routing. The examples of real printed circuit boards are shown. Flexible any-angle routing and non-preferred directions routing in layers allows you to:
1.reduce the total wire length
2.reduce the entire wire area
3.reduce the level of cross-electromagnetic interference, both by reducing the length of the wire and by reducing the level of parallelism
4.reduce the delay mismatch in the group of signals or in the differential signal due to the heterogeneity of PCB material
5.improve the quality of BGA component routing
6.improve the structure of nets by constructing Steiner trees
7.easily change the nets topology
References
1.S. Luzin, O. Polubasov, "Advantages of Isotropic PCB Routing," Printed Circuit Design & Fab, #6, pp. 38 - 40, Fab. 2009.
2.O. Polubasov, "Routing Concepts of a Topological Router CAD System," Onboard Technology, pp. 11 - 15, May 2011.
3.S. Yu. Luzin, Yu. T. Lyachek, G. S. Petrosyan, O. B. Polubasov, "Models and algorithms for computer-aided design of electronic and computer equipment". – St. Petersburg: BHV-Petersburg, 2010. – 224 p. (in Russian)
4.S. Gao, M. Jerrum, M. Kaufmann, K. Mehlhorn, W. Rulling, C. Storb. On continuous homotopic one layer routing // in Proc. 4th Annu. ACM Symp. Computational Geometry. – 1988. – pp. 392–402.
5.Yu. Popov, S. Popov, Calculation of the Minimum Path Length Wire in the Printed Wiring Topological Routing // Scientific And Technical Journal Of Information Technologies, Mechanics And Optics. – 2012. – # 6 (82). – pp. 117–123. (in Russian)
6.S. Luzin, S. Popov, Yu. Popov. Clinches Removal Automation in the Printed Circuit Topology // Scientific And Technical Journal Of Information Technologies, Mechanics And Optics. – 2012. – # 4 (80). – pp. 116–121. (in Russian)
7.S. Luzin, O. Polubasov, G. Petrosjan, "Problems in Routing of PCB with BGA components," Onboard Technology, pp. 12 - 15, November 2009.
