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

This preview shows page 1-2 out of 6 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

MainASP02Front MatterTable of ContentsSession IndexAuthor IndexAn 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 routing tree is decreased. [16] presented a timing-driven Steiner tree algorithm based on Sakurai timing model. Experimental results in [16] show that using Sakurai timing model is more accurate than using Elmore timing model in Steiner tree constructing. However, the run time of the algorithm [16] is still longer. In this paper, we present a hierarchical timing-driven Steiner tree algorithm based on Sakurai timing model. The algorithm significantly speeds up the process of routing tree constructing with high timing performance. The remainder of this paper is organized as follows. In Section 2, the Sakurai-delay-based timing model for accurately calculating the delay is discussed, the global routing problem is formulated for symbolic analysis, and the Dreyfus-Wagner (DW) algorithm is introduced. The timing-driven Steiner tree algorithm is given in detail in Section 3. Section 4 presents the efficient strategies. Section 5 shows our experimental results. Section 6 is an overall conclusion. 2. Preliminaries In this section, we will discuss timing models and give the problem formulation. Then, the Dreyfus-Wagner algorithm will be introduced.2.1. Timing model The Sakurai-delay-based timing model [17], used in this paper instead of Elmore-delay-based timing model [18, 19] and optimized Elmore-delay-based timing model [20], is modeled as a voltage source with the on-resistance of the transistor , distributed RC lines of resistance , capacitance , and loading capacitance . It accords with actual value. The delay is given by the following expression: sRecerzCDZT T (1) zeeezesDZCrcrCcRβαβ+++= )(Where α equals 1.02 and β equals 2.21, which yields 90% of the signal’s final delay time. In the case of multi-terminal net, the delay is formulated as T ssDCRsβ=)( T wvwvwDDCLrLcrvTwˆˆˆ)()(2βα++=Where node v is the predecessor node of node w, is the wire length from v to w, is the total capacitance of the rest sink pins and wire segments of the net. vwLwC2.2. Problem formulation With the progress in multi-layer routing technology, routing area expands to the whole plane instead of many channels. Let us assume that the chip has been divided into a rectangular array of cells called global routing cells (GRCs). Global routing graph (GRG) is the dual graph of the graph, which is composed of the gridlines and crossings. colrowNN × Thus, a net can be specified as a set of nodes in GRG. The problem of routing a net in GRG can be described as a Steiner tree problem of specified nodes in the GRG. 2.3. Dreyfus-Wagner algorithm As an application of dynamic programming technique, the Dreyfus-Wagner algorithm [21] searches for all the possible Steiner trees connecting T (representing the set of pins of a signal net) to minimize the total wire length. We use to denote the Steiner tree of , where and , while the definition of is similar, with one extra constraint that . Let be the shortest path from v to w in G. The following two recursions are used: }){( vKSvUTK ⊆}){vK U2)( ≥v}{vK UKVv −∈),( wvp(Pvdegree}){ '(}){ '(min{}){( vKKSvKSvKPvvvUUU


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

Download An Efficient Hierarchical Timing-Driven Steiner Tree Algorithm for Global Routing
Our administrator received your request to download this document. We will send you the file to your email shortly.
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 2 2 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?