Unit 8: Layout Compaction

Course contents
Design rules
Symbolic layout
Constraint-graph compaction
Readings: Chapter 6

Unit 8 1
NTUEE / ntro. EDA

Design Rules
Design rules: Patterns and design
rules are often
restrictions on the mask
expressed in rules.
patterns to increase the
probability of successful
Most common design
rules:
fabrication. minimum-width rules (valid
for a mask pattern of a
specific layer): (a).
minimum-separation rules
(between mask patterns of
the same layer or different
layers): (b), (c).
minimum-overlap rules
(mask patterns in different
layers): (e).

Unit 8 2
NTUEE / ntro. EDA

1
 CMOS Inverter Layout Example

p/n diffusion
polysilicon
contact cut
metal
Symbolic layout
Geometric layout

Unit 8 3
NTUEE / ntro. EDA

Symbolic Layout
Geometric (mask) layout: coordinates of the layout
patterns (rectangles) are absolute (or in multiples of ).
Symbolic (topological) layout: only relations between
layout elements (below, left to, etc) are known.
Single symbols are used to represent elements located in
several layers, e.g. transistors, contact cuts.
The length, width or layer of a wire or another layout element
might be left unspecified.
Mask layers not directly related to the functionality of the circuit
do not need to be specified, e.g. n-well, p-well.
The symbolic layout can work with a technology file that
contains all design rule information for the target
technology to produce the geometric layout.

Unit 8 4
NTUEE / ntro. EDA

2
 Compaction and Its Applications
A compaction program or compactor generates layout
at the mask level. It attempts to make the layout as
dense as possible.
Applications of compaction:
Area minimization: remove redundant space in layout at
the mask level.
Layout compilation: generate mask-level layout from
symbolic layout.
Redesign: automatically remove design-rule violations.
Rescaling: convert mask-level layout from one
technology to another.

Unit 8 5
NTUEE / ntro. EDA

Aspects of Compaction
Dimension:
1-dimensional (1D) compaction: layout elements

only are moved or shrunk in one dimension (x or y

direction).
Is often performed first in the x-dimension and

then in the y-dimension (or vice versa).

2-dimensional (2D) compaction: layout elements are

moved and shrunk simultaneously in two dimensions.

Complexity:
1D compaction can be done in polynomial time.

2D compaction is NP-hard.

Unit 8 6
NTUEE / ntro. EDA

3
 1D Compaction: X Followed By Y
Each square is 2 * 2 , minimum separation is 1 .
Initially, the layout is 11 * 11 .
After compacting along the x direction, then the y
direction, we have the layout size of 8 * 11 .

Unit 8 7
NTUEE / ntro. EDA

1D Compaction: Y Followed By X
Each square is 2 * 2 , minimum separation is 1 .
Initially, the layout is 11 * 11 .
After compacting along the y direction, then the x
direction, we have the layout size of 11 * 8 .

Unit 8 8
NTUEE / ntro. EDA

4
 2D Compaction
Each square is 2 * 2 , minimum separation is 1 .
Initially, the layout is 11 * 11 .
After 2D compaction, the layout size is only 8 * 8 .

Since 2D compaction is NP-complete, most compactors

are based on repeated 1D compaction.

Unit 8 9
NTUEE / ntro. EDA

Inequalities for Distance Constraints

Minimum-distance For example, if the
design rules can be minimum width is a and
expressed as inequalities. the minimum separation
xj xi dij. is b, then
x2 x1 a
x3 x2 b
x3 x6 b

Unit 8 10
NTUEE / ntro. EDA

5
 Constraint Graph
The inequalities can be used to construct a constraint
graph G(V, E):
There is a vertex vi for each variable xi.
For each inequality xj xi dij there is an edge (vi, vj) with weight dij .
There is an extra source vertex, v0; it is located at x = 0; all other
vertices are at its right.
If all the inequalities express minimum-distance constraints,
the graph is acyclic (DAG).
The longest path in a constraint graph determines the
layout dimension.

constraint graph
Unit 8 11
NTUEE / ntro. EDA

Maximum-Distance Constraints
Sometimes the distance of layout elements is bounded
by a maximum, e.g., when the user wants a maximum
wire width, maintains a wire connecting to a via, etc.
A maximum distance constraint gives an inequality of the form:
xj xi cij or xi xj -cij
Consequence for the constraint graph: backward edge
(vj, vi) with weight dji = -cij; the graph is not acyclic anymore.
The longest path in a constraint graph determines the
layout dimension.

Unit 8 12
NTUEE / ntro. EDA

6
 Longest-Path Algorithm for DAGs

pi: in-degree of vi.

xi: longest-path
length from v0 to vi.

Unit 8 13
NTUEE / ntro. EDA

DAG Longest-Path Example

Runs in a breadth-first search
manner.
pi: in-degree of vi.
xi: longest-path length from v0
to vi.
Time complexity: O(V+E).

Unit 8 14
NTUEE / ntro. EDA

7
 Longest-Paths In Cyclic Graphs
Constraint-graph compaction with maximum-distance
constraints requires solving the longest-path problem in
cyclic graphs.
Two cases are distinguished:
There are positive cycles: No feasible solution for longest
paths. We shall detect the cycles.
All cycles are negative: Polynomial-time algorithms exist.

Unit 8 15
NTUEE / ntro. EDA

The Liao-Wong Longest-Path Algorithm

Split the edge set E of the constraint graph into two
subsets:
Forward edges Ef: related to minimum-distance constraints.
Backward edges Eb: related to maximum-distance
constraints.
The graph G(V, Ef) is acyclic; the longest distance for
each vertex can be computed with the procedure
longest-path.
Repeat :
Update longest distances by processing the edges from Eb.
Call longest-path for G(V, Ef).
Worst-case time complexity: O(Eb r Ef).

Unit 8 16
NTUEE / ntro. EDA

8
 Pseudo Code: The Liao-Wong Algorithm

Unit 8 17
NTUEE / ntro. EDA

Example for the Liao-Wong Algorithm

Two edge sets: forward edges Ef and
backward edges Eb
xi: longest-path length from v0 to vi.
Call longest-path for G(V, Ef).
Update longest distances by
processing the edges from Eb.
Time complexity: O(Eb r Ef).

x1 < x2 - 3

x3 < x4 - 1

x5 = x4 - 4
Unit 8 18
NTUEE / ntro. EDA

9
 The Bellman-Ford Algorithm for Longest Paths

/* n: upper bound of vertex ID */

/* n+1: total # of vertices */
/* current wave front */
/* next wave front */

Unit 8 19
NTUEE / ntro. EDA

Example of Bellman-Ford for Longest Paths

Repeated wave front propagation.
S1: the current wave front.
xi: longest-path length from v0 to vi.
After k iterations, it computes the
longest-path values for paths going
through k-1 intermediate vertices.
Time complexity: O(VE).

Unit 8 20
NTUEE / ntro. EDA

10
 Longest and Shortest Paths
Longest paths become shortest paths and vice versa
when edge weights are multiplied by 1.
Situation in DAGs: both the longest and shortest path
problems can be solved in linear time.
Situation in cyclic directed graphs:
All weights are positive: shortest-path problem in P
(Dijkstra), no feasible solution for the longest-path
problem.
All weights are negative: longest-path problem in P
(Dijkstra), no feasible solution for the shortest-path
problem.
No positive cycles: longest-path problem is in P.
No negative cycles: shortest-path problem is in P.

Unit 8 21
NTUEE / ntro. EDA

Remarks on Constraint-Graph Compaction

Noncritical layout elements: Every element outside the
critical paths has freedom on its best position => may
use this freedom to optimize some cost function.
Automatic jog insertion: The quality of the layout can
further be improved by automatic jog insertion.

Hierarchy: A method to reduce complexity is

hierarchical compaction, e.g., consider cells only.

Unit 8 22
NTUEE / ntro. EDA

11
 Constraint Generation
The set of constraints should be irredundant and generated
efficiently.
An edge (vi, vj) is redundant if edges (vi, vk) and (vk, vj) exist
and w((vi, vj)) w((vi, vk)) + w((vk, vj)).
The minimum-distance constraints for (A, B) and (B, C) make
that for (A, C) redundant.

Doenhardt and Lengauer have proposed a method for

irredundant constraint generation with complexity O(n log n).

Unit 8 23
NTUEE / ntro. EDA

Appendix: Dijkstra's Shortest-Path Algorithm

Dijkstra(G, w, s)
1. Initialize-Single-Source(G, s);
2. S ;
3. Q V[G];
4. while Q
5. u Extract-Minimum(Q);
6. S S {u};
7. for each vertex v Adj[u]
8. Relax(u, v, w);

Combines a greedy and a dynamic-programming schemes.

Works only when all edge weights are nonnegative.
Executes essentially the same as Prim's algorithm.
Naive analysis: O(V2) time by using adjacency lists.
Can be done in O(E lg V) time (Q: a binary heap) or O(E + V lg V)
time (Q: a Fibonacci heap)
Unit 8 24
NTUEE / ntro. EDA

12
 Relaxation
Initialize-Single-Source(G, s)
1. for each vertex v V[G] Relax(u, v, w)
2. d[v] ; 1. if d[v] > d[u]+w(u, v)
/* upper bound on the weight of 2. d[v] d[u]+w(u, v);
a shortest path from s to v */ 3. [v] u;
3. [v] NIL; /* predecessor of v */
4. d[s] 0;
d[v] d[u] + w(u, v) after calling Relax(u, v, w).
d[v] (s, v) during the relaxation steps; once d[v] achieves its
lower bound (s, v), it never changes. ((s, v); shortest path
distance from the source s to v.)
Let be a shortest path. If d[u] = (s, u) prior to the
call Relax(u, v, w), then d[v] = (s, v) after the call.

Unit 8 25
NTUEE / ntro. EDA

Example: Dijkstra's Shortest-Path Algorithm

d[u]=10
[u]=s d[u]=8 d[v]=14
[u]=x [v]=x
d[s]=0
[s]=NIL

d[y]=7
d[x]=5 [y]=x
[x]=s

Unit 8 26
NTUEE / ntro. EDA

13
 Shortest Path for Directed Acyclic Graphs (DAGs)
DAG-Shortest-Paths(G, w, s)
1. topologically sort the vertices of G;
2. Initialize-Single-Source(G, s);
3. for each vertex u taken in topologically sorted order
4. for each vertex v Adj[u]
5. Relax(u, v, w);
Time complexity: O(V+E) (adjacency-list representation).

Unit 8 27
NTUEE / ntro. EDA

Representations of Graphs: Adjacency List

Adjacency list: An array Adj of |V | lists, one for each
vertex in V. For each u V, Adj[u] pointers to all the
vertices adjacent to u.
Advantage: O(V+E) storage, good for sparse graph.
Drawback: Need to traverse list to find an edge.

Unit 8 28
NTUEE / ntro. EDA

14
 Topological Sort
A topological sort of a directed acyclic graph (DAG) G = (V, E) is a
linear ordering of V s.t. (u, v) E u appears before v.
Topological-Sort(G)
1. call DFS(G) to compute finishing times f[v] for each vertex v
2. as each vertex is finished, insert it onto the front of a linked list
3. return the linked list of vertices
Time complexity: O(V+E) (adjacency list).

Unit 8 29
NTUEE / ntro. EDA

Depth-First Search (DFS)

DFS(G)
1. for each vertex u V[G] color[u]: white (undiscovered)
2. color[u] WHITE; gray (discovered) black
3. [u] NIL; (explored: out edges are all
4. time 0;
5. for each vertex u V[G] discovered)
6. if color[u] = WHITE
7. DFS-Visit(u). d[u]: discovery time (gray);
f[u]: finishing time (black);
DFS-Visit(u) [u]: predecessor.
1. color[u] GRAY;
/* white vertex u has just been Time complexity: O(V+E)
discovered. */
2. d[u] time time + 1; (adjacency list).
3. for each vertex v Adj[u]
/* Explore edge (u,v). */
4. if color[v] = WHITE
5. [v] u;
6. DFS-Visit(v);
7. color[u] BLACK;
/* Blacken u; it is finished. */
8. f[u] time time +1.
Unit 8 30
NTUEE / ntro. EDA

15
 DFS Example

color[u]: white gray black.

Depth-first forest: G = (V, E), E = {([v], v) E | v V, [v]
Unit 8
NIL}. 31
NTUEE / ntro. EDA

The Bellman-Ford Algorithm for Shortest Paths

Bellman-Ford(G,w, s)
1. Initialize-Single-Source(G, s);
2. for i 1 to |V[G]|-1
3. for each edge (u, v) E[G]
4. Relax(u, v, w);
5. for each edge (u, v) E[G]
6. if d[v] > d[u] + w(u, v)
7. return FALSE;
8. return TRUE

Solves the case where edge weights can be

negative.
Returns FALSE if there exists a negative-weight
cycle reachable from the source; TRUE otherwise.
Time complexity: O(VE).
Unit 8 32
NTUEE / ntro. EDA

16
 Example for Bellman-Ford for Shortest Paths

Unit 8 33
NTUEE / ntro. EDA

17