关键词: 最小斯坦纳树, 避障, 布线, 超大规模集成电路

Abstract: In the routing phase of very large-scale integrated circuits (VLSI), the rapid and efficient creation of a rectilinear obstacle-avoiding Steiner  minimal tree (ROASMT) is crucial for successful routing. Therefore, this paper proposes a single-layer rectilinear obstacle-avoiding Steiner  minimal tree generation algorithm based on net partitioning, which combines partitioning and legalization techniques. By dividing the scanning point regions, an obstacle-avoiding spanning graph (OASG) is generated. Obstacle-avoiding spanning trees are then selected from the OASG and transformed into pin spanning trees (PSTs), thereby partitioning the original net into multiple sub-nets. Subsequently, the rectilinear Steiner minimal tree (RSMT) algorithm is applied to create rectilinear minimal Steiner trees for each obstacle-free sub-net, which are then legalized to obtain valid initial solutions. Additionally, this paper introduces a global optimization method based on “multi-segment edges” and a local optimization method based on “V-like structures”. Algorithm validation results show that the single-layer rectilinear  obstacle-avoiding Steiner minimal tree (SL-ROASMT) algorithm based on net partitioning reduces the total wire length by an average of approximately 3.6% compared to graph-based and edge-based algorithms, with all test cases completing routing within 1 second. 

Key words: Steiner minimal tree, obstacle-avoiding, routing, very large-scale integration (VLSI) circuit