CAD of VLSI Systems

I Introduction d i
Virendra Singh g Indian Institute of Science g Bangalore
virendra@computer.org

E0-285: CAD of VLSI Systems

Acknowledgement
z z

z z z z z

Prof. S.K. Nandy, SERC Prof. Kewal K. Saluja, Univ. of WisconsinMadison, USA Prof. Hideo Fujiwara, NAIST, Japan Prof. Vishwani Agrawal, Auburn University, USA Prof. Samiha Mourad, Santa Clara Univ., USA Prof. Erik Larsson, Linkoping Univ., Sweden Mr. Raj Singh, CEERI, PIlani
Aug 10, 2010 E0-285@SERC 2

CAD of VLSI Systems

z z z z z z

Design of VLSI Systems Complex p system y Need systematic methodology Algorithms Can be automated Sh ld h Should handle dl very l large d designs i

Aug 10, 2010

E0-285@SERC

Design Domains (Y - Chart)

B h Behavaioral i l Domain D i
System Algorithms g Reg. Transfers Logic Transfer functions

St t l D Structural Domain i
Processors ALU, RAM, .. Gates, FFs, .. Transistors Transistor Layout Cell Layout Module Layout Floorplan Physical Partitions

Physical Domain
Aug 10, 2010 E0-285@SERC

Gajski 1982 Gajski,

4

Algorithms
z z z z z z z

Mostly M l i intractable bl problems bl Exact Algorithms Approximate algorithms Branch and Bound Dynamic y Programming g g Greedy Algorithms Soft computing techniques

Genetic Algorithms Ant colony optimization Tabu search etc..

Aug 10, 2010

E0-285@SERC

Wh t is What i Linear Li Programming P i

z

Linear programming Li i (LP) is i a mathematical th ti l method for selecting the best solution from the available solutions of a problem. Method:
will be determined. Develop a linear programming model:

State the problem and define variables whose values

Write the problem as an optimization formula (a linear
expression to be minimized or maximized) Write a set of linear constraints

An available LP solver (computer program) gives the

values of variables
Aug 10, 2010 E0-285@SERC 6

Types of LPs
z z z

LP all variables are real. ILP all variables are integers. g MILP some variables are integers, others are real. A reference:

S. S I I. Gass, Gass An Illustrated Guide to Linear

Programming, New York: Dover, 1990.

Aug 10, 2010

E0-285@SERC

A Single-Variable Si l V i bl P Problem bl
z z

Consider variable x Problem: find the maximum value of x subject to constraint, 0 x 15. Solution: x = 15.
Constraint satisfied 0 15 Solution x = 15
Aug 10, 2010 E0-285@SERC 8

Single Variable Problem (Cont.)

z z

Consider more complex constraints: Maximize x, subject to following constraints:

x0 5x 75 6x 30 x 10

(1) (2) (3) (4)

5
( ) (3)

10

15
(2) (4)

x
(1)

All constraints satisfied Solution, x = 5

Aug 10, 2010 E0-285@SERC 9

A Two-Variable Problem
z

Manufacture of chairs and tables: Resources available:

Material: 400 boards of wood Labor: 450 man-hours man hours Chair: $45 Table: $80 Chair

Profit:

Resources needed:

Table

5 boards of wood 10 man-hours 20 boards of wood 15 man-hours

Problem: How many y chairs and how many y tables should be manufactured to maximize the total profit?
Aug 10, 2010 E0-285@SERC 10

Formulating Two-Variable Problem

z

Manufacture x1 chairs and x2 tables to maximize profit: P = 45x1 + 80x2 dollars Subject to given resource constraints:

400 boards of wood, 450 man-hours of labor, x1 0 x2 0

5x1 + 20x2 400 10x1 + 15x2 450

(1) (2) (3) (4)

Aug 10, 2010

E0-285@SERC

11

S l ti Solution: Two-Variable T V i bl P Problem bl

40 30

Tables, x2 T

Best solution: 24 chairs, 14 tables P fit = 4524 + 8014 = 2200 dollars Profit d ll (24, 14) (3)

(1) 20
10 0 0 10

(4)
20 30

Chairs, x1

40

50

60

70

80

90

(2) decresing

increasing

Aug 10, 2010

E0-285@SERC

12

Change Profit of Chair to $64/Unit

z

Manufacture x1 chairs and x2 tables to maximize profit: P = 64x1 + 80x2 dollars Subject to given resource constraints:

400 boards of wood, 450 man-hours man hours of labor, x1 0 x2 0

5x1 + 20x2 400 10x1 + 15x2 450

(1) (2) (3) (4)

13

Aug 10, 2010

E0-285@SERC

S l ti Solution: $64 Profit/Chair P fit/Ch i

40 30

Tables, x2 T

Best solution: 45 chairs, 0 tables P fit = 6445 + 800 = 2880 dollars Profit d ll

(1) 20
10

(24, 14) (3) (4)

10 20 30

0 0

Chairs, x1

40

50

60

(2)

70

80

90

increasing g decresing 14

Aug 10, 2010

E0-285@SERC

AD Dual lP Problem bl
z
z

Explore an alternative.
Questions: Should we make tables and chairs? Or, auction off the available resources? To answer this question we need to know: What is the minimum price for the resources that will p provide us with same amount of revenue as the profits from tables and chairs? This is the dual of the original problem.
Aug 10, 2010 E0-285@SERC 15

Formulating the Dual Problem

z

Revenue received by selling off resources:

For each board,, w1 For each man-hour, w2

5w1 + 10w2 20w1 + 15w2 w1 0 w2 0

z z

Minimize 400w1 + 450w2 Subject to constraints:

45 80

Aug 10, 2010

E0-285@SERC

16

Th Duality The D lit Th Theorem

z

If the primal has a finite optimal solution, so does the dual, and the optimum values of the objective functions are equal.

Aug 10, 2010

E0-285@SERC

17

Primal-Dual Problems
z

Primal problem

Dual Problem

Fixed resources Maximize profit

Fixed profit Minimize value

Variables:

Variables:

x1 (number of chairs) x2 (number of tables)

z z

z z

Maximize profit 45x1+80x2 Subject to:

5x1 + 20x2 10x1 + 15x2 x1 x2 400 450 0 0

w1 ($ value/board of wood) w2 ($ value/man-hour)

Minimize value 400w1+450w2 Subject to:

5w1 + 10w2 20w1 + 15w2 w1 w2 45 80 0 0

Solution:

Solution:
w1 = $1, $1 w2 = $4 value = $2200
18

x1 = 24 chairs chairs, x2 = 14 tables Profit = $2200

Aug 10, 2010

E0-285@SERC

LP for f n Variables V i bl
minimize

cj xj

Objective function

j =1
subject to

aij xj
j =1 n

bi,

i = 1, 2, . . ., m

j =1

cij xj

= di,

i = 1, 2, . . ., p

Variables: xj Constants: cj, aij, bi, cij, di

Aug 10, 2010 E0-285@SERC 19

Algorithms for Solving LP

z

Simplex method

G. B. Dantzig, Linear Programming and Extension, Princeton, New Jersey, Princeton University Press, 1963. L. G. Khachiyan, A Polynomial Algorithm for Linear Programming, Soviet Math. Dokl., vol. 20, pp. 191-194, 1984. N. K. Karmarkar, A New Polynomial-Time Algorithm for Linear Programming, Combinatorica, vol. 4, pp. 373-395, 1984.

Ellipsoid method

Interior-point method

Aug 10, 2010

E0-285@SERC

20

Extreme points

Basic Ideas of Solution methods

Extreme points

Constraints

Objective f function ti

C Constraints i

Objective f function

Simplex: search on extreme points.

Interior-point methods: Successively iterate with interior spaces of analytic convex boundaries.
21

Aug 10, 2010

E0-285@SERC

I t Integer Linear Li Programming P i (ILP)

z z z

Variables are integers. Complexity p y is exponential p higher g than LP. LP relaxation

Convert all variables to real real, preserve ranges ranges. LP solution provides guidance. Rounding LP solution can provide a non-optimal non optimal
solution.

Aug 10, 2010

E0-285@SERC

22

Solving TSP: Five Cities

Distances (dij) in miles (symmetric TSP TSP, general TSP is asymmetric)

City i=1 i=2 i=3 i=4 i=5

Aug 10, 2010

j=1 0 18 10 12 27

j=2 18 0 5 12 20

j=3 10 5 0 15 19

j=4 12 12 15 0 6

j=5 27 20 19 6 0
23

E0-285@SERC

Search Space: No. of Tours

z

Asymmetric TSP tours

Five-city problem: 4 3 2 1 = 24 tours Nine-city Nine city problem: 362 362,880 880 tours 14-city problem: 87,178,291,200 tours 50-city problem: 49! = 6.0810 6 081062 tours
Time for enumerative search assuming 1 s per tour evaluation = 1.931055 years y

Aug 10, 2010

E0-285@SERC

24

A Greedy y Heuristic Solution

City i=1 (start) i=2 i=3 i=4 i=5
Aug 10, 2010

j=1 0 18 10 12 27

j=2 18 0 5 12 20

j=3 10 5 0 15 19

j=4 12 12 15 0 6

j=5 27 20 19 6 0
25

Tour length = 10 + 5 + 12 + 6 + 27 = 60 miles (non-optimal)

E0-285@SERC

ILP Variables, Constants and Constraints

x14 [0,1] [0 1] d14 = 12 1 4 5 x15 [0,1] d15 = 27 x12 [0,1] d12 = 18

Integer variables: xij = 1, travel i to j xij = 0, do not travel i to j Real variables: dij = distance from i to j

x13 [0,1] d13 = 10 3 x12 + x13 + x14 + x15 = 2 f four other th similar i il equations ti
Aug 10, 2010

E0-285@SERC

26

Obj ti Objective F Function ti and d ILP S Solution l ti

5 i-1 Minimize xij dij i=1 j=1

xij j=1 2 3 4 5 i=1 0 0 1 0 0 2 1 0 0 0 0 3 0 1 0 0 0 4 0 0 0 0 1 5 0 0 0 1 0

Aug 10, 2010 E0-285@SERC

xij = 2 ji

for all i

27

ILP Solution
d54 = 6
4 1 5

d21 = 18 d13 = 10
3 2

d45 = 6

d32 = 5

Total length = 45 but not a single tour

Aug 10, 2010

E0-285@SERC

28

Additional Constraints for Single Tour

z

Following constraints prevent split tours. For any subset S of cities, the tour must enter and exit that subset:
xij 2 for all S, |S| < 5 iS jS Remaining set At least two arrows must cross this boundary.

Any subset
Aug 10, 2010 E0-285@SERC 29

ILP Solution
d41 = 12
1 4

d54 = 6
5

d25 = 20 d13 = 10
3 2

d32 = 5

Total length = 53

Aug 10, 2010

E0-285@SERC

30

Characteristics of ILP
z z

Worst-case complexity is exponential in number of variables. Li Linear programming i (LP) relaxation, l ti where h i integer t variables are treated as real, gives a lower bound on the objective j function. Recursive rounding of relaxed LP solution to nearest integers gives an approximate solution to th ILP problem. the bl

Aug 10, 2010

E0-285@SERC

31

Algorithms
z

A Graph G(V, E) is a pair (V, E), where V is a set and E is a relation on V Directed Graph - the edges are ordered pairs of vertices Undirected Graph p edges g are unordered p pairs

Aug 10, 2010

E0-285@SERC

32

A hit t Architectural l Synthesis S th i

Computation: Differential Equation Solver xl = x + dx ul = u ( (3*x*u*dx) )( (3*y*dx) y ) c = xl < a Data Flow Graph (DFG): represent operation and data dependencies
Aug 10, 2010 E0-285@SERC 33

D t Fl Data Flow G Graph h

x 3 u dx 3 y u dx x dx

*
3

*
7

*
dx y

*
+
yl

8
xl

+ <
c

10
a

*
4

11

ul
E0-285@SERC 34

Aug 10, 2010

Graph Representation
1 d 4 a e c 3

1
2 b

2 1 0 0 0

3 1 1 0 0

4 1 0 1 0

1 2 3 4

0 0 0 0

Aug 10, 2010

E0-285@SERC

35

Graph Representation
1 d 4 a e c 3 2 b 2 3 4 1
2

3 4

Aug 10, 2010

E0-285@SERC

36

Graph Algorithms
Shortest h Path h Algorithms l h

Longest g Path Algorithms g Traveling Salesman Problem Maximal M i l Cliques Cli Graph Colouring Vertex Covering Minimum Spanning Tree
Aug 10, 2010 E0-285@SERC 37

Graph Algorithms
z z z z z z

Mostly intractable problems Approximate algorithms B Branch h and dB Bound d Dynamic Programming Greedy Algorithms Soft computing techniques

Genetic Algorithms g Ant colony optimization Tabu search etc..

Aug 10, 2010

E0-285@SERC

38

Graph Algorithms
z z

Shortest Path algorithms Dijkstras j algorithm g

10

1
30 10

100

Greedy algorithm Make local decision g greedily y Gives shortest path from a
source node

5
60

20

Aug 10, 2010

E0-285@SERC

39

Dijkstras Algorithms
10

1
30 10

Iter. S 100

V-S

w 2 4 3 5

D[2] 10 10 10 10 10

D[3] D[4] D[5] 60 50 50 50 30 30 30 30 30 100 100 90 60 60

Init {1} {2 {2,3,4,5} 3 4 5} 1 2 3 4 {1,2} {3,4,5} {1,2,4} {3,5} {1,2,4,3} {5} {1,2,4,3,5}

2
50

5
60

20

Aug 10, 2010

E0-285@SERC

40

Dijkstras Algorithms
z z z

Begin S = {1} F I = 2 to For t n do d

10

1
30 10

100

2 3

5
60

D[i] = C [1,i] initialize Choose a vertex w in V-S s.t. D[w] is minimum Add w to S F each For h vertex t v in i V-S V S do d

For I = 1 to n n-1 1 do begin

20

D[v] = Min{D[v], D[w]+C[w,v]}

end
Aug 10, 2010 E0-285@SERC 41

Floyds Algorithms
z z

All Pair Shortest Path algorithms Floyds y algorithm g

Make local decision and refine it later Gives shortest p path for all p pairs
2 8

2
5

Aug 10, 2010

E0-285@SERC

42

Floyds Algorithms
2 8

2
5

1 2 1 0 8 2 3 3 0 2 A0[i,j]
Aug 10, 2010

3 5 0

1 1 0 2 3 3

2 8 0

3 5 8 0

A1[i,j]
E0-285@SERC 43

Floyds Algorithms
2 8

2
5

1 2 1 0 8 2 3 3 5 A2[i,j]
Aug 10, 2010

3 5 8 0

1 1 0 2 3 3 5 A3[i,j]
E0-285@SERC

2 7 0 2

3 5 8 0

0 2

44

Floyds Algorithms
z z z

Begin S = {1} For I = 2 to n do

For j = 1 to n do

2
5

A[I,j] = C [i,j] initialize

For I = 1 to n do
A[I i] = 0 A[I,i]

For k = 1 to n-1 do begin

For i = 1 to n do

For j = 1 to n do

If A[I,k]+A[k,j] < A[I,j] then A[I,j] = A[I,k]+A[k,j] P[I j] = k P[I,j]

end
Aug 10, 2010 E0-285@SERC 45

Spanning Tree
z z z z

Free three F th that th t connects t all ll the th vertices ti Cost of a spanning tree is sum of edges Minimum Spanning Tree (MST) Prims Algorithm
Greedy algoritthm Start from an intial node U = {1} Grows G ST, ST one edge d at t a time ti At each step, it finds a shortest edge (u,v) that connects U and V V-U U and adds v to V V-U U from U
Aug 10, 2010 E0-285@SERC 46

Prims Algorithm
6

1
5 6 1

5 5 4

1 4
2

2
3

3
6

2
3

4
4 2

Aug 10, 2010

E0-285@SERC

47

Prims Algorithm
2
3 6 5 6

1
1

5 5 4

1 4 6 2 5 1 3 4 6 4

3
6 1

4 6
2

2 5

1 3

1 4 4 6 2 5 2 5 1 3 4 4 6
E0-285@SERC

1 2 3 5
48

2 5

1 3

1 3 4 4 6 2

Aug 10, 2010

Kruskals Algorithm
z z z

Start with a graph t = (V,) only vertices Each vertex is connected component in itself As algorithm progresses, To build progressively larger connected component

Have collection of connected components For each component select an edge for ST

Examine edges for E in order of increasing cost If the edge connects two vertices in two different connected component, tthen add edge to T
E0-285@SERC 49

Aug 10, 2010

Kruskals Algorithm
2
3 6 5 6

1
1

5 5 4

3
6 1

4 6
2

2 5

1 3 6

2 5

1 1 3 6

4 2

1 1 4 2 6 2 3 5 3 4 4 6
E0-285@SERC

1 2 3 5
50

2 3 5

1 3

1 3 4 4 6 2

Aug 10, 2010

Vertex Covering Problem

z

Vertex Covering of an undirected graph G is a subset of the vertices s.t. each edge in E has h at t least l t one edge d in i th that t subset b t Heuristic

Select vertex with largest degree Deletion of a vertex corresponds to the removal
of f vertex itself i lf and d all ll edges d i incident id to i it

Aug 10, 2010

E0-285@SERC

51

Vertex Covering Problem

1 2 3 4 5

3 1
Aug 10, 2010

4 2

3 1
E0-285@SERC

4 2
52

Graph Colouring Problem

z

z z

Graph G h colouring l i problem bl of f an undirected di t d graph G is a labeling of vertices such that no edge in E has two end end-points points with the same label Search for a vertex colouring with minimum number of colours Most algorithms are based on sequential scan of vertex set where vertices are coloured one at a time
Aug 10, 2010 E0-285@SERC 53

THANK YOU
Aug 10, 2010 E0-285@SERC 54