An Efficient Obstacle-Avoiding Rectilinear Steiner Tree Construction Method Using PB-SAT

Rectilinear Steiner tree (RST) construction is an important part of recent VLSI physical design. This article presents an efficient satisfiability (SAT) based approach to construct an obstacle-avoiding Rectilinear Steiner tree for a given set of pins in the presence of a given set of rectilinear obstacles. Initially, a spanning tree is generated without considering the obstacles and the net is decomposed into 2-pin sub-nets. Then, the RST is constructed for each subnet considering obstacles. RST is generated by applying a Pseudo-Boolean (PB) SAT-based technique. The proposed technique has been verified on several benchmark circuits. The results indicate that the proposed technique is able to produce a shorter wire length than other state-of-the-art RST tools in many cases.