View Full Document

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



View the full content.
View Full Document
View Full Document

5 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 caiyc tiger cs tsinghua edu cn Jun Gu Dept of Computer Science Hong Kong University of Science Technology Hong Kong China Email gu cs ust hk 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



Access the best Study Guides, Lecture Notes and Practice Exams

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?