ch16.2.htm
来自「介绍asci设计的一本书」· HTM 代码 · 共 2,471 行 · 第 1/5 页
HTM
2,471 行
= [<SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="SubscriptVariable">
ij</SUB>
] is the (possibly weighted) connectivity matrix, and <SPAN CLASS="EquationVariables">
d</SPAN>
<SUB CLASS="SubscriptVariable">
ij</SUB>
is the Euclidean distance between the centers of logic cell <SPAN CLASS="EquationVariables">
i</SPAN>
and logic cell <SPAN CLASS="EquationVariables">
j</SPAN>
. Since we are going to minimize a cost function that is the square of the distance between logic cells, these methods are also known as <SPAN CLASS="Definition">
quadratic placement</SPAN>
<A NAME="marker=24684">
</A>
methods. This type of cost function leads to a simple mathematical solution. We can rewrite the cost function <SPAN CLASS="EquationVariables">
f</SPAN>
in matrix form: </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=110280">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110282">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110284">
</A>
1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110286">
</A>
<SPAN CLASS="EquationVariables">
n</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110288">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=110290">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=110292">
</A>
</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=110294">
</A>
<SPAN CLASS="EquationVariables">
f</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110296">
</A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110298">
</A>
––</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110300">
</A>
<SPAN CLASS="BigMath">
S</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=110302">
</A>
<SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="SubscriptVariable">
ij</SUB>
(<SPAN CLASS="EquationVariables">
x</SPAN>
<SUB CLASS="SubscriptVariable">
i</SUB>
– <SPAN CLASS="EquationVariables">
x</SPAN>
<SUB CLASS="SubscriptVariable">
j</SUB>
)<SUP CLASS="Superscript">
2</SUP>
+ <SPAN CLASS="EquationVariables">
(y</SPAN>
<SUB CLASS="SubscriptVariable">
i</SUB>
– <SPAN CLASS="EquationVariables">
y</SPAN>
<SUB CLASS="SubscriptVariable">
j</SUB>
)<SUP CLASS="Superscript">
2</SUP>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=110304">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=110306">
</A>
</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=110309">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110311">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110313">
</A>
2</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110315">
</A>
<SPAN CLASS="EquationVariables">
i</SPAN>
= 1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110317">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=110319">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=110321">
</A>
</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=110439">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110441">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110443">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110445">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110447">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=110449">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=110451">
</A>
</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=110457">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110459">
</A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="3">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=110461">
</A>
<SPAN CLASS="Vector">
x</SPAN>
<SUP CLASS="Superscript">
T</SUP>
<SPAN CLASS="Vector">
Bx</SPAN>
+ <SPAN CLASS="Vector">
y</SPAN>
<SUP CLASS="Superscript">
T</SUP>
<SPAN CLASS="Vector">
By</SPAN>
.</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=110467">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=110469">
</A>
<A NAME="33941">
</A>
(16.7)</P>
</TD>
</TR>
</TABLE>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=9148">
</A>
In Eq. <A HREF="CH16.2.htm#33941" CLASS="XRef">
16.7</A>
, <SPAN CLASS="Vector">
B</SPAN>
is a symmetric matrix, the <A NAME="marker=8125">
</A>
<SPAN CLASS="Definition">
disconnection matrix</SPAN>
(also called the <A NAME="marker=52776">
</A>
Laplacian).</P>
<P CLASS="Body">
<A NAME="pgfId=94897">
</A>
We may express the Laplacian <SPAN CLASS="Vector">
B</SPAN>
in terms of the connectivity matrix <SPAN CLASS="Vector">
C</SPAN>
; and <SPAN CLASS="Vector">
D</SPAN>
, a diagonal matrix (known as the <A NAME="marker=52775">
</A>
degree matrix), defined as follows: </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=110724">
</A>
<SPAN CLASS="Vector">
B</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110726">
</A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="2">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=110728">
</A>
<SPAN CLASS="Vector">
D</SPAN>
– <SPAN CLASS="Vector">
C</SPAN>
;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=110733">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=110735">
</A>
<A NAME="41073">
</A>
(16.8)</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=110737">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110739">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110741">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110743">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=110745">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=110747">
</A>
</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=110749">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110751">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110753">
</A>
<SPAN CLASS="EquationVariables">
n</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110755">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=110757">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=110759">
</A>
</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=110761">
</A>
<SPAN CLASS="EquationVariables">
d</SPAN>
<SUB CLASS="SubscriptVariable">
ii</SUB>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110763">
</A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110765">
</A>
<SPAN CLASS="BigMath">
S</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=110767">
</A>
<SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="SubscriptVariable">
ij</SUB>
, <SPAN CLASS="EquationVariables">
i</SPAN>
= 1, ... , <SPAN CLASS="EquationVariables">
ni</SPAN>
; <SPAN CLASS="EquationVariables">
d</SPAN>
<SUB CLASS="SubscriptVariable">
ij</SUB>
= 0, <SPAN CLASS="EquationVariables">
i</SPAN>
<SPAN CLASS="Symbol">
π</SPAN>
<SPAN CLASS="EquationVariables">
j</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=110769">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=110771">
</A>
</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=110773">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110775">
</A>
</P>
</TD>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?