ch15.7.htm

介绍asci设计的一本书

<DIV>
<H2 CLASS="Heading2">
<A NAME="pgfId=3387">
 </A>
15.7.5&nbsp;<A NAME="16811">
 </A>
The Kernighan&#8211;Lin Algorithm</H2>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=10117">
 </A>
<A HREF="CH15.7.htm#35581" CLASS="XRef">
Figure&nbsp;15.8</A>
 illustrates some of the terms and definitions needed to describe the K&#8211;L algorithm. External edges cross between partitions; internal edges are contained inside a partition. Consider a network with 2 <SPAN CLASS="EquationVariables">
m</SPAN>
 nodes (where <SPAN CLASS="EquationVariables">
m</SPAN>
 is an integer) each of equal size. If we assign a cost to each edge of the network graph, we can define a <A NAME="marker=5336">
 </A>
<A NAME="marker=5337">
 </A>
cost matrix C = <SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="SubscriptVariable">
ij</SUB>
, where <SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="SubscriptVariable">
ij</SUB>
 = <SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="SubscriptVariable">
ji</SUB>
 and <SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="SubscriptVariable">
ii</SUB>
 = 0. If all connections are equal in importance, the elements of the cost matrix are 1 or 0, and in this special case we usually call the matrix the <A NAME="marker=13025">
 </A>
connectivity matrix. Costs higher than 1 could represent the number of wires in a bus, multiple connections to a single logic cell, or nets that we need to keep close for timing reasons.</P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=188534">
 </A>
&nbsp;</P>
<DIV>
<IMG SRC="CH15-12.gif">
</DIV>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigureTitle">
<A NAME="pgfId=188537">
 </A>
FIGURE&nbsp;15.8&nbsp;<A NAME="35581">
 </A>
Terms used by the Kernighan&#8211;Lin partitioning algorithm. (a)&nbsp;An example network graph. (b)&nbsp;The connectivity matrix, C; the column and rows are labeled to help you see how the matrix entries correspond to the node numbers in the graph. For example, C <SUB CLASS="Subscript">
17</SUB>
 (column 1, row 7) equals 1 because nodes 1 and 7 are connected. In this example all edges have an equal weight of 1, but in general the edges may have different weights.</P>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=13033">
 </A>
Suppose we already have split a network into two partitions, <SPAN CLASS="EquationVariables">
A</SPAN>
 and <SPAN CLASS="EquationVariables">
B</SPAN>
, each with <SPAN CLASS="EquationVariables">
m</SPAN>
 nodes (perhaps using a constructed partitioning). Our goal now is to swap nodes between <SPAN CLASS="EquationVariables">
A</SPAN>
 and <SPAN CLASS="EquationVariables">
B</SPAN>
 with the objective of minimizing the number of external edges connecting the two partitions. Each external edge may be weighted by a cost, and our objective corresponds to minimizing a cost function that we shall call the total external cost, <A NAME="marker=147318">
 </A>
cut cost, or <A NAME="marker=2118">
 </A>
cut weight, <SPAN CLASS="EquationVariables">
W</SPAN>
:  </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=204240">
 </A>
W</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204242">
 </A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204244">
 </A>
<SPAN CLASS="BigMath">
S</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=204326">
 </A>
<SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="SubscriptVariable">
ab</SUB>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204246">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=204248">
 </A>
(15.13)</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=204250">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204252">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204254">
 </A>
<SPAN CLASS="EquationVariables">
a</SPAN>
 <SPAN CLASS="Symbol">
&#8712;</SPAN>
 <SPAN CLASS="EquationVariables">
A</SPAN>
, <SPAN CLASS="EquationVariables">
b</SPAN>
 <SPAN CLASS="Symbol">
&#8712;</SPAN>
 <SPAN CLASS="EquationVariables">
B</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=204328">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204256">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=204258">
 </A>
&nbsp;</P>
</TD>
</TR>
</TABLE>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=5338">
 </A>
In <A HREF="CH15.7.htm#35581" CLASS="XRef">
Figure&nbsp;15.8</A>
(a) the cut weight is 4 (all the edges have weights of 1).</P>
<P CLASS="Body">
<A NAME="pgfId=13802">
 </A>
In order to simplify the measurement of the change in cut weight when we interchange nodes, we need some more definitions. First, for any node <SPAN CLASS="EquationVariables">
a</SPAN>
 in partition <SPAN CLASS="EquationVariables">
A</SPAN>
, we define an <A NAME="marker=2129">
 </A>
external edge cost, which measures the connections from node <SPAN CLASS="EquationVariables">
a</SPAN>
 to <SPAN CLASS="EquationVariables">
B</SPAN>
,  </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=204574">
 </A>
E<SUB CLASS="SubscriptVariable">
a</SUB>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204576">
 </A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204578">
 </A>
<SPAN CLASS="BigMath">
S</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=204580">
 </A>
<SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="SubscriptVariable">
ay</SUB>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204582">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=204584">
 </A>
&nbsp;</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=204586">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204588">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204590">
 </A>
<SPAN CLASS="EquationVariables">
y</SPAN>
 <SPAN CLASS="Symbol">
&#8712;</SPAN>
 <SPAN CLASS="EquationVariables">
B</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=204592">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204594">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=204596">
 </A>
(15.14)</P>
</TD>
</TR>
</TABLE>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=5346">
 </A>
For example, in <A HREF="CH15.7.htm#35581" CLASS="XRef">
Figure&nbsp;15.8</A>
(a) <SPAN CLASS="EquationVariables">
E</SPAN>
<SUB CLASS="Subscript">
1</SUB>
 = 1, and <SPAN CLASS="EquationVariables">
E</SPAN>
<SUB CLASS="Subscript">
3</SUB>
 = 0. Second, we define the <A NAME="marker=2140">
 </A>
internal edge cost to measure the internal connections to <SPAN CLASS="EquationVariables">
a</SPAN>
,  </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=204624">
 </A>
I<SUB CLASS="SubscriptVariable">
a</SUB>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204626">
 </A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204628">
 </A>
<SPAN CLASS="BigMath">
S</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=204630">
 </A>
<SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="SubscriptVariable">
az</SUB>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204632">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=204634">
 </A>
&nbsp;</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=204636">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204638">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204640">