A Quick Tour of the FORst

In an earlier post about VLSI routing, I promised a little wonkish post on Obstacle Avoiding Rectilinear Steiner Minimum Tree (OARSMT). This may be it, but still not so wonkish. In this post, I would try to explain FORst - one of the earlier methods (2004) to solve OARSMT problem.

OARSMT is a NP-Complete problem and so it cannot be solved in polynomial time. So VLSI designers use different heuristics to derive the solution for OARSMT or simply RSMT. The simplest of all the solutions is to derive a rectilinear minimum spanning tree and taking that as the approximation for RSMT. Theoretically, it is nearly a 50% approximation, i.e. wire length would be up to 50% more if we assume rectilinear minimum spanning tree to be RSMT, although in practice, it would be lot better.

In this paper, the authors have derived a 3-step heuristic algorithm as an optimal solution for OARSMT. The first step is to split the entire graph into several subgraphs depending on the location of the terminals. For this we have to construct a full steiner tree. Full steiner tree is the one in which all nodes in the graph are leaves. Hwang's theorem is used to construct such a tree. Once done, we just need to wipe out all edges that pass over one or more obstacles. Now the nodes in the subtrees that we get, constitutes the subgraph.

The second step is RSMT construction. It is apparent that the subgraphs that we constructed are free of obstacles. We can use any heuristic to construct the RSMTs. The original paper uses a combination of ant colony optimization (ACO) and greedy approximation methods to construct the RSMTs. To be more specific, ACO is used for smaller terminals for accuracy and for connecting them together in a larger terminal greedy method is used as it produces faster result.

The third step is to combine all the RSMTs. The nearest nodes of every RSMT is joined together with all adjacent subgraphs. The paper gives experimental evidence that even a large graph with several obstacles can be routed in a small time. A typical nanometer integrated circuit fabric would have thousands of nodes and hundreds of obstacles like power lines, IPs, etc. All those cases can be treated as large scale OARSMT problem and FORst is the right candidate if you are looking for a solution.

FORst is now nearly five years old and there have been several improvements and several improved heuristics resulting in more and more efficient implementations. However we just could not miss our FORst. It's like the 8088 processor, however outdated you would always learn before proceeding to the architecture of P4.

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.