NR
Code No: 54217/MT
M.Tech. – II Semester Regular Examinations, September, 2008 ALGORITHMS FOR VLSI DESIGN AUTOMATION (Common to Digital Systems & Computer Electronics/ VLSI System Design/ VLSI & Embedded Systems) Time: 3hours
1.a) b)
Max. Marks:60
Answer any FIVE questions All questions carry equal marks --What are the most important entities in VLSI Design? Explain about each of them? Draw the sketch for decomposition tree and explain about the stabilized view of a design.
2.a) b)
Explain about computational complexity. Distinguish between Depth-First search and Breadth-First Search methods.
3.a)
Give an algorithm for an exhaustive search by means of back tracking. Give the Pseudo code description of simulated annealing.
b) 4.a) b)
Give the symbolic layout of a CMOS Inverter and its geometric layout. Explain about the Liao-Wong Algorithm.
5.a) b)
Explain about ROBDD Manipulation with an example. What is meant by variable ordering? Explain.
6.a) b)
Give an example for a conditional construct. Draw the Data Flow graph of a second order digital filter section.
7.a) b)
What are the various FPGA Technologies? Explain. Explain about Routing for staggered models.
8.
Write a) b) c)
notes on any Two:MCM Physical design Full custom based Approaches Maze Routing x-x-x