A Fast and Stable Algorithm for Obstacle-Avoiding Rectilinear Steiner Minimal Tree Construction

In routing, finding a rectilinear Steiner minimal tree (RSMT) is a fundamental problem. Today´s design often contains rectilinear obstacles, like macro cells, IP blocks, and pre-routed nets. Therefore obstacle-avoiding RSMT (OARSMT) construction becomes a very practical problem. In this paper we present a fast and stable algorithm for this problem. We use a partitioning based method and an ant colony optimization based method to construct obstacle-avoiding Steiner minimal tree (OASMT). Besides, two heuristics are proposed to do the rectilinearization and refinement to further improve wirelength. The experimental results show our algorithm achieves the best wirelength results in most of the test cases and the runtime is very small even for the larger cases each of which has both the number of terminals and the number of obstacles more than 100.