Thapar University 2006 B.E Computer Science CAD for VLSI - Question Paper

Thapar Institute of Engineering & Technology
B.Tech CS (4th Year)
Final Term exam
CS019 (CAD for VLSI)

THAPAR INSTITUTE OF ENGINEERING & TECHNOLOGY

COMPUTER SCIENCE & ENGINEERING DEPARTMENT Semester : July-Dee 2006

Course Code : CS-024    Max. Marks : 72

Course : CAD for VLSI    Time : 3 Hours

Note : 1) All questions are compulsory.

_2) Attempt all parts of a question sequentially at one place._

1. For the rectangular floorplan shown in Fig. 1 and corresponding cell's sizes as given in Table 1, attempt the followings-

Module No.	Width	Height
1	2	1
2	2	2
3	4	3
4	3	1
5	1	3
6	1	1
7	3	2
8	3	1
9	2	4

Fig. 1 Floorplan    Table 1 Cell sizes

a)    Draw the vertical and horizontal adjacency graphs corresponding to the above floorplan.

b)    Use the adjacency graphs to determine the minimum required width and height of the floorplan

c)    Draw the skewed slicing tree corresponding to the above slicing'floorplan.

d)    Determine the normalized polish expression corresponding to the skewed slicing tree.

(4x4)

2.    a) What are the general uses of global routing? Explain.    4

b)    Discuss the global routing problem and objectives for various layout styles, namely, gate-array, standard-cell and building block design style.    6

c)    Suggest at least two techniques for removing cycles from the ordered constraint graph.

4

3.    a) S and T are two points on a routing grid. The horizontal separation between S and T is

/ \ m + n

m units, and the vertical separation is n units. Show that there are R(m,n)-

l ^m ,

ways of routing a two-pin net from S to T. Assume that only vertical and horizontal routing are permitted, and assume that there is a single routing layer. What happens to R(m,n) when m = n ?    8

b) In the above problem, if we permit 45 and 135 routing also, how many ways are there to route a net from S and T?    4

r r

c) The label clearing phase of Lee algorithm is as complex as the filling phase. Suggest a technique to speed up this process.    2

4 For the 5-point net shown below, attempt the followings -

A

B

c

a) The cost of connecting one point to another is measured by the Manhattan distance between two points. Construct a minimum spanning tree to join all the five points of the

net. What is the cost of minimum spanning tree?    3

b)    Calculate the cost using minimum chain method. Compare the resulting cost with that of minimum spanning tree method.    3

c)    Discuss the placement problem cost functions and constraints parameters.    8

5 a) Draw the 3-input CMOS NAND gate.    3

b)    Write difference between Artificial neural network computing and conventional computing.    4

c)    Explain hardware software co-design.    4

d)    Explain supervised and unsupervised learning methods of neural network.    3

Attachment: thapar-university-2006-b-e-computer-science-25962-1.pdf

Earning:   Approval pending.