Flip-Chip routing

 

Basically, our problem described below is followed by the instructions from 2014 CAD contest [1]. Given a set of I/O driver pads and a set of bump pads on a single layer, and assume the number of driver pads is the same as the number of bump pads. One driver pad needs to connect with one bump pad. The problem specifications are:

(1) To find the path connecting between each pair of driver and bump pads with
minimal total wire length.

(2) All the paths must be composed of horizontal or vertical wires with specified wire width, and without any open or short.

(3) All the wires must satisfy the minimum spacing constraint.

(4) This is a grid-based routing problem. It means all the wires must be on grid.

The I/O driver pads are in the boundary of the design; while, the bump pads are clustered and placed inside the design. The program has to find the path, formed with vertical and horizontal wires, connecting each driver pad and bump pad in only one single layer. The driver and bump pads are one-to-one mapped. That is, we assume all nets are 2 pin nets. There is an example shown in Figure 1. White rectangles represent the bump pads; black rectangles represent the driver pads.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Methodology

The methodology is mainly stemmed from [2]. But in the related work, the algorithm is not properly defined to solve this problem. We derive the LCS and MPSC from [2][3]. But still we have to build up the mapping function to map the routing pair onto the real pad and at the same time to solve the “fly-line” problem.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Depiction of functions

   (a) Alignment:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

As the figure 3 shows, we change the two-dimensional layout into a one-dimensional problem. Namely, we change the “bump square” into row vectors from innermost area outwardly.

   (b) LCS function:

We find the LCS (longest common subsequence) of every row vector and the driver vector from the inside out (figure 4). By doing so, we label the bump as “DirectedRoute” and “UnDirectedRoute” respectively whether they belong to LCS or not.

   (c) MPSC function:

In MPSC, which refers to “Maximum Planar Subset of Nets in a Channel”[3], we insert the virtual node from former layer to next layer in proper ordinal position (figure 5). Next, we run the “ring-by-ring” sub-function to check the “Routability” of every layer, saying that to seek the maximum directly routed pairs without any crossing lines, like demonstration in the figure 6.

After finding the directly routed pairs, we take these pairs into the “In-circle” function, which means to bind one node to another across two adjacent layers. While other nodes, we will put them into the “Out-circle” function.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

   (d) “In-circle”➔box-mapping and path-assignment function:

First, we proposed a concept of “box” by combine a 2X2 square of bump nodes depends on its original absolute coordinates. It means that we put the row vectors back to its location on the pad, just as figure 8 below.

Then we connect the pairs in which nodes are labeled “In-circle”. By our definition, “In-circle” means the real bump node in inner box can be directly routed to a virtual node in outer box. For example in figure 9, box 5 is the inner box while other 8 boxes are outer part, and bump i assigned to driver i supposedly. In Path-assignment, we decide the shortest path from virtual node i to bump node i, for the path should not cross the inner box 5(Crossing inner box implies that node pair has to be connected across more than 2 layers, like the green lines in figure 7, that is  what the term “Out-circle” has been declared for.)

After assigning the path of node i, we check each node pair from on the edge of every boxes one by one following the direction of the green dotted line in figure 9. But the number of paths available in every box is limited for the spacing and width given in specification. Therefore, in this step, we also have to assure that the number of paths we’ve assign won’t exceed the limitation of every box.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

   (e) Wire-mapping function:

In last step, we have to assign every wire in the boxes to absolute coordinate. And all wires have to be connected perpendicularly and vertically according to problem requirements. Besides, they have to be connected in the smallest “area-consumption” to make sure that in every edge of box we can put into as more paths as we want. Last part but not the least, we connect every virtual nodes and real bump nodes around the whole “bump square” to the drivers, then her we got the layout of flip-chip routing.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Performance evaluation

We visualized our output file by Matlab. From figure 10 and 11 below, we can see that although we successfully routed some driver-bump pairs, but will some of them exceeded the boundary limitation of the board. Besides, we didn’t complete the “Out-circle” function and it turns out to be “fly-line” problems.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Reference

[1]2014 CAD contest website http://cad_contest.ee.ncu.edu.tw/

[2]C.-W Lin, P.-W Lee, Y.-W. Chang, C.-F Shen, W.-C Tseng, ”An Efficient Pre-assignment Routing Algorithm for Flip-Chip Designs”, IEEE Transactions on computer-aided design of integrated circuits and systems, Vol. 31, No. 6, June 2012

[3] Kenneth J. Supowit, ”Finding a Maximum Planar Subset of Nets in a Channel”, IEEE Transactions on computer-aided design, Vol. CAD-6, No. 1, Jan 1987