ch16.2.htm

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

<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110777">
 </A>
<SPAN CLASS="EquationVariables">
i</SPAN>
 = 1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110779">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=110781">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=110783">
 </A>
&nbsp;</P>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=8716">
 </A>
We can simplify the problem by noticing that it is symmetric in the <SPAN CLASS="Emphasis">
x</SPAN>
- and <SPAN CLASS="Emphasis">
y</SPAN>
-coordinates. Let us solve the simpler problem of minimizing the cost function for the placement of logic cells along just the <SPAN CLASS="Emphasis">
x</SPAN>
-axis first. We can then apply this solution to the more general two-dimensional placement problem. Before we solve this simpler problem, we introduce a constraint that the coordinates of the logic cells must correspond to valid positions (the cells do not overlap and they are placed on-grid). We make another simplifying assumption that all logic cells are the same size and we must place them in fixed positions. We can define a vector <SPAN CLASS="Vector">
p</SPAN>
 consisting of the valid positions:  </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=110870">
 </A>
<SPAN CLASS="Vector">
p</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110872">
 </A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=110874">
 </A>
[<SPAN CLASS="EquationVariables">
p</SPAN>
<SUB CLASS="Subscript">
1</SUB>
, ..., <SPAN CLASS="EquationVariables">
p</SPAN>
<SUB CLASS="SubscriptVariable">
n</SUB>
] .</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=110876">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=110878">
 </A>
(16.9)</P>
</TD>
</TR>
</TABLE>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=8774">
 </A>
For a valid placement the <SPAN CLASS="Emphasis">
x</SPAN>
-coordinates of the logic cells,  </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=110908">
 </A>
<SPAN CLASS="Vector">
x</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110910">
 </A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=110912">
 </A>
[<SPAN CLASS="EquationVariables">
x</SPAN>
<SUB CLASS="Subscript">
1</SUB>
, ..., <SPAN CLASS="EquationVariables">
x</SPAN>
<SUB CLASS="SubscriptVariable">
n</SUB>
] .</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=110914">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=110916">
 </A>
(16.10)</P>
</TD>
</TR>
</TABLE>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=8779">
 </A>
must be a permutation of the fixed positions, <SPAN CLASS="Vector">
p</SPAN>
. We can show that requiring the logic cells to be in fixed positions in this way leads to a series of <SPAN CLASS="EquationVariables">
n</SPAN>
 equations restricting the values of the logic cell coordinates [<A NAME="Cheng84a">
 </A>
Cheng and Kuh, 1984]. If we impose all of these constraint equations the problem becomes very complex. Instead we choose just one of the equations:  </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111076">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111078">
 </A>
<SPAN CLASS="EquationVariables">
n</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111080">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111082">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111084">
 </A>
<SPAN CLASS="EquationVariables">
n</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111086">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=111088">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=111090">
 </A>
&nbsp;</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111092">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111094">
 </A>
<SPAN CLASS="BigMath">
S</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=111096">
 </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=111098">
 </A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111100">
 </A>
<SPAN CLASS="BigMath">
S</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=111102">
 </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=111104">
 </A>
.</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=111106">
 </A>
<A NAME="42315">
 </A>
(16.11)</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111108">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111110">
 </A>
<SPAN CLASS="EquationVariables">
i</SPAN>
 = 1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111112">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111114">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111116">
 </A>
<SPAN CLASS="EquationVariables">
i</SPAN>
 = 1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111118">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=111120">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=111122">
 </A>
&nbsp;</P>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=8721">
 </A>
Simplifying the problem in this way will lead to an approximate solution to the placement problem. We can write this single constraint on the <SPAN CLASS="Emphasis">
x</SPAN>
-coordinates in matrix form:  </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111633">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111635">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111637">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111639">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111641">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111643">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111645">
 </A>
<SPAN CLASS="EquationVariables">
n</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111647">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=111649">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=111651">
 </A>
&nbsp;</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111653">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=111655">
 </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=111657">
 </A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=111659">
 </A>
P ;&nbsp;&nbsp;&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=111661">
 </A>
<SPAN CLASS="EquationNumber">
P</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111663">
 </A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111665">
 </A>
<SPAN CLASS="BigMath">
S</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=111667">
 </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=111669">
 </A>
.</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=111671">
 </A>
(16.12)</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111673">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111675">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111677">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=111679">
 </A>
&nbsp;</P>