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.