📄 ch15.7.htm
字号:
<A NAME="pgfId=204798">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204800">
</A>
<SPAN CLASS="EquationVariables">
n</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=204802">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204804">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=204806">
</A>
</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=204827">
</A>
G<SUB CLASS="SubscriptVariable">
n</SUB>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204829">
</A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204831">
</A>
<SPAN CLASS="BigMath">
S</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=204833">
</A>
<SPAN CLASS="EquationVariables">
g</SPAN>
<SUB CLASS="SubscriptVariable">
i</SUB>
.</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204835">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=204837">
</A>
(15.19)</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=204808">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204810">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204812">
</A>
<SPAN CLASS="EquationVariables">
i</SPAN>
= 1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=204814">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204816">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=204818">
</A>
</P>
</TD>
</TR>
</TABLE>
<LI CLASS="NumberList">
<A NAME="pgfId=24825">
</A>
We now choose n corresponding to the maximum value of <SPAN CLASS="EquationVariables">
G</SPAN>
<SUB CLASS="SubscriptVariable">
n</SUB>
. </LI>
</OL>
<P CLASS="Body">
<A NAME="pgfId=188604">
</A>
If the maximum value of <SPAN CLASS="EquationVariables">
G</SPAN>
<SUB CLASS="SubscriptVariable">
n</SUB>
> 0, then we swap the sets of nodes X and Y and thus reduce the cut weight by <SPAN CLASS="EquationVariables">
G</SPAN>
<SUB CLASS="SubscriptVariable">
n</SUB>
. We use this new partitioning to start the process again at the first step. If the maximum value of <SPAN CLASS="EquationVariables">
G</SPAN>
<SUB CLASS="SubscriptVariable">
n</SUB>
= 0, then we cannot improve the current partitioning and we stop. We have found a locally optimum solution.</P>
<P CLASS="Body">
<A NAME="pgfId=188617">
</A>
<A HREF="CH15.7.htm#21127" CLASS="XRef">
Figure 15.9</A>
shows an example of partitioning a graph using the K–L algorithm. Each completion of steps 1 through 5 is a pass through the algorithm. Kernighan and Lin found that typically 2–4 passes were required to reach a solution. The most important feature of the K–L algorithm is that we are prepared to consider moves even though they seem to make things worse. This is like unraveling a tangled ball of string or solving a Rubik’s cube puzzle. Sometimes you need to make things worse so they can get better later. The K–L algorithm works well for partitioning graphs. However, there are the following problems that we need to address before we can apply the algorithm to network partitioning:</P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=188613">
</A>
</P>
<DIV>
<IMG SRC="CH15-14.gif">
</DIV>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigureTitle">
<A NAME="pgfId=188616">
</A>
FIGURE 15.9 <A NAME="21127">
</A>
Partitioning a graph using the Kernighan–Lin algorithm. (a) Shows how swapping node 1 of partition A with node 6 of partition B results in a gain of g = 1. (b) A graph of the gain resulting from swapping pairs of nodes. (c) The total gain is equal to the sum of the gains obtained at each step.</P>
</TD>
</TR>
</TABLE>
<UL>
<LI CLASS="BulletFirst">
<A NAME="pgfId=3790">
</A>
It minimizes the number of <SPAN CLASS="Emphasis">
edges</SPAN>
cut, not the number of <SPAN CLASS="Emphasis">
nets</SPAN>
cut.</LI>
<LI CLASS="BulletList">
<A NAME="pgfId=3793">
</A>
It does not allow logic cells to be different sizes. </LI>
<LI CLASS="BulletList">
<A NAME="pgfId=2255">
</A>
It is expensive in computation time.</LI>
<LI CLASS="BulletList">
<A NAME="pgfId=2257">
</A>
It does not allow partitions to be unequal or find the optimum partition size.</LI>
<LI CLASS="BulletList">
<A NAME="pgfId=2259">
</A>
It does not allow for selected logic cells to be fixed in place.</LI>
<LI CLASS="BulletList">
<A NAME="pgfId=2261">
</A>
The results are random.</LI>
<LI CLASS="BulletLast">
<A NAME="pgfId=2263">
</A>
It does not directly allow for more than two partitions.</LI>
</UL>
<P CLASS="Body">
<A NAME="pgfId=2267">
</A>
To implement a <A NAME="marker=2271">
</A>
net-cut partitioning rather than an <A NAME="marker=2274">
</A>
edge-cut partitioning, we can just keep track of the nets rather than the edges [<A NAME="Schweikert79">
</A>
Schweikert and Kernighan, 1979]. We can no longer use a connectivity or cost matrix to represent connections, though. Fortunately, several people have found efficient data structures to handle the bookkeeping tasks. One example is the Fiduccia–Mattheyses algorithm to be described shortly.</P>
<P CLASS="Body">
<A NAME="pgfId=2285">
</A>
To represent nets with multiple terminals in a network accurately, we can extend the definition of a network graph. <A HREF="CH15.7.htm#40950" CLASS="XRef">
Figure 15.10</A>
shows how a <A NAME="marker=2279">
</A>
hypergraph with a special type of vertex, a <A NAME="marker=2282">
</A>
star, and a <A NAME="marker=2284">
</A>
hyperedge, represents a net with more than two terminals in a network. </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=3466">
</A>
</P>
<DIV>
<IMG SRC="CH15-15.gif">
</DIV>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigureTitle">
<A NAME="pgfId=3468">
</A>
FIGURE 15.10 <A NAME="40950">
</A>
A hypergraph. (a) The network contains a net y with three terminals. (b) In the network hypergraph we can model net y by a single hyperedge (B, C, D) and a star node. Now there is a direct correspondence between wires or nets in the network and hyperedges in the graph.</P>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=3951">
</A>
In the K–L algorithm, the internal and external edge costs have to be calculated for all the nodes before we can select the nodes to be swapped. Then we have to find the pair of nodes that give the largest gain when swapped. This requires an amount of computer time that grows as <SPAN CLASS="EquationVariables">
n</SPAN>
<SUP CLASS="Superscript">
2</SUP>
log <SPAN CLASS="EquationVariables">
n</SPAN>
for a graph with 2n nodes. This <SPAN CLASS="EquationVariables">
n</SPAN>
<SUP CLASS="Superscript">
2</SUP>
dependency is a major problem for partitioning large networks. The <A NAME="marker=3955">
</A>
Fiduccia–Mattheyses algorithm (the <A NAME="marker=3956">
</A>
F–M algorithm) is an extension to the K–L algorithm that addresses the differences between nets and edges and also reduces the computational effort [<A NAME="Fiduccia82">
</A>
Fiduccia and Mattheyses, 1982]. The key features of this algorithm are the following:</P>
<UL>
<LI CLASS="BulletFirst">
<A NAME="pgfId=2307">
</A>
Only one logic cell, the <A NAME="marker=2303">
</A>
base logic cell, moves at a time. In order to stop the algorithm from moving all the logic cells to one large partition, the base logic cell is chosen to maintain <A NAME="marker=2306">
</A>
balance between partitions. The balance is the ratio of total logic cell size in one partition to the total logic cell size in the other. Altering the balance allows us to vary the sizes of the partitions.</LI>
<LI CLASS="BulletList">
<A NAME="pgfId=2313">
</A>
Critical nets are used to simplify the gain calculations. A net is a <A NAME="marker=2311">
</A>
critical net if it has an attached logic cell that, when swapped, changes the number of nets cut. It is only necessary to recalculate the gains of logic cells on critical nets that are attached to the base logic cell. </LI>
<LI CLASS="BulletLast">
<A NAME="pgfId=2317">
</A>
The logic cells that are free to move are stored in a doubly linked list. The lists are sorted according to gain. This allows the logic cells with maximum gain to be found quickly.</LI>
</UL>
<P CLASS="Body">
<A NAME="pgfId=183010">
</A>
These techniques reduce the computation time so that it increases only slightly more than linearly with the number of logic cells in the network, a very important improvement [Fiduccia and Mattheyses, 1982].</P>
<P CLASS="Body">
<A NAME="pgfId=183012">
</A>
Kernighan and Lin suggested simulating logic cells of different sizes by clumping <SPAN CLASS="EquationVariables">
s</SPAN>
logic cells together with highly weighted nets to simulate a logic cell of size <SPAN CLASS="EquationVariables">
s</SPAN>
. The F–M algorithm takes logic-cell size into account as it selects a logic cell to swap based on maintaining the balance between the total logic-cell size of each of the partitions. To generate unequal partitions using the K–L algorithm, we can introduce dummy logic cells with no connections into one of the partitions. The F–M algorithm adjusts the partition size according to the balance parameter.</P>
<P CLASS="Body">
<A NAME="pgfId=2329">
</A>
Often we need to fix logic cells in place during partitioning. This may be because we need to keep logic cells together or apart for reasons other than connectivity, perhaps due to timing, power, or noise constraints. Another reason to fix logic cells would be to improve a partitioning that you have already partially completed. The F–M algorithm allows you to fix logic cells by removing them from consideration as the base logic cells you move. Methods based on the K–L algorithm find locally optimum solutions in a random fashion. There are two reasons for this. The first reason is the random starting partition. The second reason is that the choice of nodes to swap is based on the gain. The choice between moves that have equal gain is arbitrary. Extensions to the K–L algorithm address both of these problems. Finding nodes that are naturally grouped or clustered and assigning them to one of the initial partitions improves the results of the K–L algorithm. Although these are constructive partitioning methods, they are covered here because they are closely linked with the K–L iterative improvement algorithm. </P>
</DIV>
<DIV>
<H2 CLASS="Heading2">
<A NAME="pgfId=11437">
</A>
15.7.6 The Ratio-Cut Algorithm</H2>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=2343">
</A>
The <A NAME="marker=2341">
</A>
ratio-cut algorithm removes the restriction of constant partition sizes. The cut weight <SPAN CLASS="EquationVariables">
W</SPAN>
for a cut that divides a network into two partitions, <SPAN CLASS="EquationVariables">
A</SPAN>
and <SPAN CLASS="EquationVariables">
B</SPAN>
, is given by </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=204893">
</A>
W</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204895">
</A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204897">
</A>
<SPAN CLASS="BigMath">
S</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=204899">
</A>
<SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="SubscriptVariable">
ab</SUB>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204901">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=204903">
</A>
</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -