[ Chapter start ] [ Previous page ] [ Next page ]
| ||
* = Difficult, ** = Very difficult, *** = Extremely difficult
16.1 (Wire loads, 30 min.) Table 16.2 shows a wire-load table. Since you might expect the interconnect load to be a monotonic increasing function of fanout and block area, it seems as though some of the data in Table 16.2 may be in error; these figures are shown preceded by an asterisk, '*' (this table is from an ASIC vendor data book). Using a spreadsheet, analyze the data in Table 16.2 .
|
TABLE 16.2 Wire- load table. Predicted interconnect loads (measured in standard loads) as a function of block size and fanout (Problem 16.1 ). |
|||||||||||||
16.2 (Trees, 20 min.) For the network graph shown in Figure 16.32 (f), draw the following trees and calculate their Manhattan lengths:
Figure 16.32 parts (a–e) illustrate the definitions of these trees. There is no known solution to the minimum Steiner-tree problem for nets with more than five terminals.
|
|
FIGURE 16.32 Tree routing. (a) The minimum rectilinear Steiner tree (MRST). (b) The minimum rectilinear spanning tree. (c) The minimum single-trunk rectilinear Steiner tree (1-MRST). (d) The minimum rectilinear chain connection. (e) The minimum source-to-sink connection. (f) Example net for Problem 16.2 . |
16.3 (Eigenvalue placement constraints, 10 min. [ Cheng and Kuh, 1984]) Consider the one-dimensional placement problem with a vector list of valid positions for the logic cells p = [ p i ] and a vector list of x -coordinates for the logic cells x = [ x i ].
Show that for a valid placement x (where the vector elements x i are some permutation of the vector elements p i ), the following equations hold:
( Hint: Consider the polynomial ( x + x i ) n . In our simplification to the problem, we chose to impose only the second equation of these constraints.)
16.4 (*Eigenvalue placement, 30 min.) You will need MatLab, Mathematica, or a similar mathematical calculus program for this problem.
( Hint: Check your answer. The smallest, nonzero, eigenvalue should be 0.5045.)
16.5 (Die size, 10 min.) Suppose the minimum spacing between pad centers is W mil (1 mil = 10 –3 inch), there are N I/O pads on a chip, and the die area (assume a square die) is A mil 2 :
16.6 (Power buses, 20 min.) Assume aluminum metal interconnect has a resistance of about 30 m W /square (a low value). Consider a power ring for the I/O pads. Suppose you have a high-power chip that dissipates 5 W at V DD = 5 V, and assume that half of the supply current (0.5 A) is due to I/O. Suppose the square die is L mil on a side, and that the I/O current is equally distributed among the N VDD pads that are on the chip. In the worst case, you want no more than 100 mV drop between any VDD pad and the I/O circuits drawing power (notice that there will be an equal drop on the VSS side; just consider the VDD drop).
16.7 (Interconnect-length approximation, 10 min.) Figure 16.22 shows the correlation between actual interconnect length and two approximations. Use this graph to derive a correction function (together with an estimation of the error) for the complete-graph measure and the half-perimeter measure.
16.8 (Half-perimeter measure, 10 min.) Draw a tree on a rectangular grid for which the MRST is equal to the half-perimeter measure. Draw a tree on a rectangular grid for which the MRST is twice the half-perimeter measure.
16.9 (***Min-cut, 120 min.) Many floorplanning and placement tools use min-cut methods and allow you to alter the type and sequence of bisection cuts. Research and describe the difference between: quadrature min-cut placement, bisection min-cut placement, and slice/bisection min-cut placement.
16.10 (***Terminal propagation, 120 min.) There is a problem with the min-cut algorithm in the way connectivity is measured. Figure 16.33 shows a situation in which logic cells G and H are connected to other logic cells (A and F) outside the area R1 that is currently being partitioned. The min-cut algorithm ignores connections outside the area to be divided. Thus logic cells G and H may be placed in partition R3 rather than partition R2. Suggest solutions to this problem. Hint: See Dunlop [1983]; Hartoog [1986]; or the Barnes–Hut galaxy model.
|
|
FIGURE 16.33 (For Problem 16.10 .) A problem with the min-cut algorithm is that it ignores connections to logic cells outside the area being partitioned. (a) We perform a vertical cut 1 producing the areas R 1 and R 2 . (b) Next we make a horizontal cut 2, producing L 2 and L 3 , and a cut 2', producing R 2 and R 3 . (c) The min-cut algorithm ignores the connection from L 2 and is equally likely to produce the arrangement shown here when we make cut 2'. |
16.11 (Benchmarks and statistics, 30 min.) Your boss asks you to compare two placement programs from companies ABC and XYZ. You run five test cases for both on a single netlist, P1. You get results (measured in arbitrary units) of 9, 8, 9, 7, 11 for ABC; 6, 9, 10, 13, 8 for XYZ.
On average each test case takes about 0.5 hours (wall clock) for both ABC and XYZ. Next you run six test cases on another netlist, P2 with the following results: 4, 6, 7, 8, 5, 7 for ABC, and 4, 5, 3, 6, 4, 3 for XYZ. These test cases take about 0.75 hours (wall clock) each.
16.12 (Linear and quadratic placement, 20 min.) [ Sigl, Doll, and Johannes, 1991] Figure 16.34 (a) shows a simple network that we will place. Figure 16.34 (b) shows the problem. The logic cells are all the same size: 1 grid unit wide by 1 grid unit high. Logic cells 1 and 3 are fixed at the locations shown. Logic cell 2 is movable and placed at coordinates (for the lower-left corner) of ( x 2 , y 2 ). The lower-left corners of logic cells should be placed at grid locations and should not overlap.
where d ij is the distance between logic cells i and j .
|
FIGURE 16.34 Problem 16.12 illustrates placement objectives. (a) An example network for placement. (b) The placement restrictions. Logic cells 1 and 3 are fixed in position, the placement problem is to optimize the position of logic cell 2 under different placement objectives. |
16.13 (Placement interconnect lengths, 45 min.) Figure 16.30 (d) shows the actual routing corresponding to a placement with an estimated routing length of 8 units ( Figure 16.30 b).
16.14 (Zero-slack algorithm, 60 min.) For the circuit of Figure 16.35 :
|
FIGURE 16.35 A circuit to illustrate the zero-slack algorithm (Problem 16.14 ). |
i. Find arrival, required, and slack times on all nets.
ii. Find an input pin p with the least nonzero slack S p on a net which has not already been selected. If there are none go to step 6.
ii. Find the path through p (may include several gates) on which all pins have slack S p .
iv. Distribute a delay equal to the slack S p along the path assigning a fraction to each net at the output pins of the gates on the path.
v. Work backward from p updating all the required times as necessary and forward from p updating all the arrival times.
Hint: You can consult the original description of the zero-slack algorithm if this is not clear [ Hauge et al., 1987].
16.15 (World planning, 60 min.) The seven continents are (with areas in millions of square miles): Europe—strictly a peninsula of Asia (4.1), Asia (17.2), North America (9.4), South America (6.9), Australia (3.0), Africa (11.7), and Antarctica (5.1). Assume the continents are flexible blocks whose aspect ratio may be adjusted.
[ Chapter start ] [ Previous page ] [ Next page ]
| Copyright 1997 by Addison Wesley Longman, Inc. No part of this book may be printed, reproduced, stored, or transmitted without the prior written permission of the publisher. |
