NPTEL Online Certification Courses
Indian Institute of Technology Kharagpur
Course Name: VLSI PHYSICAL DESIGN
Assignment- Week 3
TYPE OF QUESTION: MCQ/MSQ/SA
Number of questions: 10 Total mark: 10 x 1 = 10
______________________________________________________________________________
QUESTION 1:
Which of the following is/are true for various types of routing?
a. Grid routing is responsible for determining the approximate regions through
which each interconnection net should pass.
b. Global routing is responsible for determining the approximate regions through
which each interconnection net should pass.
c. Horizontal and vertical metal line segments are assigned in the detailed routing.
d. Grid routing is responsible for horizontal and vertical metal line segment
assignment.
Correct Answer: b, c
Detailed Solution: Global routing is responsible for determining the approximate regions
through which each interconnection net should pass. In detailed routing interconnections are
completed by assigning horizontal and vertical metal line segments. On the other hand, grid
routing is responsible for interconnecting pins on a single layer.
The correct options are (b) and (c).
______________________________________________________________________________
QUESTION 2:
Which of the following is false for various grid routing algorithms?
a. The time and space complexity of Lee’s algorithm is O(N2) for a grid size of N x N.
b. Lee’s algorithm is a type of line search algorithm.
c. Lee’s algorithm is a type of Maze routing algorithm
d. Hadlock’s algorithm uses detour number for cell numbering.
Correct Answer: b
Detailed Solution: Lee’s algorithm is a type of Maze routing algorithm; the time and space
complexity is O(N2) for a grid size of N x N. Hadlock algorithm uses the detour number for
routing a net.
NPTEL Online Certification Courses
Indian Institute of Technology Kharagpur
The correct option is (b).
______________________________________________________________________________
QUESTION 3:
Consider a grid size of 3000 x 2000 for maze routing using Lee’s algorithm with the regular cell
numbering scheme (1, 2, 3, 4, etc.). In the worst case, the total memory requirement will be:
a. 6.25 x 106 bytes
b. 3.75 x 106 bytes
c. 9.75 x 106 bytes
d. 5.25 x 106 bytes
Correct Answer: c
Detailed Solution: The memory requirement per grid cell will be log2 (3000 + 2000 + 1) = 13
bits (taking the ceiling function). Hence, the total memory required will be
3000 * 2000 * 13 / 8 bytes = 9.75 x 106 bytes
The correct option is (c).
______________________________________________________________________________
QUESTION 4:
Consider a 2000 x 2000 grid for maze routing using Lee’s algorithm with the improved cell
numbering scheme (1, 2, 3, 4, 1, 2, 3, 4 etc.). In the worst case, the total memory requirement
will be:
a. 1.50 x 106 bytes
b. 1.75 x 106 bytes
c. 1.25 x 106 bytes
d. 1.35 x 106 bytes
Correct Answer: a
Detailed Solution: The memory requirement per grid cell will be log2 (4 + 2) = 3 bits (taking the
ceiling function). Hence, the total memory required will be
2000 * 2000 * 3 / 8 bytes = 1.5 x 106 bytes
The correct option is (a).
______________________________________________________________________________
NPTEL Online Certification Courses
Indian Institute of Technology Kharagpur
QUESTION 5:
Consider a 2000 x 1000 grid for maze routing using Lee’s algorithm with the cell numbering
scheme (0, 0, 1, 1, 0, 0, 1, 1, etc.). In the worst case, the total memory requirement will be:
a. 0.50 x 106 bits
b. 1 x 106 bits
c. 2.50 x 106 bits
d. 1.50 x 106 bits
Correct Answer: a
Detailed Solution: The memory requirement per grid cell will be log2 (2 + 2) = 2 bits (taking the
ceiling function). Hence, the total memory required will be
2000 * 1000 * 2 / 8 bytes = 0.50 x 106 bytes
The correct option is (a).
______________________________________________________________________________
QUESTION 6:
In Lee’s algorithm, what will happen if we start from the point that is closer to the corner of the
grid?
a. We shall always obtain the minimum length path.
b. Less number of cells will get labeled on the average
c. There is no guarantee for finding the minimum length path.
d. More number of cells will get labeled on the average
Correct Answer: a, b
Detailed Solution: In Lee’s algorithm, if we start from near the center of the grid, cell
numbering will proceed in all four directions, and more number of cells will get labeled on the
average. However, if we start from near one corner, we have to proceed in one direction only,
and less number of cells will get labeled. In both the cases, Lee’s algorithm will find the
minimum length path.
Hence, the correct options are (a) and (b).
______________________________________________________________________________
NPTEL Online Certification Courses
Indian Institute of Technology Kharagpur
QUESTION 7:
Which of the following is/are true for the line search algorithms?
a. The line search algorithm guarantees to find the optimal path.
b. The algorithm guarantees to find the shortest path but the number of bends may
be quite large.
c. All the trial lines that are generated during a particular iteration are all parallel to
each other.
d. The trial lines generated during consecutive iterations are perpendicular to each
other.
Correct Answer: c, d
Detailed Solution: In the line search algorithm (Mikami‐Tabuchi or Hightower), in every
iteration some trial lines are generated from both source and target points. In a particular
iteration, all lines generated are parallel to each other, and across iterations they are
perpendicular. In the presence of obstacles, the methods do not guarantee the finding of
shortest path.
Hence, the correct options are (c) and (d).
____________________________________________________________________________
QUESTION 8:
Suppose we are running Hadlock’s algorithm to find a path from a source point S to a target
point T within a 50 x 50 array of grid cells. If the co‐ordinates of S and T are (7,5) and (20,12)
respectively, the detour number of a cell with co‐ordinates (3,19) will be _________. Assume
that the lower left and upper right grid cells have co‐ordinates (0,0) and (49,49) respectively.
Correct Answer: 11
Detailed Solution: The detour number d(P) of a path P connecting two cells S and T is defined
as the number of grid cells directed away from the target T. For the cell with co‐ordinates
(3,19), the x‐value is 4 less than the x‐value of the source (i.e. in opposite direction), and the y‐
value is 7 more than the y‐value of the target (i.e. in opposite direction). Hence, the detour
number will be 4 + 7 = 11.
_____________________________________________________________________________
NPTEL Online Certification Courses
Indian Institute of Technology Kharagpur
QUESTION 9:
Which of the following objectives are true for global routing?
a. It defines the routing regions.
b. Each net is assigned a tentative route through the routing regions.
c. Each net is assigned to tracks within the routing regions.
d. All of these.
Correct Answer: a, b
Detailed Solution: During global routing, the routing regions are identified, and the tentative
route for each net is determined (as an ordered sequence of routing regions). No detailed
assignment of nets to tracks is assigned in this phase.
The correct options are (a) and (b).
______________________________________________________________________________
QUESTION 10:
For the integer linear programming based approach to global routing, which of the following
statements are false?
a. The layout is modeled as a channel intersection graph.
b. For every multi‐terminal net, we try to select the best Steiner tree to route
among several alternatives.
c. Each edge in the graph is initially considered to be of infinite capacity, which gets
defined as part of the final solution.
d. The approach cannot be used for large problem instances.
Correct Answer: a, b
Detailed Routing: In the ILP formulation, the layout is modeled as a channel intersection
graph, and the net is modeled as a Steiner tree. The time complexity is high, and so it cannot be
used for large problem instances.
The correct options are (a) and (b).
______________________________________________________________________________
************ END ************
