ch16.6.htm

介绍asci设计的一本书

</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=45530">
 </A>
5.45</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=45532">
 </A>
6.44</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=45534">
 </A>
7.44</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=45536">
 </A>
8.44</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=45538">
 </A>
9.43</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=45540">
 </A>
17.4</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=45542">
 </A>
33.33</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=45544">
 </A>
65.20</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=45546">
 </A>
0.996</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=83063">
 </A>
	1.465</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLast">
<A NAME="pgfId=45550">
 </A>
12 <SPAN CLASS="Symbol">
&#165;</SPAN>
 12</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLast">
<A NAME="pgfId=45552">
 </A>
3.04</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLast">
<A NAME="pgfId=45554">
 </A>
4.1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLast">
<A NAME="pgfId=45556">
 </A>
5.17</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLast">
<A NAME="pgfId=45558">
 </A>
6.23</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLast">
<A NAME="pgfId=45560">
 </A>
7.3</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLast">
<A NAME="pgfId=45562">
 </A>
8.35</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLast">
<A NAME="pgfId=45564">
 </A>
9.42</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLast">
<A NAME="pgfId=45566">
 </A>
10.48</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLast">
<A NAME="pgfId=45568">
 </A>
18.8</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLast">
<A NAME="pgfId=45570">
 </A>
36.03</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLast">
<A NAME="pgfId=45572">
 </A>
70.00</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLast">
<A NAME="pgfId=45574">
 </A>
1.063</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=45576">
 </A>
	1.964</P>
</TD>
</TR>
</TABLE>
</UL>
<P CLASS="ExerciseHead">
<A NAME="pgfId=18652">
 </A>
16.2&nbsp;<A NAME="26895">
 </A>
(Trees, 20 min.) For the network graph shown in <A HREF="CH16.6.htm#22857" CLASS="XRef">
Figure&nbsp;16.32</A>
(f), draw the following trees and calculate their Manhattan lengths:</P>
<UL>
<LI CLASS="ExercisePartFirst">
<A NAME="pgfId=100456">
 </A>
a.&nbsp;The minimum Steiner tree.</LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=100458">
 </A>
b.&nbsp;The <A NAME="marker=100457">
 </A>
<SPAN CLASS="Definition">
chain connection</SPAN>
.</LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=100459">
 </A>
c.&nbsp;The minimum rectilinear Steiner tree.</LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=18643">
 </A>
d.&nbsp;The <SPAN CLASS="Definition">
minimum rectilinear spanning tree</SPAN>
<A NAME="marker=32077">
 </A>
 [<A NAME="Hwang76">
 </A>
Hwang, 1976].</LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=44220">
 </A>
e.&nbsp;The minimum single-trunk rectilinear Steiner tree (with a horizontal or vertical trunk).</LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=18646">
 </A>
f.&nbsp;The <SPAN CLASS="Definition">
minimum rectilinear chain connection</SPAN>
<A NAME="marker=32078">
 </A>
 (easy to compute).</LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=18647">
 </A>
g.&nbsp;The <SPAN CLASS="Definition">
minimum source-to-sink connection</SPAN>
<A NAME="marker=32079">
 </A>
.</LI>
</UL>
<P CLASS="Exercise">
<A NAME="pgfId=32043">
 </A>
	Calculate:</P>
<UL>
<LI CLASS="ExercisePart">
<A NAME="pgfId=18648">
 </A>
h.&nbsp;The complete-graph measure and the half-perimeter measure.</LI>
</UL>
<P CLASS="Exercise">
<A NAME="pgfId=36096">
 </A>
<A HREF="CH16.6.htm#22857" CLASS="XRef">
Figure&nbsp;16.32</A>
 parts (a&#8211;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.</P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=44237">
 </A>
&nbsp;</P>
<DIV>
<IMG SRC="CH16-33.gif">
</DIV>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigureTitle">
<A NAME="pgfId=44241">
 </A>
FIGURE&nbsp;16.32&nbsp;<A NAME="22857">
 </A>
 Tree routing. (a)&nbsp;The minimum rectilinear Steiner tree (MRST). (b)&nbsp;The minimum rectilinear spanning tree. (c)&nbsp;The minimum single-trunk rectilinear Steiner tree (1-MRST). (d)&nbsp;The minimum rectilinear chain connection. (e)&nbsp;The minimum source-to-sink connection. (f)&nbsp;Example net for Problem <A HREF="CH16.6.htm#26895" CLASS="XRef">
16.2</A>
.</P>
</TD>
</TR>
</TABLE>
<P CLASS="ExerciseHead">
<A NAME="pgfId=25673">
 </A>
16.3&nbsp;<A NAME="29983">
 </A>
(Eigenvalue placement constraints, 10 min. [<A NAME="Cheng84b">
 </A>
Cheng and Kuh, 1984]) Consider the one-dimensional placement problem with a vector list of valid positions for the logic cells <SPAN CLASS="Vector">
p</SPAN>
  = [<SPAN CLASS="EquationVariables">
 p</SPAN>
<SUB CLASS="SubscriptVariable">
i </SUB>
] and a vector list of <SPAN CLASS="Emphasis">
x</SPAN>
-coordinates for the logic cells <SPAN CLASS="Vector">
x</SPAN>
 = [<SPAN CLASS="EquationVariables">
x</SPAN>
<SUB CLASS="SubscriptVariable">
i</SUB>
]. </P>
<P CLASS="Exercise">
<A NAME="pgfId=94911">
 </A>
Show that for a valid placement <SPAN CLASS="Vector">
x</SPAN>
 (where the vector elements <SPAN CLASS="EquationVariables">
x</SPAN>
<SUB CLASS="SubscriptVariable">
i</SUB>
 are some permutation of the vector elements <SPAN CLASS="EquationVariables">
p</SPAN>
<SUB CLASS="SubscriptVariable">
i</SUB>
), the following equations hold:  </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=112911">
 </A>
<SUB CLASS="SubscriptVariable">
n</SUB>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113036">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=112913">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=113096">
 </A>
<SUB CLASS="SubscriptVariable">
n</SUB>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113076">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=112917">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=112919">
 </A>
&nbsp;</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=112957">
 </A>
<SPAN CLASS="BigMath">
S</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113038">
 </A>
<SPAN CLASS="EquationVariables">
x</SPAN>
<SUB CLASS="SubscriptVariable">
i</SUB>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=112959">
 </A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=113098">
 </A>
<SPAN CLASS="BigMath">
S</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113078">
 </A>
<SPAN CLASS="EquationVariables">
p</SPAN>
<SUB CLASS="SubscriptVariable">
i</SUB>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=112963">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=112965">
 </A>
&nbsp;</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=112967">
 </A>
<SPAN CLASS="EquationVariables">
i</SPAN>
 = 1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113040">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=112969">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=113100">
 </A>
<SPAN CLASS="EquationVariables">
i</SPAN>
 = 1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113080">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=112973">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=112975">
 </A>
&nbsp;</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=113106">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113108">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=113110">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=113112">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113114">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113116">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=113118">
 </A>
&nbsp;</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=113226">
 </A>
<SUB CLASS="SubscriptVariable">
n</SUB>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113228">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=113230">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=113232">
 </A>
<SUB CLASS="SubscriptVariable">
n</SUB>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113234">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113134">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=113136">
 </A>
&nbsp;</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=113236">
 </A>
<SPAN CLASS="BigMath">
S</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113238">
 </A>
<SPAN CLASS="EquationVariables">
x</SPAN>
<SUB CLASS="SubscriptVariable">
i</SUB>
<SUP CLASS="Superscript">
2</SUP>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=113240">
 </A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=113242">
 </A>
<SPAN CLASS="BigMath">
S</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113244">
 </A>
<SPAN CLASS="EquationVariables">
p</SPAN>
<SUB CLASS="SubscriptVariable">
i</SUB>
<SUP CLASS="Superscript">
2</SUP>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=113155">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=113157">
 </A>
&nbsp;</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">