In this paper, we formulate the timing-driven multiple-layer obstacle-avoiding rectilinear Steiner minimal tree (TML-OARSMT) problem and propose an algorithm to solve the problem. The objective is simultaneously to minimize the maximum source-to-terminal length and minimize the number of vias. The proposed algorithm contains the three steps, including the multiple-level timing-driven partitioning, the multiple-level routing tree construction with obstacles, and the timing-driven multiple-layer balanced tree construction. Compared with the traditional method, the partition-based method can significantly improve the maximum source-to-terminal length and the total wirelength by 11.3% and 10.9% respectively with the additional number of vias.
['Hsin-Hsiung Huang', 'Hui-Yu Huang', 'Yu-Cheng Lin', 'Tsai-Ming Hsieh']
Timing-driven obstacles-avoiding routing tree construction for a multiple-layer system