Report

Coupling-Aware Length-RatioMatching Routing for Capacitor Arrays in Analog Integrated Circuits Kuan-Hsien Ho, Hung-Chih Ou, Yao-Wen Chang and Hui-Fang Tsao Graduate Institute of Electronics Engineering, National Taiwan University, Taiwan DAC’13 Outline Introduction Problem Formulation Routing Model and Algorithm Overview Topology Overview Detail Routing Experimental Result 2 Introduction The parasitic resistors and capacitors of interconnects gradually dominate the performance, signal integrity, and reliability of circuit designs [1]. The parasitic effects of interconnects on a layout with multiple unit capacitors cannot be ignored because the effects might change the capacitance ratio. Capacitance-ratio mismatch in a switched-capacitor circuit could significantly degrade circuit performance. 3 Introduction Parasitic capacitance is highly correlated with wire length [13] if the length ratio of interconnects of each capacitor can match the desired capacitance ratio, the impact of parasitic capacitance can be minimized. 4 Introduction (A) Without length ratio matching. C1 : C2 : C3 : C4 : C5 = 2 : 6 : 7 : 7 : 8 (B) With length ratio matching but no coupling considerations. (C) With both length ratio5 matching and coupling considerations. Introduction 6 Problem Formulation For two capacitor nets ni and nj ( j > i), ideally the length ratio equals the desired capacitance ratio: where the function L(ni) and Lu(ni) denote the respective length and unit length of the capacitor net ni ( i.e., Lu(ni) = L(ni) / ki ). C = {C1, C2, ...,Cm } be the set of m capacitors, and ki be the number of unit capacitors in Ci ∈ C for 1 ≤ i ≤ m. Capacitance ratio C1 : C2 : ... : Cm = k1 : k2 : ... : km. A capacitor net ni of Ci ∈ C is an interconnect that connects all of the unit capacitors of Ci and the pad of Ci. 7 Problem Formulation Length-Ratio-Matching Routing Problem: Given a capacitor set and a capacitor placement[6], route all of the capacitor nets such that the length-ratio-matching cost is minimized under the 100% routability guarantee and no route or via intersects any unit capacitors (tracks) 8 Problem Formulation The length-ratio-matching cost function Φ(m) by the difference of unit lengths between each pair of capacitor nets as follows: 9 Routing Model and Algorithm Overview 10 Routing Model and Algorithm Overview Determines the topologies of all capacitor nets. Each multi-pin net is decomposed into a set of 2- pin nets based on its topology. Given a length ratio, a feasible length interval is first determined, and the minimum feasible length is set as the desired length for each capacitor. 11 Routing Model and Algorithm Overview terminal tiles space tiles Routing graph modeling Tile is modeled as a vertex and each 12 boundary between two adjacent tiles as an edge Spanning-Graph Construction and Congestion Estimation Construct a spanning graph [5] for each capacitor net, each spanning graph is an undirected connected graph on the vertex set of the corresponding capacitor net. propagated probability model is proposed, which propagates probabilities tile by tile for a high accuracy, and use the proposed model to estimate the congestion for each edge of the spanning graph. 13 Spanning-Graph Construction and Congestion Estimation propagated probability model 14 Weight Computation and Spanning-Tree Construction In this step, we assign weights to all the edges in each spanning graph and then construct a spanning tree on the graph. The edge weight we of each edge depends on (1) wirelength weight wlength (2) congestion weight wcong 15 Weight Computation and Spanning-Tree Construction Wirelength weight wlength is the Manhattan distance of the two edge pins. The congestion weight of an edge can be computed by dynamic programming as follows. wcong [cb, rb] is the minimum of the maximum congestions bV[cb,rb] is the estimated congestion on the boundary between t[cb, rb−1] and t[cb, rb] 16 among all possible monotonic paths from the source tile t[1, 1] to t[cb, rb] Weight Computation and Spanning-Tree Construction With the wirelength weight and congestion weight, we define we as follows: where Ntrack is the minimum number of tracks between two adjacent unit capacitors in the vertical or the horizontal direction. To avoid congested areas during the construction of a minimum spanning tree, the congestion map in the routing graph needs to be updated once an edge is selected. 17 Coupling-aware SteinerPoint Insertion 18 Coupling-aware SteinerPoint Insertion flexibility range of a Steiner point s the difference of the upper and lower bounds of a 3-pin net wirelength by inserting s moving box of s the bounding box of the three pins. 19 Coupling-aware SteinerPoint Insertion Traverse a minimum spanning tree in a preorder sequence. The visited vertex and its parent both become the children of the Steiner point, while the grandparent becomes the parent of the Steiner point. 20 Coupling-aware SteinerPoint Insertion shrinking cost Difference of the product of (1) the sum of the flexibility ranges and (2) the total area of the two moving boxes, before and after moving a Steiner point. 21 Desired Wirelength Determination Determine the desired wirelength di (li ≤ di ≤ ui) for each capacitor net ni to minimize Equation (1). Normalize the length interval [ li, ui ] of each capacitor net ni, to a unit length interval [ ˆli, ˆui ], where we divide the length interval by ki, ˆli = li/ki and ˆui = ui / ki. 22 Desired Wirelength Determination expanding wirelength ei as (di − li ) the length that should be provided by moving the Steiner points in their corresponding bounding boxes. Distribute ei of ni to each Steiner point of ni, where the necessary moving length Ms of each Steiner point s is set as ei × (Imax/(ui − li)), where Imax is the maximum wirelength increment of moving the Steiner point located at the median inside the corresponding bounding box. 23 Desired Wirelength Determination Find a candidate position for each Steiner point for the next stage, detailed routing. Considering a Steiner point s in the grid-based model, we can get a diamond whose radius is equal to Ms. In order to satisfy Properties 1 and 2, we select the grids which are (1) on the diamond, (2) in the corresponding bounding box, (3) not on the location of any unit capacitor, as the candidate grids of the Steiner point. Once the Steiner point s is embedded in any candidate grid, the total wirelength can be increased by Ms. 24 Routing Model and Algorithm Overview Detailed routing for wirelength minimization is performed for each 2-pin net to match the coupling-aware desired length. 25 DETAILED ROUTING Decompose each resulting tree into a set of 2-pin nets Simultaneously determine the final positions of Steiner points and minimize routing wirelength. Assign a Steiner point to a routable candidate grid with the least congestion and coupling according to the routed nets and the routing topologies determined in the first stage. Then route all the 2-pin nets by maze routing while minimizing the bend number and coupling noise. 26 EXPERIMENTAL RESULTS The test cases used in this experiments were modified from 27 the resulting capacitor placements of the work [6]. EXPERIMENTAL RESULTS Total cost Total differences of unit lengths between each pair of capacitor nets, as defined in Eq. (1). Avg. cost Dividing the total cost by the number of different pairs of capacitor nets. The PCM method replaces our propagated probability congestion estimation model by the probabilistic congestion 28 model which is widely used in previous works [7, 14]. Conclusion An effective length-ratio-matching routing algorithm is proposed for the addressed problem. This work is the first work that addresses the issue of wirelength ratios in capacitor arrays for analog circuit design. The experimental results have shown that this algorithm outperforms a reasonable heuristic by large margins. 29