An efficient hierarchical timing-driven Steiner tree algorithm for global routing

✍ Scribed by Jingyu Xu; Xianlong Hong; Tong Jing; Yici Cai; Jun Gu

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 425 KB
• Volume: 35
• Category: Article
• ISSN: 0167-9260
• DOI: 10.1016/s0167-9260(03)00029-4

✦ Synopsis

In this paper, we propose a hierarchical timing-driven Steiner tree algorithm for global routing which considers the minimization of timing delay during the tree construction as the goal. The algorithm uses heuristic approach to decompose the problem of minimum delay Steiner tree into hierarchy and construct the sub-trees, respectively, based on dynamic programming technique. Taking the net topology into consideration, we build the final routing tree by reconnecting the sub-trees at each level recursively and then improve the connection with the objective of minimizing the delay from source to sink pins on the critical path. Meanwhile, some efficient strategies have been proposed to speed up the solving process. Experimental results are given to demonstrate the efficiency of our algorithm.