ch16.2.htm

来自「介绍asci设计的一本书」· HTM 代码 · 共 2,471 行 · 第 1/5 页

</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111681">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111683">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111685">
 </A>
<SPAN CLASS="EquationVariables">
i</SPAN>
 = 1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111687">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=111689">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=111691">
 </A>
&nbsp;</P>
</TD>
</TR>
</TABLE>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=11715">
 </A>
where <SPAN CLASS="EquationNumber">
P</SPAN>
 is a constant. We can now summarize the formulation of the problem, with the simplifications that we have made, for a one-dimensional solution. We must minimize a cost function, <SPAN CLASS="EquationVariables">
g</SPAN>
 (analogous to the cost function <SPAN CLASS="EquationVariables">
f</SPAN>
 that we defined for the two-dimensional problem in Eq. <A HREF="CH16.2.htm#33941" CLASS="XRef">
16.7</A>
), where  </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=111695">
 </A>
<SPAN CLASS="EquationVariables">
g</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111697">
 </A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=111699">
 </A>
<SPAN CLASS="Vector">
x</SPAN>
<SUP CLASS="Superscript">
T</SUP>
<SPAN CLASS="Vector">
Bx</SPAN>
 .</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=111701">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=111703">
 </A>
(16.13)</P>
</TD>
</TR>
</TABLE>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=8224">
 </A>
subject to the constraint:  </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=111710">
 </A>
<SPAN CLASS="Vector">
x</SPAN>
<SUP CLASS="Superscript">
T</SUP>
<SPAN CLASS="Vector">
x</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111712">
 </A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=111714">
 </A>
P .</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=111716">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=111718">
 </A>
(16.14)</P>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=8229">
 </A>
This is a standard problem that we can solve using a <A NAME="marker=27956">
 </A>
Lagrangian multiplier:  </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=111725">
 </A>
<SPAN CLASS="Symbol">
L</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111727">
 </A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=111729">
 </A>
<SPAN CLASS="Vector">
x</SPAN>
<SUP CLASS="Superscript">
T</SUP>
<SPAN CLASS="Vector">
Bx</SPAN>
 &#8211; <SPAN CLASS="Symbol">
l</SPAN>
[<SPAN CLASS="Vector">
x</SPAN>
<SUP CLASS="Superscript">
T</SUP>
<SPAN CLASS="Vector">
x</SPAN>
 &#8211; P] .</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=111731">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=111733">
 </A>
(16.15)</P>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=8234">
 </A>
To find the value of <SPAN CLASS="Vector">
x</SPAN>
 that minimizes <SPAN CLASS="EquationVariables">
g</SPAN>
 we differentiate L partially with respect to <SPAN CLASS="Vector">
x</SPAN>
 and set the result equal to zero. We get the following equation:  </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=111768">
 </A>
[<SPAN CLASS="Vector">
B</SPAN>
 &#8211; <SPAN CLASS="Symbol">
l</SPAN>
<SPAN CLASS="Vector">
I</SPAN>
]<SPAN CLASS="Vector">
x</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111770">
 </A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=111772">
 </A>
<SPAN CLASS="Vector">
0</SPAN>
 .</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=111774">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=111776">
 </A>
<A NAME="16612">
 </A>
(16.16)</P>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=8240">
 </A>
This last equation is called the <A NAME="marker=1924">
 </A>
<SPAN CLASS="Definition">
characteristic equation</SPAN>
 for the disconnection matrix <SPAN CLASS="Vector">
B</SPAN>
 and occurs frequently in matrix algebra (this l has nothing to do with scaling). The solutions to this equation are the <A NAME="marker=1927">
 </A>
<SPAN CLASS="Definition">
eigenvectors</SPAN>
 and <A NAME="marker=1929">
 </A>
<SPAN CLASS="Definition">
eigenvalues</SPAN>
 of <SPAN CLASS="Vector">
B</SPAN>
. Multiplying Eq.&nbsp;<A HREF="CH16.2.htm#16612" CLASS="XRef">
16.16</A>
 by <SPAN CLASS="Vector">
x</SPAN>
<SUP CLASS="Superscript">
T</SUP>
 we get:  </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=111800">
 </A>
<SPAN CLASS="Symbol">
l</SPAN>
<SPAN CLASS="Vector">
 x</SPAN>
<SUP CLASS="Superscript">
T</SUP>
<SPAN CLASS="Vector">
x</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111802">
 </A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=111804">
 </A>
<SPAN CLASS="Vector">
x</SPAN>
<SUP CLASS="Superscript">
T</SUP>
<SPAN CLASS="Vector">
Bx</SPAN>
 .</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=111806">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=111808">
 </A>
(16.17)</P>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=8245">
 </A>
However, since we imposed the constraint <SPAN CLASS="Vector">
x</SPAN>
<SPAN CLASS="EquationVariables">
T</SPAN>
<SPAN CLASS="Vector">
x</SPAN>
  = <SPAN CLASS="EquationNumber">
P</SPAN>
 and <SPAN CLASS="Vector">
x</SPAN>
<SUP CLASS="Superscript">
T</SUP>
<SPAN CLASS="Vector">
Bx</SPAN>
  = <SPAN CLASS="EquationVariables">
g</SPAN>
, then  </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=111827">
 </A>
<SPAN CLASS="Symbol">
l</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111829">
 </A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=111831">
 </A>
<SPAN CLASS="EquationVariables">
g</SPAN>
/P .</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=111833">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=111835">
 </A>
(16.18)</P>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=8253">
 </A>
The eigenvectors of the disconnection matrix <SPAN CLASS="Vector">
B</SPAN>
 are the solutions to our placement problem. It turns out that (because something called the <A NAME="marker=27957">
 </A>
rank of matrix <SPAN CLASS="Vector">
B</SPAN>
 is <SPAN CLASS="EquationVariables">
n</SPAN>
 &#8211; 1) there is a degenerate solution with all <SPAN CLASS="Emphasis">
x</SPAN>
-coordinates equal (<SPAN CLASS="Symbol">
l</SPAN>
 = 0)&#8212;this makes some sense because putting all the logic cells on top of one another certainly minimizes the interconnect. The smallest, nonzero, eigenvalue and the corresponding eigenvector provides the solution that we want. In the two-dimensional placement problem, the <SPAN CLASS="Emphasis">
x</SPAN>
- and <SPAN CLASS="Emphasis">
y</SPAN>
-coordinates are given by the eigenvectors corresponding to the two smallest, nonzero, eigenvalues. (In the next section a simple example illustrates this mathematical derivation.)</P>
</DIV>
<DIV>
<H2 CLASS="Heading2">
<A NAME="pgfId=25676">
 </A>
16.2.5&nbsp;<A NAME="30717">
 </A>
Eigenvalue Placement Example</H2>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=25679">
 </A>
Consider the following connectivity matrix <SPAN CLASS="Vector">
C</SPAN>
 and its disconnection matrix <SPAN CLASS="Vector">
B</SPAN>
, calculated from Eq. <A HREF="CH16.2.htm#41073" CLASS="XRef">
16.8</A>
 [<A NAME="Hall70">
 </A>
Hall, 1970]:  </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=112212">
 </A>
<SPAN CLASS="Symbol">
</SPAN>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=112214">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=112216">
 </A>
0 0 0 1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=112218">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=112220">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=112222">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=112224">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=112226">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=112228">
 </A>
&nbsp;</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=112230">
 </A>
<SPAN CLASS="Vector">
C</SPAN>
</P>
</T