ch15.9.htm

介绍asci设计的一本书

&nbsp;</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=205583">
 </A>
<SPAN CLASS="Vector">
C</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=205585">
 </A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=205587">
 </A>
0 0 0 1 0 0 0 0 0 0</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=205589">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=205591">
 </A>
(15.26)</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=205593">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=205595">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=205597">
 </A>
0 1 0 0 0 0 0 0 1 0</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=205599">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=205601">
 </A>
&nbsp;</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=205607">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=205609">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=205611">
 </A>
1 0 0 0 0 0 0 0 1 0</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=205613">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=205615">
 </A>
&nbsp;</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=205617">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=205619">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=205621">
 </A>
0 1 1 0 0 0 0 0 1 0</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=205623">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=205625">
 </A>
&nbsp;</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=205631">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=205633">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=205635">
 </A>
0 0 0 1 0 0 1 1 0 1 </P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=205637">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=205639">
 </A>
&nbsp;</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=205641">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=205643">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=205645">
 </A>
0 0 0 0 0 0 0 0 1 0</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=205647">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=205649">
 </A>
&nbsp;</P>
</TD>
</TR>
</TABLE>
<LI CLASS="ExercisePart">
<A NAME="pgfId=16109">
 </A>
b.&nbsp;Draw the partitioned network graph for <SPAN CLASS="Bold">
C</SPAN>
 with nodes 1&#8211;5 in partition A and nodes 6&#8211;10 in partition B. What is the cut weight?</LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=13766">
 </A>
c.&nbsp;Improve the initial partitioning using the K&#8211;L algorithm. Show the gains at each stage. What problems did you find in following the algorithm and how do you resolve them?</LI>
</UL>
<P CLASS="ExerciseHead">
<A NAME="pgfId=17058">
 </A>
15.20&nbsp;(The gain graph in the K&#8211;L algorithm, 20  min.). Continue with the K&#8211;L algorithm for the network that we started to partition in <A HREF="CH15.7.htm#21127" CLASS="XRef">
Figure&nbsp;15.9</A>
(a).</P>
<UL>
<LI CLASS="ExercisePartFirst">
<A NAME="pgfId=96535">
 </A>
a.&nbsp;Show that choices of logic cells to swap and the gains correspond to the graph of <A HREF="CH15.7.htm#21127" CLASS="XRef">
Figure&nbsp;15.9</A>
(b).</LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=193449">
 </A>
b.&nbsp;Notice that <SPAN CLASS="EquationVariables">
G</SPAN>
<SUB CLASS="Subscript">
5</SUB>
 = 0. In fact <SPAN CLASS="EquationVariables">
G</SPAN>
<SUB CLASS="SubscriptVariable">
m</SUB>
 (where there are 2 <SPAN CLASS="EquationVariables">
m</SPAN>
 nodes to be partitioned) will always be zero. Can you explain why?</LI>
</UL>
<P CLASS="ExerciseHead">
<A NAME="pgfId=193452">
 </A>
15.21&nbsp;<A NAME="11854">
 </A>
(Look-ahead gain in the K&#8211;L algorithm, 20  min.)&nbsp;In the K&#8211;L algorithm we have to compute the gain each time we consider swapping one pair of nodes:  </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=205518">
 </A>
<SPAN CLASS="EquationVariables">
g</SPAN>
<SUB CLASS="Subscript">
1</SUB>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=205520">
 </A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=205522">
 </A>
<SPAN CLASS="EquationVariables">
D</SPAN>
<SUB CLASS="SubscriptVariable">
a</SUB>
 + <SPAN CLASS="EquationVariables">
D</SPAN>
<SUB CLASS="SubscriptVariable">
b</SUB>
 &#8211; 2 <SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="SubscriptVariable">
ab</SUB>
 .</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=205524">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=205526">
 </A>
(15.27)</P>
</TD>
</TR>
</TABLE>
<P CLASS="Exercise">
<A NAME="pgfId=16242">
 </A>
If we swap two pairs of nodes (<SPAN CLASS="EquationVariables">
a</SPAN>
<SUB CLASS="SubscriptVariable">
1</SUB>
 and <SPAN CLASS="EquationVariables">
b</SPAN>
<SUB CLASS="SubscriptVariable">
1</SUB>
 followed by <SPAN CLASS="EquationVariables">
a</SPAN>
<SUB CLASS="Subscript">
2</SUB>
 and <SPAN CLASS="EquationVariables">
b</SPAN>
<SUB CLASS="Subscript">
2</SUB>
), show that the gain is  </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=205744">
 </A>
<SPAN CLASS="EquationVariables">
g</SPAN>
<SUB CLASS="Subscript">
1</SUB>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=205746">
 </A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=205748">
 </A>
<SPAN CLASS="EquationVariables">
D</SPAN>
<SUB CLASS="SubscriptVariable">
a</SUB>
<SUB CLASS="Subscript">
2</SUB>
 + <SPAN CLASS="EquationVariables">
D</SPAN>
<SUB CLASS="SubscriptVariable">
b</SUB>
<SUB CLASS="Subscript">
2</SUB>
 &#8211; 2 <SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="SubscriptVariable">
a</SUB>
<SUB CLASS="Subscript">
2</SUB>
<SUB CLASS="SubscriptVariable">
b</SUB>
<SUB CLASS="Subscript">
2</SUB>
 &#8211; 2 <SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="SubscriptVariable">
a</SUB>
<SUB CLASS="Subscript">
2</SUB>
<SUB CLASS="SubscriptVariable">
a</SUB>
<SUB CLASS="Subscript">
1</SUB>
 &#8211; 2 <SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="SubscriptVariable">
a</SUB>
<SUB CLASS="Subscript">
2</SUB>
<SUB CLASS="SubscriptVariable">
b</SUB>
<SUB CLASS="Subscript">
1</SUB>
 &#8211; 2 <SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="SubscriptVariable">
b</SUB>
<SUB CLASS="Subscript">
2</SUB>
<SUB CLASS="SubscriptVariable">
a</SUB>
<SUB CLASS="Subscript">
1</SUB>
 + 2 <SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="SubscriptVariable">
b</SUB>
<SUB CLASS="Subscript">
2</SUB>
<SUB CLASS="SubscriptVariable">
b</SUB>
<SUB CLASS="Subscript">
1</SUB>
 .</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=205750">
 </A>
(15.28)</P>
</TD>
</TR>
</TABLE>
<P CLASS="ExerciseHead">
<A NAME="pgfId=23048">
 </A>
15.22&nbsp;<A NAME="16003">
 </A>
(FPGA partitioning, 30  min.)&nbsp;<A HREF="CH15.9.htm#18648" CLASS="XRef">
Table&nbsp;15.10</A>
 shows some data on FPGAs from company Z.</P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="5">
<P CLASS="TableTitle">
<A NAME="pgfId=23166">
 </A>
TABLE&nbsp;15.10&nbsp;<A NAME="18648">
 </A>
FPGAs from company Z (Problem <A HREF="CH15.9.htm#16003" CLASS="XRef">
15.22</A>
).</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFirst">
<A NAME="pgfId=23175">
 </A>
FPGA size</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFirst">
<A NAME="pgfId=30252">
 </A>
Die area / cm<SUP CLASS="Superscript">
2</SUP>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFirst">
<A NAME="pgfId=23177">
 </A>
Average gate count</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFirst">
<A NAME="pgfId=23179">
 </A>
Package pins</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFirst">
<A NAME="pgfId=23181">
 </A>
Cost</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=23183">
 </A>
S</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=30254">
 </A>
0.26</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=23185">
 </A>
1500</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=23187">
 </A>
68</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=23189">
 </A>
 $26</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=23191">
 </A>
M</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=30256">
 </A>
0.36</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=23193">
 </A>
2300</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=23195">
 </A>