In this paper, we present an algorithm called FOARS for obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) construction. FOARS applies a top-down approach which first partitions the set of pins into several subsets uncluttered by obstacles. Then an obstacle-avoiding Steiner tree is generated for each subset by an obstacle aware version of the rectilinear Steiner minimal tree algorithm FLUTE. Finally, the trees are merged and refined to form the OARSMT. To guide the partitioning of pins, we propose a novel algorithm to construct a linear-sized obstacle-avoiding spanning graph which guarantees to contain a rectilinear minimum spanning tree if there is no obstacle. Experimental results show that FOARS is among the best algorithms in terms of both wirelength and runtime for testcases both with and without obstacles.

Obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) construction is becoming one of the most sought after problems in modern design flow. In this paper we present FOARS, an algorithm to route a multi-terminal net in the presence of obstacles. FOARS is a top down approach which includes partitioning the initial solution into subproblems and using obstacle aware version of Fast Lookup Table based Wire-length Estimation (OA-FLUTE) at a lower level to generate an OAST followed by recombining them with some backend refinement. To construct an initial connectivity graph FOARS uses a novel obstacle-avoiding spanning graph (OASG) algorithm which is a generalization of Zhou's spanning graph algorithm without obstacle [1]. FOARS has a run time complexity of O(n log n). Our experimental results indicate that it outperforms Lin et al. [2] by 2.3% in wirelength. FOARS also has 20% faster run time as compared with Long et al. [3], which is the fastest solution till date.