VLSI Routing - the most interesting puzzle of the last decade

One of the most important task in physical design of VLSI circuits is routing. The speed and power conservation of the chip depends upon how the different components are routed using the shortest possible wiring. The speed at which an optimal or semi-optimal route is derived, is crucial for the rate of chip production in scale. To solve this problem, we have to divulge into Graph theory.


Now lets start with Minimum Spanning Tree. In a connected, undirected, weighted graph with several nodes, a spanning tree is defined as subgraph that connects all the vertices together. A graph can have many spanning trees. One of those spanning tree becomes a minimum spanning tree, if the sum of weights of all edges in that spanning tree is the least compared to the other spanning trees. So in a simple VLSI layout in which we need to connect all nodes, you can very well assert that the minimum spanning tree is the best way to route the different nodes. Minimum spanning tree problem is easy to solve using any of these algorithms.

But in practise, the layout routing is not always that easy. The complication comes when the total number of nodes in the graph is V and there are N nodes, such that N is a subset of V. In such a situation, we have an option to use the nodes that are in V, but not in N, provided it yields a better solution. The minimum spanning tree among the N used nodes is not necessarily the most optimal solution, because using the nodes that are not in N, we could actually create shorter routes. So we have to go for a steiner tree. A Steiner tree is a tree that connects the N nodes in a graph using extra nodes, in an attempt to reduce the total Euclidean length. Solving a Steiner tree problem is not so simple because the Steiner Tree problem is a NP-complete problem. Under certain circumstances the problem can be solved in polynomial time, but in general heuristics-based algorithm has to be used. To get more details about Steiner Tree problem, please refer to this book. A typical VLSI layout will have V nodes in which only N needs to be connected, although you can use all the V nodes to ensure shortest routing. So Steiner Tree Problem is more similar to VLSI routing than the spanning tree problem.

There is another practical factor that we overlooked in the previous paragraph. In VLSI routing, we cannot simply take any arbitrary route to connect two nodes. In other words, the shortest route between two nodes is not necessarily the line connecting them. This is because once the placement is over, the routing is allowed only through the rectilinear grid in between the cells. So the problem to solve is not really Steiner Tree, but a rectilinear Steiner Tree. So in a VLSI layout, given a set of terminal, the rectilinear Steiner minimum tree interconnects all the terminals through some additional nodes.

But as the size of the chip reduces, as we move from micrometer scale design to nanometer scale design, new problems crop up. The VLSI routing in a nanometer design has to consider various obstacles like power lines, pre-routed nets, jumpers, etc. As a result, an obstacle avoiding rectilinear steiner minimal tree (OARSMT) has become an important problem in recent years. The first practical approach of OARSMT was present in the name of FORst approach in 2004. Since then there has been a lot of interesting heuristics and approximations to solve this problem. In another wonkish post, I would explain FORst and recent developments to optimize OARSMT solution in another wonkish post.