ch16.2.htm

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

</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110124">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=110126">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=110128">
 </A>
&nbsp;</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=110130">
 </A>
<SPAN CLASS="EquationVariables">
f</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110132">
 </A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110134">
 </A>
&#8211;&#8211;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110136">
 </A>
<SPAN CLASS="BigMath">
S</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110138">
 </A>
<SPAN CLASS="EquationVariables">
h</SPAN>
<SUB CLASS="SubscriptVariable">
i</SUB>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=110140">
 </A>
<SPAN CLASS="Symbol">
,</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=110143">
 </A>
(16.5)</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=110145">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=110147">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110149">
 </A>
2</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110151">
 </A>
<SPAN CLASS="EquationVariables">
i</SPAN>
 = 1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110153">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=110155">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=110157">
 </A>
&nbsp;</P>
</TD>
</TR>
</TABLE>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=58152">
 </A>
where <SPAN CLASS="EquationVariables">
h</SPAN>
<SUB CLASS="SubscriptVariable">
i</SUB>
 is the half-perimeter measure for net <SPAN CLASS="EquationVariables">
i</SPAN>
.</P>
<P CLASS="Body">
<A NAME="pgfId=58153">
 </A>
It does not really matter if our approximations are inaccurate if there is a good correlation between actual interconnect lengths (after routing) and our approximations. <A HREF="CH16.2.htm#32290" CLASS="XRef">
Figure&nbsp;16.22</A>
 shows that we can adjust the complete-graph and half-perimeter measures using correction factors [<A NAME="Goto86">
 </A>
Goto and Matsuda, 1986]. Now our wiring length approximations are functions, not just of the terminal positions, but also of the number of terminals, and the size of the bounding box. One practical example adjusts a Steiner-tree approximation using the number of terminals [<A NAME="Chao90">
 </A>
Chao, Nequist, and Vuong, 1990]. This technique is used in the Cadence Gate Ensemble placement tool, for example. </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigTitleSide">
<A NAME="pgfId=79982">
 </A>
FIGURE&nbsp;16.22&nbsp;<A NAME="32290">
 </A>
Correlation between total length of chip interconnect and the half-perimeter and complete-graph measures.</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=58166">
 </A>
&nbsp;</P>
<DIV>
<IMG SRC="CH16-22.gif">
</DIV>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=86293">
 </A>
One problem with the measurements we have described is that the MRST may only approximate the interconnect that will be completed by the detailed router. Some programs have a <SPAN CLASS="Definition">
meander factor</SPAN>
<A NAME="marker=58898">
 </A>
 that specifies, on average, the ratio of the interconnect created by the routing tool to the interconnect-length estimate used by the placement tool. Another problem is that we have concentrated on finding estimates to the MRST, but the MRST that minimizes total net length may not minimize net delay (see <A HREF="CH16.2.htm#35092" CLASS="XRef">
Section&nbsp;16.2.8</A>
). </P>
<P CLASS="Body">
<A NAME="pgfId=1671">
 </A>
There is no point in minimizing the interconnect length if we create a placement that is too congested to route. If we use minimum <A NAME="marker=1669">
 </A>
<SPAN CLASS="Definition">
interconnect congestion</SPAN>
 as an additional placement objective, we need some way of measuring it. What we are trying to measure is interconnect density. Unfortunately we always use the term <SPAN CLASS="Emphasis">
density</SPAN>
 to mean channel density (which we shall discuss in Section 17.2.2, &#8220;Measurement of Channel Density&#8221;). In this chapter, while we are discussing placement, we shall try to use the term <SPAN CLASS="Emphasis">
congestion</SPAN>
, instead of density, to avoid any confusion.</P>
<P CLASS="Body">
<A NAME="pgfId=57943">
 </A>
One measure of interconnect congestion uses the <A NAME="marker=57942">
 </A>
<SPAN CLASS="Definition">
maximum cut line</SPAN>
. Imagine a horizontal or vertical line drawn anywhere across a chip or block, as shown in <A HREF="CH16.2.htm#40194" CLASS="XRef">
Figure&nbsp;16.23</A>
. The number of interconnects that must cross this line is the <SPAN CLASS="Definition">
cut size</SPAN>
<A NAME="marker=58257">
 </A>
 (the number of interconnects we cut). The maximum cut line has the highest cut size. </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=57952">
 </A>
<IMG SRC="CH16-23.gif" ALIGN="BASELINE">
&nbsp;</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigureTitle">
<A NAME="pgfId=57955">
 </A>
FIGURE&nbsp;16.23&nbsp;<A NAME="40194">
 </A>
Interconnect congestion for the cell-based ASIC from <A HREF="CH16.1.htm#36876" CLASS="XRef">
Figure&nbsp;16.11</A>
(b). (a)&nbsp;Measurement of congestion. (b)&nbsp;An expanded view of flexible block A shows a maximum cut line.</P>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=25621">
 </A>
Many placement tools minimize estimated interconnect length or interconnect congestion as objectives. The problem with this approach is that a logic cell may be placed a long way from another logic cell to which it has just one connection. This logic cell with one connection is less important as far as the total wire length is concerned than other logic cells, to which there are many connections. However, the one long connection may be critical as far as timing delay is concerned. As technology is scaled, interconnection delays become larger relative to circuit delays and this problem gets worse.</P>
<P CLASS="Body">
<A NAME="pgfId=91381">
 </A>
In <SPAN CLASS="Definition">
timing-driven placement</SPAN>
<A NAME="marker=91380">
 </A>
 we must estimate delay for every net for every trial placement, possibly for hundreds of thousands of gates. We cannot afford to use anything other than the very simplest estimates of net delay. Unfortunately, the minimum-length Steiner tree does not necessarily correspond to the interconnect path that minimizes delay. To construct a minimum-delay path we may have to route with non-Steiner trees. In the placement phase typically we take a simple interconnect-length approximation to this minimum-delay path (typically the half-perimeter measure). Even when we can estimate the length of the interconnect, we do not yet have information on which layers and how many vias the interconnect will use or how wide it will be. Some tools allow us to include estimates for these parameters. Often we can specify <SPAN CLASS="Definition">
metal usage</SPAN>
<A NAME="marker=91382">
 </A>
, the percentage of routing on the different layers to expect from the router. This allows the placement tool to estimate RC values and delays&#8212;and thus minimize delay.</P>
</DIV>
<DIV>
<H2 CLASS="Heading2">
<A NAME="pgfId=3713">
 </A>
16.2.4&nbsp;<A NAME="22214">
 </A>
Placement Algorithms</H2>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=17846">
 </A>
There are two classes of placement algorithms commonly used in commercial CAD tools: constructive placement and iterative placement improvement. A <A NAME="marker=46294">
 </A>
<SPAN CLASS="Definition">
constructive placement method </SPAN>
uses a set of rules to arrive at a constructed placement. The most commonly used methods are variations on the <SPAN CLASS="Emphasis">
min-cut algorithm</SPAN>
. The other commonly used constructive placement algorithm is the <SPAN CLASS="Emphasis">
eigenvalue method.</SPAN>
 As in system partitioning, placement usually starts with a constructed solution and then improves it using an iterative algorithm. In most tools we can specify the locations and relative placements of certain critical logic cells as <A NAME="marker=46302">
 </A>
<SPAN CLASS="Definition">
seed placements</SPAN>
.</P>
<P CLASS="Body">
<A NAME="pgfId=1744">
 </A>
The <A NAME="marker=1742">
 </A>
<SPAN CLASS="Definition">
min-cut placement</SPAN>
 method uses successive application of partitioning [<A NAME="Breuer77">
 </A>
Breuer, 1977]. The following steps are shown in <A HREF="CH16.2.htm#40701" CLASS="XRef">
Figure&nbsp;16.24</A>
:</P>
<OL>
<LI CLASS="NumberFirst">
<A NAME="pgfId=1748">
 </A>
Cut the placement area into two pieces.</LI>
<LI CLASS="NumberList">
<A NAME="pgfId=1750">
 </A>
Swap the logic cells to minimize the cut cost. </LI>
<LI CLASS="NumberList">
<A NAME="pgfId=1752">
 </A>
Repeat the process from step 1, cutting smaller pieces until all the logic cells are placed. </LI>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=3770">
 </A>
<IMG SRC="CH16-24.gif" ALIGN="BASELINE">
&nbsp;</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigureTitle">
<A NAME="pgfId=3772">
 </A>
FIGURE&nbsp;16.24&nbsp;<A NAME="40701">
 </A>
Min-cut placement. (a)&nbsp;Divide the chip into bins using a grid. (b)&nbsp;Merge all connections to the center of each bin. (c)&nbsp;Make a cut and swap logic cells between bins to minimize the cost of the cut. (d)&nbsp;Take the cut pieces and throw out all the edges that are not inside the piece. (e)&nbsp;Repeat the process with a new cut and continue until we reach the individual bins.</P>
</TD>
</TR>
</TABLE>
</OL>
<P CLASS="Body">
<A NAME="pgfId=1761">
 </A>
Usually we divide the placement area into <SPAN CLASS="Definition">
bins</SPAN>
<A NAME="marker=19290">
 </A>
. The size of a bin can vary, from a bin size equal to the base cell (for a gate array) to a bin size that would hold several logic cells. We can start with a large bin size, to get a rough placement, and then reduce the bin size to get a final placement.</P>
<P CLASS="Body">
<A NAME="pgfId=1820">
 </A>
The <A NAME="marker=1816">
 </A>
<SPAN CLASS="Definition">
eigenvalue placement algorithm</SPAN>
 uses the cost matrix or weighted <A NAME="marker=1819">
 </A>
<SPAN CLASS="Definition">
connectivity matrix</SPAN>
 (<A NAME="marker=12998">
 </A>
eigenvalue methods are also known as <SPAN CLASS="Definition">
spectral methods</SPAN>
<A NAME="marker=12997">
 </A>
) [Hall, 1970]. The measure we use is a cost function <SPAN CLASS="EquationVariables">
f</SPAN>
 that we shall minimize, given by  </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=110193">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=110195">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110197">
 </A>
1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110199">
 </A>
<SPAN CLASS="EquationVariables">
n</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110201">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=110203">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=110205">
 </A>
&nbsp;</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=110207">
 </A>
<SPAN CLASS="EquationVariables">
f</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110209">
 </A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110211">
 </A>
&#8211;&#8211;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110213">
 </A>
<SPAN CLASS="BigMath">
S</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110215">
 </A>
<SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="SubscriptVariable">
ij</SUB>
<SPAN CLASS="EquationVariables">
 d</SPAN>
<SUB CLASS="SubscriptVariable">
ij </SUB>
<SUP CLASS="Superscript">
2</SUP>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=110217">
 </A>
<SPAN CLASS="Symbol">
,</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=110219">
 </A>
(16.6)</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=110222">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=110224">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110226">
 </A>
2</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110228">
 </A>
<SPAN CLASS="EquationVariables">
i</SPAN>
 = 1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110230">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=110232">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=110234">
 </A>
&nbsp;</P>
</TD>
</TR>
</TABLE>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=1829">
 </A>
where <SPAN CLASS="Vector">
C</SPAN>