📄 ch15.7.htm
字号:
<A NAME="pgfId=204905">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204907">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204909">
</A>
<SPAN CLASS="EquationVariables">
a</SPAN>
<SPAN CLASS="Symbol">
∈</SPAN>
<SPAN CLASS="EquationVariables">
A</SPAN>
, <SPAN CLASS="EquationVariables">
b</SPAN>
<SPAN CLASS="Symbol">
∈</SPAN>
<SPAN CLASS="EquationVariables">
B</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=204911">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204913">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=204915">
</A>
(15.20)</P>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=5474">
</A>
The K–L algorithm minimizes <SPAN CLASS="EquationVariables">
W</SPAN>
while keeping partitions <SPAN CLASS="EquationVariables">
A</SPAN>
and <SPAN CLASS="EquationVariables">
B</SPAN>
the same size. The <A NAME="marker=2353">
</A>
ratio of a cut is defined as </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=205025">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=205027">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=205029">
</A>
W</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=205031">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=205033">
</A>
</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=205035">
</A>
R</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=205037">
</A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=205039">
</A>
–––––––</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=205041">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=205043">
</A>
(15.21)</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=205045">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=205047">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=205049">
</A>
| <SPAN CLASS="EquationVariables">
A</SPAN>
| | <SPAN CLASS="EquationVariables">
B</SPAN>
|</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=205051">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=205053">
</A>
</P>
</TD>
</TR>
</TABLE>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=5397">
</A>
In this equation |<SPAN CLASS="EquationVariables">
A</SPAN>
| and |<SPAN CLASS="EquationVariables">
B</SPAN>
| are the sizes of partitions <SPAN CLASS="EquationVariables">
A</SPAN>
and <SPAN CLASS="EquationVariables">
B</SPAN>
. The size of a partition is equal to the number of nodes it contains (also known as the <A NAME="marker=2366">
</A>
set cardinality). The cut that minimizes <SPAN CLASS="EquationVariables">
R</SPAN>
is called the <A NAME="marker=2368">
</A>
ratio cut. The original description of the ratio-cut algorithm uses ratio cuts to partition a network into small, highly connected groups. Then you form a reduced network from these groups—each small group of logic cells forms a node in the reduced network. Finally, you use the F–M algorithm to improve the reduced network [<A NAME="Cheng91">
</A>
Cheng and Wei, 1991].</P>
</DIV>
<DIV>
<H2 CLASS="Heading2">
<A NAME="pgfId=11438">
</A>
15.7.7 The Look-ahead Algorithm</H2>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=2373">
</A>
Both the K–L and F–M algorithms consider only the immediate gain to be made by moving a node. When there is a tie between nodes with equal gain (as often happens), there is no mechanism to make the best choice. This is like playing chess looking only one move ahead. <A HREF="CH15.7.htm#35453" CLASS="XRef">
Figure 15.11</A>
shows an example of two nodes that have equal gains, but moving one of the nodes will allow a move that has a higher gain later. </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=195250">
</A>
</P>
<DIV>
<IMG SRC="CH15-16.gif">
</DIV>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigureTitle">
<A NAME="pgfId=195253">
</A>
FIGURE 15.11 <A NAME="35453">
</A>
An example of network partitioning that shows the need to look ahead when selecting logic cells to be moved between partitions. Partitionings (a), (b), and (c) show one sequence of moves, partitionings (d), (e), and (f) show a second sequence. The partitioning in (a) can be improved by moving node 2 from A to B with a gain of 1. The result of this move is shown in (b). This partitioning can be improved by moving node 3 to B, again with a gain of 1. The partitioning shown in (d) is the same as (a). We can move node 5 to B with a gain of 1 as shown in (e), but now we can move node 4 to B with a gain of 2.</P>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=16535">
</A>
We call the gain for the initial move the first-level gain. Gains from subsequent moves are then second-level and higher gains. We can define a <A NAME="marker=16536">
</A>
gain vector that contains these gains. <A HREF="CH15.7.htm#35453" CLASS="XRef">
Figure 15.11</A>
shows how the first-level and second-level gains are calculated. Using the gain vector allows us to use a <A NAME="marker=16540">
</A>
look-ahead algorithm in the choice of nodes to be swapped. This reduces both the mean and variation in the number of cuts in the resulting partitions.</P>
<P CLASS="Body">
<A NAME="pgfId=16550">
</A>
We have described algorithms that are efficient at dividing a network into two pieces. Normally we wish to divide a system into more than two pieces. We can do this by recursively applying the algorithms. For example, if we wish to divide a system network into three pieces, we could apply the F–M algorithm first, using a balance of 2:1, to generate two partitions, with one twice as large as the other. Then we apply the algorithm again to the larger of the two partitions, with a balance of 1:1, which will give us three partitions of roughly the same size.</P>
</DIV>
<DIV>
<H2 CLASS="Heading2">
<A NAME="pgfId=2413">
</A>
15.7.8 <A NAME="36355">
</A>
Simulated Annealing</H2>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=2423">
</A>
A different approach to solving large graph problems (and other types of problems) that arise in VLSI layout, including system partitioning, uses the <A NAME="marker=2417">
</A>
simulated-annealing algorithm [<A NAME="Kirkpatrick83">
</A>
Kirkpatrick et al., 1983]. Simulated annealing takes an existing solution and then makes successive changes in a series of random moves. Each move is accepted or rejected based on an <A NAME="marker=2420">
</A>
energy function, calculated for each new trial configuration. The minimums of the energy function correspond to possible solutions. The best solution is the <A NAME="marker=2422">
</A>
global minimum.</P>
<P CLASS="Body">
<A NAME="pgfId=2427">
</A>
So far the description of simulated annealing is similar to the interchange algorithms, but there is an important difference. In an interchange strategy we accept the new trial configuration only if the energy function decreases, which means the new configuration is an improvement. However, in the simulated-annealing algorithm, we accept the new configuration even if the energy function increases for the new configuration—which means things are getting worse. The probability of accepting a worse configuration is controlled by the exponential expression exp(–D<SPAN CLASS="EquationVariables">
E / T</SPAN>
), where D<SPAN CLASS="EquationVariables">
E</SPAN>
is the resulting increase in the energy function. The parameter <SPAN CLASS="EquationVariables">
T</SPAN>
is a variable that we control and corresponds to the temperature in the annealing of a metal cooling (this is why the process is called simulated annealing). </P>
<P CLASS="Body">
<A NAME="pgfId=2431">
</A>
We accept moves that seemingly take us away from a desirable solution to allow the system to escape from a local minimum and find other, better, solutions. The name for this strategy is <A NAME="marker=118847">
</A>
hill climbing. As the temperature is slowly decreased, we decrease the probability of making moves that increase the energy function. Finally, as the temperature approaches zero, we refuse to make any moves that increase the energy of the system and the system falls and comes to rest at the nearest local minimum. Hopefully, the solution that corresponds to the minimum we have found is a good one.</P>
<P CLASS="Body">
<A NAME="pgfId=2437">
</A>
The critical parameter governing the behavior of the simulated-annealing algorithm is the rate at which the temperature <SPAN CLASS="EquationVariables">
T</SPAN>
is reduced. This rate is known as the <A NAME="marker=16502">
</A>
cooling schedule. Often we set a parameter a that relates the temperatures, <SPAN CLASS="EquationVariables">
T</SPAN>
<SUB CLASS="SubscriptVariable">
i</SUB>
<SUB CLASS="Subscript">
</SUB>
and <SPAN CLASS="EquationVariables">
T</SPAN>
<SUB CLASS="SubscriptVariable">
i</SUB>
<SUB CLASS="Subscript">
+ 1</SUB>
, at the <SPAN CLASS="EquationVariables">
i</SPAN>
th and <SPAN CLASS="EquationVariables">
i</SPAN>
+ 1th iteration: </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=205071">
</A>
<SPAN CLASS="EquationVariables">
T</SPAN>
<SUB CLASS="SubscriptVariable">
i</SUB>
<SUB CLASS="Subscript">
+1</SUB>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=205073">
</A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=205075">
</A>
<SPAN CLASS="Symbol">
a</SPAN>
<SPAN CLASS="EquationVariables">
T</SPAN>
<SUB CLASS="SubscriptVariable">
i</SUB>
.</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=205077">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=205079">
</A>
(15.22)</P>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=16496">
</A>
To find a good solution, a local minimum close to the global minimum, requires a high initial temperature and a slow cooling schedule. This results in many trial moves and very long computer run times [<A NAME="Rose90">
</A>
Rose, Klebsch, and Wolf, 1990]. If we are prepared to wait a long time (forever in the worst case), simulated annealing is useful because we can guarantee that we can find the optimum solution. Simulated annealing is useful in several of the ASIC construction steps and we shall return to it in Section 16.2.7.</P>
</DIV>
<DIV>
<H2 CLASS="Heading2">
<A NAME="pgfId=2441">
</A>
15.7.9 Other Partitioning Objectives</H2>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=182796">
</A>
In partitioning a real system we need to weight each logic cell according to its area in order to control the total areas of each ASIC. This can be done if the area of each logic cell can either be calculated or estimated. This is usually done as part of floorplanning, so we may need to return to partitioning after floorplanning.</P>
<P CLASS="Body">
<A NAME="pgfId=182800">
</A>
There will be many objectives or constraints that we need to take into account during partitioning. For example, certain logic cells in a system may need to be located on the same ASIC in order to avoid adding the delay of any external interconnections. These <A NAME="marker=182801">
</A>
timing constraints can be implemented by adding weights to nets to make them more important than others. Some logic cells may consume more power than others and you may need to add <A NAME="marker=182805">
</A>
power constraints to avoid exceeding the power-handling capability of a single ASIC. It is difficult, though, to assign more than rough estimates of power consumption for each logic cell at the system planning stage, before any simulation has been completed. Certain logic cells may only be available in a certain technology—if you want to include memory on an ASIC, for example. In this case, <A NAME="marker=182806">
</A>
technology constraints will keep together logic cells requiring similar technologies. We probably want to impose <A NAME="marker=182807">
</A>
cost constraints to implement certain logic cells in the lowest cost technology available or to keep ASICs below a certain size in order to use a low-cost package. The type of test strategy you adopt will also affect the partitioning of logic. Large RAM blocks may require BIST circuitry; large amounts of sequential logic may require scan testing, possibly with a boundary-scan interface. One of the objects of testability is to maintain controllability and observability of logic inside each ASIC. In order to do this, <A NAME="marker=182808">
</A>
test constraints may require that we force certain connections to be external. No automated partitioning tools can take into account all of these constraints. The best CAD tool to help you with these decisions is a spreadsheet.</P>
</DIV>
<HR><P>[ <A HREF="CH15.htm">Chapter start</A> ] [ <A HREF="CH15.6.htm">Previous page</A> ] [ <A HREF="CH15.8.htm">Next page</A> ]</P></BODY>
<!--#include file="Copyright.html"--><!--#include file="footer.html"-->
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -