Preliminary Studies on PCB Routing

Edwin Ng
Supervisor : Professor Richard Newton

1. Introduction

In this report, a new methodology of doing PCB routing is presented. This new methodology allows 45 degrees and multi-layer routing. More importantly the method guarantees to find the solution, if one exists, in much less time compared to other routers like the maze router. It proceeds in two phases:

  1. Global routing of the overall board
  2. Detailed routing in each sub-region

2. Global Routing Region Decomposition

2.1 Regional Decomposition

Given the results of the placement phase of the layout, and based on the predefined design rule, it is possible to determine the location and the size of the obstacles present in the netlist. To facilitate 45 degrees rounting, it is best to approximate the corners of obstacles by octagonal lines (Figure 1).

Figure 1 Typical obstacles in our PCB routing model

By using the scan line algorithm, we can dissect the free routing area into trapezoids (Figure 2). The run-time complexity of the operation is proven to be O(nlogn). While the horizontal and vertical scanning may produce different results, there are claims that such asymmetry won't impair the quality of the result. We will verify this claim after we have implemented the prototype. For now, we will just use one of the scanning orientation.

Figure 2 : Routing area after dissection

While the trapezoidal dissection approach is intuitively attractive, it nonetheless complicates the global routing phase significantly, since we have almost three times more trapezoids to deal with as compared to the case where we can approximate the corners by octhogonal lines and thus dividing the regions into rectangles instead (Figure 3). This will be one of the experiments we will try out in our prototype implementation. Three dissection strategies will be implemented :

  1. Trapezoidal dissection
  2. Rectangular dissection
  3. Rectangular dissection but exercise the trapezoidal dissection in the re-route phase of the routing.

Figure 3 : Regional dissection based on rectangular obstacles

2.2 Construction of the Connectivity Graph

Each sub-region (either rectangular or trapezoidal) formed in the last operation are then represented by nodes in a connectivity graph. If two sub-regions of the same type touch, an edge connecting the nodes will be formed (Figure 4).

Each edge in the connectivity graph formed will be assigned a cost function. This cost is the distance of the trapezoid mid-points, weighted by the sheet resistance of the routing layer.

Figure 4 : Regions after linking the obstacles to form a connectivity graph

2.3 Linking Different Layers

After creating the sub-graphs in each routing layer, we need to connect them by contact edges. A contact edge represents the possibility to generate an interconnect between the trapezoids (rectangles) in different layers. The cost of creating a contact depends on the technology and we allow the user to control the use of contacts by defining the cost Cc as followed :

where

2.3 Best Path Calculation

After constructing the complete connectivity graph, we can then use the Dijkstra algorithm to find the path with the lowest sum of weights between any source and sink nodes. We choose to use the AVL-tree as our data structure, so that we can attain an upper time bound of O(nlogn).

3. Detailed Routing

After the global routing is finished, the following information should be ready on hand :
  1. the number of nodes (results of the scanning).
  2. the number of pins (given).
  3. the nets to be routed (given).
  4. for each net to be routed, the nodes to be used (results of the Dijkstra method).

By examining the information in (4), we can determine for each node in the graph, which nets out of (2) will be entering or leaving the node. The above information is depicted in the following table :

Table 1 : Information about the in-nets and out-nets for each dissected sub-region

Furthermore, it is also possible to know the starting node and the ending node of each net based on the above information. This is useful because one of the consequences of region decomposition is the segmentation of each original net to be routed. It is not hard to see that the routing of the starting and ending net segment of any original net is the easiest. This will simplify the analysis to be done on each node discussed below.

In the following discussion, we will transform each node in the connectivity graph back to its original shape (assume trapezoid from now on), We will need to do a detailed routing on each node to complete all the net connections.

3.1 "Pseudo Switch Box Routing"

The detailed routing to be done in each trapezoid is similar to a switch box routing, but it also exhibits major differences. This is illustrated in Figure 5.

Figure 5 Assuming that we are doing a vertical scan on the region, then each net can only enter or leave the trapezoid from above or below. Only the pins on the left or right side of the trapezoid are `real', the ones on the top or bottom are pseudo pins, in a sense that while we are aware of their existence along the entrance and exit, their exact position are yet to be determined.

There are three different kinds of nets that may be present in the trapezoid :

  1. Those which originate from the trapezoid.
  2. Those which terminate in the trapezoid.
  3. Those which pass by the trapezoid.
To make the analysis more tractable, we assume the location of the nets entering the trapezoid is given as a priori (Figure 6). Then we only have to do the pseudo pin assignment on the leaving nets.

Figure 6

We will then route those nets that begin or terminate inside the trapezoid, To leave the most open space for any subsequent routing, we will route those nets along the boundary of the trapezoid (Figure 7).

Figure 7

The routing or the remaining nets proceeds as followed :

Determine the position of the trapezoid to be entered with respect to the current trapezoid.