Layout Compaction - ELEC 5402

Layout Compaction ELEC 5402 Pavan Gunupudi Dept. of Electronics, Carleton University January 10, 2012 1 / 27

Introduction General goal is to minimize layout area Layout is a collection of polygons Generally we have rectilinear polygons Some technologies allow polygons to have 45-degree segments a) Rectilinear Polygon b) 45 degree segments 2 / 27

Design Rules a) b) c) a) Minimum width b) Minimum separation c) Minimum overlap Can only place rectangles on grid points Constraints imposed through design rules Constraints for polygons on same layer and different layers Expressed as minimum/maximum distance rules 3 / 27

Applications of Layout Compaction Removing redundant area from geometric layout Adapting geometric layout to new technologies If technology changes, design rules change geometric layout has to be converted to symbolic layout and then reconverted to geometric layout with new design rules Correcting small design rule errors Converting symbolic layout to geometric layout 4 / 27

Problem Formulation Layout is a collection of rectangles Two groups of rectangles: rigid and stretchable Rigid: e.g. Transistors, contact cuts etc. Stretchable: e.g. Wires (not width but length) Layout compaction is a 2-D problem 2-D layout compaction is NP-Complete (heuristics needed) 1-D layout compaction is in P Repeated 1-D layout compaction in each dimension is a valuable heuristic for 2-D layout compaction 5 / 27

2-D, 1-D Layout Compaction C B A D C B A D I F E H G I H F E (a) G (b) C B D A C A B I H D H I E F (c) G E F G (d) 6 / 27

2-D, 1-D Layout Compaction (a) (b) C B D A C A B I H D H I E F G E F G (d) (c) C A C B A H D I H G E F G B D I E F (e) (f) 7 / 27

Graph Formulation x1 x2 x3 x5 x4 x6 Rigid rectangle - one variable Stretchable rectangle - two variables Minimum distance rule: xj xi dij x2 x1 a; x3 x2 b; x6 x5 a; x3 x6 b x4 x3 a 8 / 27

Constraint Graph 0 v1 v2 a v0 a 0 v5 b b v6 v3 v4 a Vertices of the graph vi xi (source vertex v0 ) Edges (branches) (vi , vj ) with weight w((vi , vj )) dij for each inequality xj xi dij The graph can be denoted as G(V, E); V is the set of vertices and E is the set of edges 9 / 27

Constraint Graph Solution 0 v1 v2 a v0 a 0 v5 b b v6 v3 v4 a Length of the longest path from v0 to vi gives the minimal x-coordinate xi associated with the vertex vi By taking the longest path to vi we make sure that all inequalities in which xi participates are satisfied 10 / 27

Maximum-Distance Constraints xC C d W Ťx C * x W Ť v d xW Written as xC xW d and xW xC d Leads to cycles; solution still longest path 11 / 27

Example 1 d2 d2 d1 x1 x2 x3 x4 d2 x5 x6 12 / 27

Example 1 x3 x2 d1 2 x2 x1 d2 2 x4 x3 d2 2 x6 x5 d2 2 v2 v1 0 2 v0 v3 2 v4 2 0 v5 2 v6 13 / 27

Example 2 d2 d2 d1 C1 x1 x2 C2 x4 x3 xw xc d2 x5 x6 14 / 27

Example 2 x3 x2 d1 1; x6 x5 d2 2; x4 xc C1 0.5; v1 x2 x1 d2 2 x4 x3 d2 2 xw xc C2 0.25; xc x3 C1 0.5 xc x5 C1 0.5; x6 xc C1 0.5 v2 2 1 v3 2 0.5 0.5 -0.25 0 vc 0.5 v0 v4 vw 0.5 -0.25 0 v5 2 v6 15 / 27

Longest-Path Algorithm for DAGs Applicable only to directed acyclic graphs (DAGs) Set Q contains a list of all vertices vi for which the longest distance from v0 is known. Initially only v0 Q; Gradually other vertices will be added. Once the vertex is “processed” it is removed from Q A variable pi is associated with each vertex vi to keep track of the vertices incident on vi that still have to be processed 16 / 27

Example v3 v2 1 1 5 v4 2 v0 1 4 v1 2 v5 17 / 27

LPA - Example Q φ {v0 } {v1 } {v2 , v5 } {v3 , v5 } {v5 } {v4 } p1 1 0 0 0 0 0 0 p2 2 1 0 0 0 0 0 p3 1 1 1 0 0 0 0 p4 2 2 2 1 1 0 0 p5 1 1 0 0 0 0 0 x1 0 1 1 1 1 1 1 x2 0 5 5 5 5 5 5 x3 0 0 0 6 6 6 6 x4 0 0 0 6 6 7 7 x5 0 0 3 3 3 3 3 18 / 27

LPA - Pseudocode longest-path(G) { for (i 1; i n; i i 1) pi “in-degree of vi ”; Q {v0 }; while (Q 6 ) { vi “any element from Q”; Q Q \{vi }; for each v j “such that” (vi , v j ) E { x j max(x j , xi di j ); p j p j 1; if (p j 0) Q Q {v j }; } } } main () { for (i 0; i n; i i 1) xi 0; longest-path(G); } 19 / 27

Directed graphs with cycles The previous algorithm only works for acyclic graphs Two cases of cyclic graphs Negative cycles: Sum of edges in a cycle is negative Positive cycles: Sum of edges in a cycle is positive Finding longest path for positive cycles is NP-hard But positive cycle in a layout means conflicting constraints Such a layout is over-constrained Detecting positive cycles is enough Two algorithms to calculate longest path for negative cyclic graphs Liao-Wong algorithm Bellman-Form algorithm 20 / 27

Example v3 v2 1 –1 1 5 2 –3 v0 v4 1 4 v1 –4 2 v5 21 / 27

Liao-Wong Algorithm All edges are partitioned into forward edges Ef and backward edges Eb Ef - Minimum inequality constraints Eb - Maximum inequality constraints Idea is to start with graph with only Ef edges Use the DAG longest path algorithm on it Add one edge from Eb , call the DAG longest path algorithm again Iterate until all the edges in Eb are added 22 / 27

Solution - LW Step Initialize Forward 1 Backward 1 Forward 2 Backward 2 Forward 3 Backward 3 x1 1 2 2 2 2 2 x2 5 5 5 5 5 5 x3 6 6 6 7 7 7 x4 7 7 8 8 8 8 x5 3 3 4 4 4 4 23 / 27

LW - Pseudocode count 0; for (i 1; i n; i i 1) xi ; x0 0; do { flag 0; longest-path(G f ); for each (vi , v j ) Eb if (x j xi di j ) { x j x i di j ; flag 1; } count count 1; if (count Eb && flag) error(“positive cycle”) } while (flag); 24 / 27

Bellman-Ford Algorithm This does not discriminate between forward and backward edges This algorithm goes through several iterations until it converges to the longest paths First we start with a set S1 containing the source vertex Update distances to all the vertices that edges of this vertex go to: add these new vertices to S1 and remove the source vertex Repeat this process with the vertices present in set S1 Continue until convergence is attained If convergence does not occur in n iterations (n is the number of vertices in the graph then it indicates the presence of positive cycles 25 / 27

Solution - BF S1 “not initialized” {v0 } {v1 , v2 } {v1 , v3 , v4 , v5 } {v4 , v5 } {v4 } {v3 } x1 1 2 2 2 2 2 x2 5 5 5 5 5 5 x3 6 6 6 7 7 x4 6 7 8 8 8 x5 3 4 4 4 4 26 / 27

BF - Pseudocode for (i 1; i n; i i 1) xi ; x0 0; count 0; S1 {v0 }; S2 ; while (count n && S1 6 ) { for each vi S1 for each v j “such that” (vi , v j ) E if (x j xi di j ) { x j x i di j ; S2 S2 {v j } } S1 S2 ; S2 ; count count 1; } if (count n) error(“positive cycle”); 27 / 27

Layout is a collection of rectangles Two groups of rectangles: rigid and stretchable Rigid: e.g. Transistors, contact cuts etc. Stretchable: e.g. Wires (not width but length) Layout compaction is a 2-D problem 2-D layout compaction is NP-Complete (heuristics needed) 1-D layout compaction is in P Repeated 1-D layout compaction in each dimension is a