ASIC Routing by Maze Search
With Ripup/Reroute
(Linsker’s Algorithm)
By:
Tetsuya Akiyama takiyama@andrew.cmu.edu
Li-Ying Stanley Chang liyingc@andrew.cmu.edu
12/12/2002
Introduction:
The problem with traditional sequential maze routing algorithm is that earlier routed wires have higher priority in choosing good paths, and later routed wires are limited by earlier routed wires. Linsker solves this problem by using iterative maze routing algorithm with his unique cost schedule.
The problem for this project is to implement an iterative maze router with Linsker’s algorithm. This problem can be divided into two main parts. The first one is to implement a maze router, and the second part is to implement Linsker’s algorithm. The first part involves minimum spanning trees and routing two-point connections. Vias, bends, and sometimes wire crossings need to be considered as extra cost when routing. The second part is to implement Linsker’s cost functions. This part is harder because there is no exact solution. Writing his algorithm does not guarantee good results. The more important part is to have a good cost function that can minimize the number of bad wires. Linsker did not give a lot of detail in what the cost function looks like, and what values should be used in the cost function.
Formulation:
We assumed that the Ripup/Reroute algorithm is essential to route in tighter packing case. Since the cost function is not stated clearly, we assumed that the CCR of each segment increases with different rate depending on each segment’s NCR. In addition, we assumed that only better wires have to drop the CCR sometime during the passes. This would force bad wires to explore more and restrict good wires to their current positions. The equation we devised would vary the slope of increase in CCR at every pass. Therefore, the increase is adjusted according to the NCR of each segment at each pass.
Optimization Goals:
We did the following items to improve the routability and efficiency.
- Linsker-Style Ripup/Reroute algorithm. Our implementation of the algorithm includes path history dependent penalty function and Cost scheduling. The cost is scheduled to drop suddenly after it reached a certain large value.
- Clever linked list. We used several kinds of linked list. For example, cell data structure of the grid can be linked from net data structure that has wire on the cell. Therefore, we can delete the wire from the net data structure just by traversing the list of cells from net structure without searching in the grid.
Implementation:
Data Structure:
The data structure in this project should allow easy access to different types of objects in difference part of the program. To keep track of all the data, we use the following objects:
- Cell
- Cell contains a single grid cell.
- To keep track of what nets pass through this net, we use a list of segment pointers.
- To keep track of the cost of this net when Linsker’s cost function is used, a cost variable is used.
- To keep track of if the cell is reached in wave front expanding, a reached variable is used.
- To enable backtracing once the target is found, a number representing direction to the previous cell is used. It can be North, South, East or West.
- To keep track of the cell type, a cell_type variable is used. The cell can be empty, has-wire, via, or pin.
- Gate
- Gate saves a list of net ids of nets that connect to the gate’s pins. A particular net can be accessed using the net id in netlist.
- Line
- Line is used to keep track of the exact path a segment of net is routed. It contains the starting coordinate and ending coordinate of a line. Coordinate contains the layer, x, and y information. Line also has pointers to other lines, so they can be linked as a list.
- Net
- Net keeps track of the pins it connects to, and the segments it has by using a pin array and a segment array. Arrays are used because a net has a fixed number of pins and segments. This would allow faster access to data.
- Pin
- A pin contains the position (x, y) and the net it is connected to.
- Segment
- A segment contains the starting and ending location of the net. However, it does not contain the exact path. The segment contains a list of lines, which then contains the exact routed path.
- A segment also contains a list of cells that it passes through. This allows easier calculation of cost of cells.
And we use the following objects to keep track of a group of same objects:
- Cellhook
- Cellhook is just a container class that contains cell. This is necessary for a list of cells.
- Listofcellhook
- This is just a list of linked cellhooks.
- Segmenthook
- Segmenthook is just a container class that contains segment. This is necessary for a list of segments.
- Listofsegmenthook
- This is just a list of linked segmenthooks.
- Netlist
- This contains an array of Nets read from the input file.
- Listoflines
- This
is just a list of linked lines.
As shown in the diagram below, this data structure is very flexible. Different types of data can be reached at almost any other data structures in the program.
Linsker’s Cost Function:
For the Linsker’s algorithm, the final version we decided to use is shown below:
New CCR of segment = Current CCR of segment + addition CCR( ) of segment
If new CCR > (4/5) x CONSTANT (=5000), then new CCR = new CCR / 2.
This way, when the CCR of a segment reaches the upper limit,
it is cut in half. This would create the saw tooth shape in Linsker’s algorithm.
Minimum spanning tree part:
We followed the algorithm in the class notes to implement the minimum spanning tree algorithm.
Pseudo code of out min span tree implementation:
- Create inTree list and notInTree list. Put one of the nodes to inTree list. Put other nodes to notInTree.
- Find a node, which is closest to the one of the node in inTree. Then put the node to inTree list.
- Remember the order of nodes that are put to inTree. Repeat step 2. Until all of the node are put into inTree list.
- Create spanning tree in the order of the nodes that are put into the inTree. When putting a new node to spanning tree, the edge start from the closest node to the new node.
Maze part:
We used conventional maze routing algorithm. For the
implementation of the wave front structure, we used Cost-Indexed array. There
are six starting points of the wire since their heights are 3 and they are
accessible from M1 and M2 layer. Therefore, we put all of these six cells to
the wave front as the initial expanding cells. Similarly, there are six target
cells. If the wave front reached one of the six target cells, it means the wire
is routed. Then we can backtrace the wire by using predecessor information in
cells to the source.
Ripup/Reroute part:
We followed the basic procedure of the Linsker’s algorithms. In addition, we did some modification for our implementation.
Pseudo code of our implementation of Ripup/Reroute algorithm:
1. Set per-unit-length length cost, CX, CY. We will not change this cost in the following iteration. We assume M1 and M3 are X-direction plane, M2 and M4 are Y-direction plane. The cost of via, VIA_COST, and the cost of bend, BEND_COST are also defined.
2. Conduct initial maze routing
3. Calculate NCR and CCR
4. Do for each iterative pass KPASS = 1 to kmax
a. Do for each net i (order of net in input file)
i. Erase the old path for net I
ii. Route a new path for net i such that this pass has the lowest possible value of the pass cost function.
PCP = CX*LX + CY*LY + VIA_COST + BEND_COST + Sum{CCR(j) * NCRi(j)}
b. Do for all nets j:
i. Calculate NCR(j) = the number of crossing involving the path for net j.
ii.
Define new crossing-cost CCR(j) such that the larger NCR(j)
is, the smaller CCR(j) is, and vice versa.
5.
Generate output file
Results:
Easy Cases:
For the simple cases, all benchmarks that ran without out-of-memory problem were routed 100 % with no violations except Primary1. For Primary 1, 99.6 % of wires were routed, and 74 violations happened. If the result produced by the checkers means that the violations were caused by the 4 (902 – 898) wires not routed. Then, this results shows that the routing algorithm is quite successful because the objective is to route as many wires as possible, and let a few wires have many violations. Therefore, it is easier to fix the routing by fixing these few very bad wires.
If the checker output does not mean the violations were caused by the 4 wires, the router is still quite good because the number of violations is not a lot compared to the total wirelength and the number of wires.
|
|
Toy 1 |
Toy 2 |
Industry 1 |
Industry 2 |
Primary 1 |
Primary 2 |
Fract |
Fract 2 |
|
Total wire length (layers 1-4) |
744 (219 / 336 / 2 / 187) |
1754 (922 / 518 / 52 / 262) |
Unable to complete (out of memory) |
Unable to complete (out of memory) |
173657 (87269 / 8988 / 4273 / 73125) |
Unable to complete (out of memory) |
14165 (7167 / 2609 / 235 / 4154) |
12668 (6095 / 2080 / 178 / 4315) |
Bends |
132 |
347 |
|
|
23178 |
|
2531 |
2251 |
Vias |
111 |
340 |
|
|
69795 |
|
7277 |
4024 |
# Routed / Out of |
21 / 21 |
42 / 42 |
|
|
898 / 902 |
|
147 / 147 |
125 / 142 |
Percentage |
100% |
100% |
|
|
99.6% |
|
100% |
88% |
# of Violations |
0 |
0 |
|
|
74 |
|
0 |
0 |
Hard Cases:
For the hard cases, toy1 and toy2 benchmarks are routed 100 % with no violations. In addition, primary1 has 99.3% of wires routed and 16 violations. This result is very good. The 16 violations is very small compared to the number of wires and the total wirelength. However, for Fract benchmark, 81.26% of wires were routed, and there are 14877 violations. This result seems bad; however, the large number of violations may be caused by a small number of vary bad wires, and should be fixable by rerouting these small number of wires.
|
|
Toy 1 |
Toy 2 |
Industry 1 |
Industry 2 |
Primary1 |
Primary 2 |
Fract |
|
Total wire length (layers 1-4) |
744 (219 / 336 / 2 / 187) |
1536 (851 / 370 / 52 / 263) |
Unable to complete (out of memory) |
Unable to complete (out of memory) |
181095 (57379 / 14512 / 41528 / 67676) |
Unable to complete (missing 1 benchmark file) |
13444 (6414 / 3211 / 305 / 3514) |
Bends |
132 |
359 |
|
|
37095 |
|
2633 |
Vias |
111 |
393 |
|
|
85760 |
|
7544 |
# Routed / Out of |
21 / 21 |
42 / 42 |
|
|
146 / 147 |
|
733 / 902 |
Percentage |
100% |
100% |
|
|
99.3% |
|
81.26% |
# of Violations |
0 |
0 |
|
|
16 |
|
14877 |
Post Mortem:
Due to the limitation of the time caused by multiple final projects due around the same time, we did not used Rubin’s Scheme in maze routing. We need to implement it for smart search. In addition, we need to do more tests with our cost function so it can perform at optimal performance. In addition, program can be sped up if more time is given to do a different implementation approach for some parts of the program.
Code:
(Note: benchmark results and checker results are available upon request)