1zElxS8gKyPAZ8Gfem9OtW-l_gTBj6KdD7wcE85xYDU7Y8o036Vsa8mFs2dfJryuZ0gUEZKQ97Vg-J71A4ngEA

An Efficient Hierarchical Timing-Driven Steiner Tree Algorithm for Global Routing




2 views

Unformatted text preview:

An Efficient Hierarchical Timing-Driven Steiner Tree Algorithm for Global Routing* Jingyu Xu, Xianlong Hong, Tong Jing, Yici Cai Dept. of Computer Science & Technology, Tsinghua University, Beijing, P. R. China, 100084 Email: xujy, hongxl, jingt, [email protected] Jun Gu Dept. of Computer Science, Hong Kong University of Science & Technology, Hong Kong, China Email: [email protected] Abstract 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 to 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 the algorithm. 1. Introduction With progress in VLSI deep-submicron (DSM) technology, interconnection delay has become increasingly significant in determining circuit speed [1, 2]. The wire capacitance and resistance can no longer be ignored during timing delay calculation since they are comparable to gate capacitance and output-driver resistance [3]. At the global routing stage, which determines how signal nets will finally be connected, it is necessary to estimate the wire delays in order to accurately maximize the overall chip performance. The Steiner tree algorithm is the essential part of a global routing algorithm. It has been an active field of research. To deal with the interconnection delay, many methods have been proposed, such as wire sizing [4-6], buffer inserting [7-9]. In [10], an interconnection delay calculation technique for custom chip design is presented. However, most existing Steiner tree algorithms of either wire-mode global routers or timing-driven global routers *This work was supported in part by the National Grand Fundamental Research 973 Program of China under Grant No. G-1998030411 take the minimization of total wire length as the objective. Only limited progress has been reported on timing-driven Steiner tree constructing. [11] proposed a bounded radius Steiner tree global routing algorithm with a wiring cost factor ε. For a small ε the algorithm may result in a very large net wire length, which may increase the timing delay for all sink pins of the net. Based on a simplified Elmore timing model, an iterative Dreyfus-Wagner based (IDW) [12, 13, 15] and a constructive force directed (CFD) Steiner tree algorithm [12, 14, 15] were presented. By improving the equations in Dreyfus-Wagner (DW) algorithm and introducing the timing optimization during the routing process, IDW constructs Steiner trees with high performance. The major weakness of IDW is that it becomes impractical when solving Steiner tree with more vertices (more than 7 vertices) due to the greatly increased run time. CFD runs much faster than IDW does, but the timing performance of the ...





Loading Unlocking...

Login

Join to view An Efficient Hierarchical Timing-Driven Steiner Tree Algorithm for Global Routing and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?

Sign Up

Join to view An Efficient Hierarchical Timing-Driven Steiner Tree Algorithm for Global Routing and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?