📄 ch16.6.htm
字号:
and R<SUB CLASS="Subscript">
2</SUB>
. (b) Next we make a horizontal cut 2, producing L<SUB CLASS="Subscript">
2</SUB>
and L<SUB CLASS="Subscript">
3</SUB>
, and a cut 2', producing R<SUB CLASS="Subscript">
2</SUB>
and R<SUB CLASS="Subscript">
3</SUB>
. (c) The min-cut algorithm ignores the connection from L<SUB CLASS="Subscript">
2</SUB>
and is equally likely to produce the arrangement shown here when we make cut 2'.</P>
</TD>
</TR>
</TABLE>
<P CLASS="ExerciseHead">
<A NAME="pgfId=100632">
</A>
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.</P>
<UL>
<LI CLASS="ExercisePartFirst">
<A NAME="pgfId=83050">
</A>
a. Calculate the mean and standard deviations for these results.</LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=83051">
</A>
b. What confidence (in the statistical sense) do you have in these figures?</LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=8602">
</A>
c. What can you say about the relative performance of ABC and XYZ?</LI>
</UL>
<P CLASS="Exercise">
<A NAME="pgfId=8606">
</A>
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.</P>
<UL>
<LI CLASS="ExercisePart">
<A NAME="pgfId=8609">
</A>
d. What can you say about the P2 results?</LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=8610">
</A>
e. Given the P1 and P2 results together, what can you say about ABC and XYZ?</LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=8611">
</A>
f. How many P1 test cases should you run to get a result so that you can say ABC is better or worse than XYZ with 90 percent confidence (i.e., you make the right decision 9 out of 10 times)? How long would this take?</LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=9594">
</A>
g. Find the same figures for the P2 netlist. Comment on your answers.</LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=8619">
</A>
h. Suppose you had more netlists and information about the variation of results from each netlist, together with the average time to run each netlist. How would you use this information to get the most meaningful result in the shortest time?</LI>
</UL>
<P CLASS="ExerciseHead">
<A NAME="pgfId=24703">
</A>
16.12 <A NAME="30878">
</A>
(Linear and quadratic placement, 20 min.) [<A NAME="Sigl91">
</A>
Sigl, Doll, and Johannes, 1991] <A HREF="CH16.6.htm#25186" CLASS="XRef">
Figure 16.34</A>
(a) shows a simple network that we will place. <A HREF="CH16.6.htm#25186" CLASS="XRef">
Figure 16.34</A>
(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 (<SPAN CLASS="EquationVariables">
x</SPAN>
<SUB CLASS="Subscript">
2</SUB>
<SPAN CLASS="EquationVariables">
, y</SPAN>
<SUB CLASS="Subscript">
2</SUB>
). The lower-left corners of logic cells should be placed at grid locations and should not overlap.</P>
<UL>
<LI CLASS="ExercisePartFirst">
<A NAME="pgfId=62198">
</A>
a. What is the connection matrix <SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="SubscriptVariable">
ij</SUB>
for this network?</LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=24706">
</A>
b. Calculate and draw (showing the logic-cell coordinates) the placement that minimizes the linear cost function (or objective function) <SPAN CLASS="EquationVariables">
f</SPAN>
<SUB CLASS="SubscriptVariable">
L</SUB>
, </LI>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=113339">
</A>
<SPAN CLASS="Vector">
</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=113341">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=113382">
</A>
1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=113343">
</A>
<SPAN CLASS="EquationVariables">
n</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113345">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113396">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=113347">
</A>
</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=113352">
</A>
<SPAN CLASS="EquationVariables">
f</SPAN>
<SUB CLASS="SubscriptVariable">
L</SUB>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=113354">
</A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=113384">
</A>
––</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=113356">
</A>
<SPAN CLASS="BigMath">
S</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113358">
</A>
<SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="SubscriptVariable">
ij</SUB>
<SPAN CLASS="EquationVariables">
d</SPAN>
<SUB CLASS="SubscriptVariable">
ij</SUB>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113398">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=113360">
</A>
(16.23)</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=113362">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=113364">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=113386">
</A>
2</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=113366">
</A>
<SPAN CLASS="EquationVariables">
j</SPAN>
= 1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113368">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113400">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=113370">
</A>
</P>
</TD>
</TR>
</TABLE>
</UL>
<P CLASS="Exercise">
<A NAME="pgfId=115057">
</A>
where <SPAN CLASS="EquationVariables">
d</SPAN>
<SUB CLASS="SubscriptVariable">
ij</SUB>
is the distance between logic cells <SPAN CLASS="EquationVariables">
i</SPAN>
and <SPAN CLASS="EquationVariables">
j</SPAN>
.</P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=115116">
</A>
<IMG SRC="CH16-35.gif" ALIGN="BASELINE">
</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigureTitle">
<A NAME="pgfId=115119">
</A>
FIGURE 16.34 <A NAME="25186">
</A>
Problem <A HREF="CH16.6.htm#30878" CLASS="XRef">
16.12</A>
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.</P>
</TD>
</TR>
</TABLE>
<UL>
<LI CLASS="ExercisePart">
<A NAME="pgfId=115058">
</A>
c. Calculate and draw (showing coordinates) the placement that minimizes the quadratic cost function <SPAN CLASS="EquationVariables">
f</SPAN>
<SUB CLASS="SubscriptVariable">
Q</SUB>
, </LI>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=115061">
</A>
<SPAN CLASS="Vector">
</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=115063">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=115065">
</A>
1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=115067">
</A>
<SPAN CLASS="EquationVariables">
n</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=115069">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=115071">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=115073">
</A>
</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=115075">
</A>
<SPAN CLASS="EquationVariables">
f</SPAN>
<SUB CLASS="SubscriptVariable">
Q</SUB>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=115077">
</A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=115079">
</A>
––</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=115081">
</A>
<SPAN CLASS="BigMath">
S</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=115083">
</A>
<SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="SubscriptVariable">
ij</SUB>
<SPAN CLASS="EquationVariables">
d</SPAN>
<SUB CLASS="SubscriptVariable">
ij</SUB>
<SUP CLASS="Superscript">
2</SUP>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=115085">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=115087">
</A>
(16.24)</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=115089">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=115091">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=115093">
</A>
2</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=115095">
</A>
<SPAN CLASS="EquationVariables">
j</SPAN>
= 1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=115097">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=115099">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=115101">
</A>
</P>
</TD>
</TR>
</TABLE>
</UL>
<P CLASS="ExerciseHead">
<A NAME="pgfId=115006">
</A>
16.13 <A NAME="19423">
</A>
(Placement interconnect lengths, 45 min.) <A HREF="CH16.2.htm#35878" CLASS="XRef">
Figure 16.30</A>
(d) shows the actual routing corresponding to a placement with an estimated routing length of 8 units (<A HREF="CH16.2.htm#35878" CLASS="XRef">
Figure 16.30</A>
b).</P>
<UL>
<LI CLASS="ExercisePartFirst">
<A NAME="pgfId=27029">
</A>
a. Draw the layout (with routing) corresponding to the placement of <A HREF="CH16.2.htm#35878" CLASS="XRef">
Figure 16.30</A>
(c), which has a lower estimated total routing length of 7 units.</LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=27032">
</A>
b. Compare the actual total routing length for both layouts and explain why they are different from the estimated lengths and describe the sources of the errors.</LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=44455">
</A>
c. Consider flipping both logic cells A and B about the <SPAN CLASS="Emphasis">
y</SPAN>
-axis in the layout shown in <A HREF="CH16.2.htm#35878" CLASS="XRef">
Figure 16.30</A>
(d). How much does this shorten the total interconnect length? Some placement algorithms consider such moves.</LI>
</UL>
<P CLASS="ExerciseHead">
<A NAME="pgfId=28386">
</A>
16.14 <A NAME="12002">
</A>
(Zero-slack algorithm, 60 min.) For the circuit of <A HREF="CH16.6.htm#30308" CLASS="XRef">
Figure 16.35</A>
:</P>
<UL>
<LI CLASS="ExercisePartFirst">
<A NAME="pgfId=28426">
</A>
a. Find all of the arrival, required, and slack times (all delays are in nanoseconds).</LI>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=28394">
</A>
<IMG SRC="CH16-36.gif" ALIGN="BASELINE">
</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigureTitle">
<A NAME="pgfId=28400">
</A>
FIGURE 16.35 <A NAME="30308">
</A>
A circuit to illustrate the zero-slack algorithm (Problem <A HREF="CH16.6.htm#12002" CLASS="XRef">
16.14</A>
).</P>
</TD>
</TR>
</TABLE>
<LI CLASS="ExercisePart">
<A NAME="pgfId=28427">
</A>
b. What is the critical path?</LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=28435">
</A>
c. If the gate delay of A2 is increased to 5 ns, what is the new critical path?</LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=28453">
</A>
d. ** Using your answer to part a find the upper bounds on net delays by means of the zero-slack algorithm as follows:</LI>
<P CLASS="ExerciseList">
<A NAME="pgfId=28454">
</A>
i. Find arrival, required, and slack times on all nets.</P>
<P CLASS="ExerciseList">
<A NAME="pgfId=28469">
</A>
ii. Find an input pin <SPAN CLASS="EquationVariables">
p</SPAN>
with the least nonzero slack <SPAN CLASS="EquationVariables">
S</SPAN>
<SUB CLASS="SubscriptVariable">
p</SUB>
on a net which has not already been selected. If there are none go to step 6.</P>
<P CLASS="ExerciseList">
<A NAME="pgfId=28455">
</A>
ii. Find the path through <SPAN CLASS="EquationVariables">
p</SPAN>
(may include several gates) on which all pins have slack <SPAN CLASS="EquationVariables">
S</SPAN>
<SUB CLASS="SubscriptVariable">
p</SUB>
.</P>
<P CLASS="ExerciseList">
<A NAME="pgfId=28465">
</A>
iv. Distribute a delay equal to the slack <SPAN CLASS="EquationVariables">
S</SPAN>
<SUB CLASS="SubscriptVariable">
p</SUB>
along the path assigning a fraction to each net at the output pins of the gates on the path.</P>
<P CLASS="ExerciseList">
<A NAME="pgfId=28468">
</A>
v. Work backward from <SPAN CLASS="EquationVariables">
p</SPAN>
updating all the required times as necessary and forward from <SPAN CLASS="EquationVariables">
p</SPAN>
updating all the arrival times.</P>
<P CLASS="ExerciseList">
<A NAME="pgfId=28483">
</A>
vi. Convert net delays to net lengths.</P>
</UL>
<P CLASS="ExerciseNoIndent">
<A NAME="pgfId=28484">
</A>
<SPAN CLASS="Emphasis">
Hint: </SPAN>
You can consult the original description of the zero-slack algorithm if this is not clear [<A NAME="Hauge87">
</A>
Hauge et al., 1987].</P>
<P CLASS="ExerciseHead">
<A NAME="pgfId=57501">
</A>
16.15 <A NAME="20243">
</A>
(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 whos⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -