📄 ch16.6.htm
字号:
<P CLASS="TableEqnRight">
<A NAME="pgfId=113246">
</A>
<SPAN CLASS="EquationVariables">
i</SPAN>
= 1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113248">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=113250">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=113252">
</A>
<SPAN CLASS="EquationVariables">
i</SPAN>
= 1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113254">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113173">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=113175">
</A>
</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=113181">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113183">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=113185">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=113187">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113189">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113191">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=113193">
</A>
</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=113199">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113201">
</A>
...</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=113203">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=113205">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113207">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113209">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=113211">
</A>
</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=113260">
</A>
<SUB CLASS="SubscriptVariable">
n</SUB>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113262">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=113264">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=113266">
</A>
<SUB CLASS="SubscriptVariable">
n</SUB>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113268">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=112983">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=112985">
</A>
</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=113270">
</A>
<SPAN CLASS="BigMath">
S</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113272">
</A>
<SPAN CLASS="EquationVariables">
x</SPAN>
<SUB CLASS="SubscriptVariable">
i</SUB>
<SUP CLASS="Superscript">
n</SUP>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=113274">
</A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=113276">
</A>
<SPAN CLASS="BigMath">
S</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113278">
</A>
<SPAN CLASS="EquationVariables">
p</SPAN>
<SUB CLASS="SubscriptVariable">
i</SUB>
<SUP CLASS="Superscript">
n</SUP>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113010">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=113012">
</A>
(16.22)</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=113280">
</A>
<SPAN CLASS="EquationVariables">
i</SPAN>
= 1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113282">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=113284">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=113286">
</A>
<SPAN CLASS="EquationVariables">
i</SPAN>
= 1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113288">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113024">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=113026">
</A>
</P>
</TD>
</TR>
</TABLE>
<P CLASS="ExerciseNoIndent">
<A NAME="pgfId=8364">
</A>
(<SPAN CLASS="Emphasis">
Hint:</SPAN>
Consider the polynomial (<SPAN CLASS="Emphasis">
x</SPAN>
+ <SPAN CLASS="EquationVariables">
x</SPAN>
<SUB CLASS="SubscriptVariable">
i</SUB>
)<SUP CLASS="SuperscriptVariable">
n</SUP>
. In our simplification to the problem, we chose to impose only the second equation of these constraints.)</P>
<P CLASS="ExerciseHead">
<A NAME="pgfId=10046">
</A>
16.4 <A NAME="37002">
</A>
(*Eigenvalue placement, 30 min.) You will need MatLab, Mathematica, or a similar mathematical calculus program for this problem. </P>
<UL>
<LI CLASS="ExercisePartFirst">
<A NAME="pgfId=11189">
</A>
a. Find the eigenvalues and eigenvectors for the disconnection matrix corresponding to the following connection matrix:</LI>
</UL>
<P CLASS="ComputerFirst">
<A NAME="pgfId=10946">
</A>
<SPAN CLASS="BodyComputer">
C=</SPAN>
</P>
<P CLASS="Computer">
<A NAME="pgfId=11460">
</A>
<SPAN CLASS="BodyComputer">
[ 0 1 1 0 0 0 1 0 0;</SPAN>
</P>
<P CLASS="Computer">
<A NAME="pgfId=10947">
</A>
<SPAN CLASS="BodyComputer">
1 0 0 0 0 0 0 0 0;</SPAN>
</P>
<P CLASS="Computer">
<A NAME="pgfId=10948">
</A>
<SPAN CLASS="BodyComputer">
1 0 0 1 0 0 0 1 0;</SPAN>
</P>
<P CLASS="Computer">
<A NAME="pgfId=10949">
</A>
<SPAN CLASS="BodyComputer">
0 0 1 0 0 1 0 0 0;</SPAN>
</P>
<P CLASS="Computer">
<A NAME="pgfId=10950">
</A>
<SPAN CLASS="BodyComputer">
0 0 0 0 0 1 0 0 1;</SPAN>
</P>
<P CLASS="Computer">
<A NAME="pgfId=10951">
</A>
<SPAN CLASS="BodyComputer">
0 0 0 1 1 0 1 0 0;</SPAN>
</P>
<P CLASS="Computer">
<A NAME="pgfId=10952">
</A>
<SPAN CLASS="BodyComputer">
1 0 0 0 0 1 0 0 0;</SPAN>
</P>
<P CLASS="Computer">
<A NAME="pgfId=10953">
</A>
<SPAN CLASS="BodyComputer">
0 0 1 0 0 0 0 0 1;</SPAN>
</P>
<P CLASS="ComputerLast">
<A NAME="pgfId=10954">
</A>
<SPAN CLASS="BodyComputer">
0 0 0 0 1 0 0 1 0;]</SPAN>
</P>
<P CLASS="ExerciseNoIndent">
<A NAME="pgfId=11455">
</A>
(<SPAN CLASS="Emphasis">
Hint: </SPAN>
Check your answer. The smallest, nonzero, eigenvalue should be 0.5045.)</P>
<UL>
<LI CLASS="ExercisePart">
<A NAME="pgfId=11620">
</A>
b. Use your results to place the logic cells. Plot the placement and show the connections between logic cells (this is easy to do using an X-Y plot in an Excel spreadsheet).</LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=11185">
</A>
c. Check that the following equation holds: </LI>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=113320">
</A>
<SPAN CLASS="Symbol">
l</SPAN>
<SPAN CLASS="Vector">
</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=113322">
</A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113324">
</A>
<SPAN CLASS="EquationVariables">
g</SPAN>
/P .</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113326">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=113328">
</A>
</P>
</TD>
</TR>
</TABLE>
</UL>
<P CLASS="ExerciseHead">
<A NAME="pgfId=5674">
</A>
16.5 <A NAME="17928">
</A>
(Die size, 10 min.) Suppose the minimum spacing between pad centers is <SPAN CLASS="EquationVariables">
W</SPAN>
mil (1 mil = 10<SUP CLASS="Superscript">
–3</SUP>
inch), there are <SPAN CLASS="EquationVariables">
N</SPAN>
I/O pads on a chip, and the die area (assume a square die) is <SPAN CLASS="EquationVariables">
A</SPAN>
mil<SUP CLASS="Superscript">
2</SUP>
: </P>
<UL>
<LI CLASS="ExercisePartFirst">
<A NAME="pgfId=94570">
</A>
a. Derive a relationship between <SPAN CLASS="EquationVariables">
W</SPAN>
, <SPAN CLASS="EquationVariables">
N</SPAN>
, and <SPAN CLASS="EquationVariables">
A</SPAN>
that corresponds to the point at which the die changes from being pad-limited to core-limited. </LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=94571">
</A>
b. Plot this relationship with <SPAN CLASS="EquationVariables">
N</SPAN>
(ranging from 50 to 500 pads) on the <SPAN CLASS="Emphasis">
x</SPAN>
-axis, <SPAN CLASS="EquationVariables">
A</SPAN>
on the <SPAN CLASS="Emphasis">
y</SPAN>
-axis (for dies ranging in size from 1 mm to 20 mm on a side), and <SPAN CLASS="EquationVariables">
W</SPAN>
as a parameter (for <SPAN CLASS="EquationVariables">
W</SPAN>
= 1, 2, 3, and 4 mil).</LI>
</UL>
<P CLASS="ExerciseHead">
<A NAME="pgfId=5713">
</A>
16.6 <A NAME="16197">
</A>
(Power buses, 20 min.) Assume aluminum metal interconnect has a resistance of about 30 m<SPAN CLASS="Symbol">
W</SPAN>
/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 <SPAN CLASS="EquationVariables">
V</SPAN>
<SUB CLASS="SubscriptVariable">
DD</SUB>
= 5 V, and assume that half of the supply current (0.5 A) is due to I/O. Suppose the square die is <SPAN CLASS="EquationVariables">
L</SPAN>
mil on a side, and that the I/O current is equally distributed among the <SPAN CLASS="EquationVariables">
N</SPAN>
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). </P>
<UL>
<LI CLASS="ExercisePartFirst">
<A NAME="pgfId=5746">
</A>
a. Model the power distribution as a ring of <SPAN CLASS="EquationVariables">
N</SPAN>
equally spaced pads. Each pad is connected by a resistor equal to the aluminum VDD power-bus resistance between two pads. Assume the I/O circuits associated with each pad can be considered to connect to just one point on the resistors between each pad. If the resistance between each pad is <SPAN CLASS="EquationVariables">
R</SPAN>
, what is the worst-case resistance between the I/O circuits and the supply? </LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=5747">
</A>
b. Plot a graph showing <SPAN CLASS="EquationVariables">
L</SPAN>
(in mil) on the <SPAN CLASS="Emphasis">
x</SPAN>
-axis, <SPAN CLASS="EquationVariables">
W</SPAN>
(the required power-bus width in microns) on the <SPAN CLASS="Emphasis">
y</SPAN>
-axis, with <SPAN CLASS="EquationVariables">
N</SPAN>
as a parameter (with <SPAN CLASS="EquationVariables">
N</SPAN>
= 1, 2, 5, 10).</LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=5742">
</A>
c. Comment on your results.</LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=52601">
</A>
d. An upper limit on current density for aluminum metallization is about 50 kAcm<SUP CLASS="Superscript">
–2</SUP>
; at current densities higher than this, failure due to electromigration (which we shall cover in Section 17.3.2, “Power Routing”) is a problem. Assume the metallization is 0.5 <SPAN CLASS="Symbol">
m</SPAN>
m thick. Calculate the current density in the VDD power bus for this chip in terms of the power-bus width and the number of pads. Comment on your answer.</LI>
</UL>
<P CLASS="ExerciseHead">
<A NAME="pgfId=7253">
</A>
16.7 <A NAME="29063">
</A>
(Interconnect-length approximation, 10 min.) <A HREF="CH16.2.htm#32290" CLASS="XRef">
Figure 16.22</A>
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.</P>
<P CLASS="ExerciseHead">
<A NAME="pgfId=58632">
</A>
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.</P>
<P CLASS="ExerciseHead">
<A NAME="pgfId=86793">
</A>
16.9 <A NAME="32610">
</A>
(***Min-cut, 120 min.) Many floorplanning and placement tools use min-cut methods and allow you to alter the type and sequence of <A NAME="marker=86794">
</A>
bisection cuts. Research and describe the difference between: <A NAME="marker=86795">
</A>
quadrature min-cut placement, <A NAME="marker=86796">
</A>
bisection min-cut placement, and <A NAME="marker=86797">
</A>
slice/bisection min-cut placement.</P>
<P CLASS="ExerciseHead">
<A NAME="pgfId=100607">
</A>
16.10 (***Terminal propagation, 120 min.) There is a problem with the min-cut algorithm in the way connectivity is measured. <A HREF="CH16.6.htm#25999" CLASS="XRef">
Figure 16.33</A>
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. <SPAN CLASS="Emphasis">
Hint:</SPAN>
See <A NAME="Dunlop83">
</A>
Dunlop [1983]; <A NAME="Hartoog86">
</A>
Hartoog [1986]; or the Barnes–Hut galaxy model.</P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=100619">
</A>
</P>
<DIV>
<IMG SRC="CH16-34.gif">
</DIV>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigureTitle">
<A NAME="pgfId=100626">
</A>
FIGURE 16.33 <A NAME="25999">
</A>
(For Problem <A HREF="CH16.6.htm#Dunlop83" CLASS="XRef">
16.10</A>
.) 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<SUB CLASS="Subscript">
1</SUB>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -