A High Efficient and Scalable Obstacle-Avoiding VLSI Global Routing Flow

Routing is a crucial step in the VLSI design flow. With advancements in manufacturing technology, more constraints have emerged in design rules, particularly regarding obstacles during routing, leading to increased routing complexity. Unfortunately, many global routers struggle to generate efficient obstacle-free solutions due to the lack of scalable obstacle-avoiding tree generation methods and the capability to handle modern designs with complex obstacles and nets. In this work, we propose an efficient obstacle-aware global routing flow for VLSI designs with obstacles. The flow includes a rule-based obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) algorithm during the tree generation phase. This algorithm is both scalable and fast, providing tree topologies avoiding obstacles in the early stage globally. With its guidance, in the later stages, the OARSMT-guided and obstacle-aware sparse maze routing are proposed to further minimize obstacle violations and reduce overflow costs. Compared to previously advanced methods on the benchmark with obstacles, our approach successfully eliminates obstacle violations and reduces wirelength and overflow cost, while sacrificing only a limited number of via counts and runtime overhead.