ch17.2.htm

介绍asci设计的一本书

<SPAN CLASS="Definition">
column</SPAN>
. If the branches use m2, the <A NAME="marker=42561">
 </A>
<SPAN CLASS="Definition">
column spacing</SPAN>
 (or <A NAME="marker=42562">
 </A>
<SPAN CLASS="Definition">
vertical track spacing</SPAN>
) is equal to the m2 routing pitch.</P>
<DIV>
<H2 CLASS="Heading2">
<A NAME="pgfId=9405">
 </A>
17.2.1&nbsp;Goals and Objectives</H2>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=830">
 </A>
The goal of detailed routing is to complete all the connections between logic cells. The most common objective is to minimize one or more of the following:</P>
<UL>
<LI CLASS="BulletFirst">
<A NAME="pgfId=33435">
 </A>
The total interconnect length and area</LI>
<LI CLASS="BulletList">
<A NAME="pgfId=33464">
 </A>
The number of layer changes that the connections have to make</LI>
<LI CLASS="BulletList">
<A NAME="pgfId=33465">
 </A>
The delay of critical paths</LI>
</UL>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=33466">
 </A>
Minimizing the number of layer changes corresponds to minimizing the number of vias that add parasitic resistance and capacitance to a connection. </P>
<P CLASS="Body">
<A NAME="pgfId=42603">
 </A>
In some cases the detailed router may not be able to complete the routing in the area provided. In the case of a cell-based ASIC or sea-of-gates array, it is possible to increase the channel size and try the routing steps again. A channeled gate array or FPGA has fixed routing resources and in these cases we must start all over again with floorplanning and placement, or use a larger chip.</P>
</DIV>
<DIV>
<H2 CLASS="Heading2">
<A NAME="pgfId=864">
 </A>
17.2.2&nbsp;<A NAME="32630">
 </A>
Measurement of Channel Density</H2>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=866">
 </A>
We can describe a channel-routing problem by specifying two lists of nets: one for the top edge of the channel and one for the bottom edge. The position of the net number in the list gives the column position. The net number zero represents a vacant or unused terminal. <A HREF="CH17.2.htm#31065" CLASS="XRef">
Figure&nbsp;17.14</A>
 shows a channel with the numbered terminals to be connected along the top and the bottom of the channel. </P>
<P CLASS="Body">
<A NAME="pgfId=23382">
 </A>
We call the number of nets that cross a line drawn vertically anywhere in a channel the <A NAME="marker=23383">
 </A>
<SPAN CLASS="Definition">
local density</SPAN>
. We call the maximum local density of the channel the <A NAME="marker=23384">
 </A>
<SPAN CLASS="Definition">
global density</SPAN>
 or sometimes just <A NAME="marker=23385">
 </A>
<SPAN CLASS="Definition">
channel density</SPAN>
. <A HREF="CH17.2.htm#31065" CLASS="XRef">
Figure&nbsp;17.14</A>
 has a channel density of 4. Channel density is an important measure in routing&#8212;it tells a router the absolute fewest number of horizontal interconnects that it needs at the point where the local density is highest. In two-level routing (all the horizontal interconnects run on one routing layer) the channel density determines the minimum height of the channel. The channel capacity is the maximum number of interconnects that a channel can hold. If the channel density is greater than the channel capacity, that channel definitely cannot be routed (to learn how channel density is calculated, see <A HREF="CH17.2.htm#42052" CLASS="XRef">
Section&nbsp;17.2.5</A>
).</P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=76656">
 </A>
&nbsp;</P>
<DIV>
<IMG SRC="CH17-14.gif">
</DIV>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigureTitle">
<A NAME="pgfId=76658">
 </A>
FIGURE&nbsp;17.14&nbsp;<A NAME="31065">
 </A>
The definitions of local channel density and global channel density. Lines represent the m1 and m2 interconnect in the channel to simplify the drawing.</P>
</TD>
</TR>
</TABLE>
</DIV>
<DIV>
<H2 CLASS="Heading2">
<A NAME="pgfId=896">
 </A>
17.2.3&nbsp;<A NAME="11582">
 </A>
Algorithms</H2>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=902">
 </A>
We start discussion of routing methods by simplifying the general channel-routing problem. The <A NAME="marker=900">
 </A>
<SPAN CLASS="Definition">
restricted channel-routing</SPAN>
 <SPAN CLASS="Definition">
problem</SPAN>
 limits each net in a channel to use only one horizontal segment. In other words the channel router uses only one trunk for each net. This restriction has the effect of minimizing the number of connections between the routing layers. This is equivalent to minimizing the number of vias used by the channel router in a two-layer metal technology. Minimizing the number of vias is an important objective in routing a channel, but it is not always practical. Sometimes constraints will force a channel router to use jogs or other methods to complete the routing (see <A HREF="CH17.2.htm#42052" CLASS="XRef">
Section&nbsp;17.2.5</A>
). Next, though, we shall study an algorithm that solves the restricted channel-routing problem. </P>
</DIV>
<DIV>
<H2 CLASS="Heading2">
<A NAME="pgfId=910">
 </A>
17.2.4&nbsp;<A NAME="40892">
 </A>
Left-Edge Algorithm</H2>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=918">
 </A>
The <A NAME="marker=914">
 </A>
<SPAN CLASS="Definition">
left-edge algorithm</SPAN>
 (<A NAME="marker=917">
 </A>
<SPAN CLASS="Definition">
LEA</SPAN>
<A NAME="marker=39149">
 </A>
) is the basis for several routing algorithms [<A NAME="Hashimoto71">
 </A>
Hashimoto and Stevens, 1971]. The LEA applies to two-layer channel routing, using one layer for the trunks and the other layer for the branches. For example, m1 may be used in the horizontal direction and m2 in the vertical direction. The LEA proceeds as follows:</P>
<OL>
<LI CLASS="NumberFirst">
<A NAME="pgfId=926">
 </A>
Sort the nets according to the leftmost edges of the net&#8217;s horizontal segment.</LI>
<LI CLASS="NumberList">
<A NAME="pgfId=928">
 </A>
Assign the first net on the list to the first free track. </LI>
<LI CLASS="NumberList">
<A NAME="pgfId=930">
 </A>
Assign the next net on the list, which will fit, to the track.</LI>
<LI CLASS="NumberList">
<A NAME="pgfId=932">
 </A>
Repeat this process from step 3 until no more nets will fit in the current track.</LI>
<LI CLASS="NumberList">
<A NAME="pgfId=934">
 </A>
Repeat steps 2&#8211;4 until all nets have been assigned to tracks.</LI>
<LI CLASS="NumberLast">
<A NAME="pgfId=936">
 </A>
Connect the net segments to the top and bottom of the channel.</LI>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=71704">
 </A>
&nbsp;</P>
<DIV>
<IMG SRC="CH17-15.gif">
</DIV>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigureTitle">
<A NAME="pgfId=71706">
 </A>
FIGURE&nbsp;17.15&nbsp;<A NAME="32636">
 </A>
Left-edge algorithm. (a) Sorted list of segments. (b)&nbsp;Assignment to tracks. (c)&nbsp;Completed channel route (with m1 and m2 interconnect represented by lines).</P>
</TD>
</TR>
</TABLE>
</OL>
<P CLASS="Body">
<A NAME="pgfId=940">
 </A>
<A HREF="CH17.2.htm#32636" CLASS="XRef">
Figure&nbsp;17.15</A>
 illustrates the LEA. The algorithm works as long as none of the branches touch&#8212;which may occur if there are terminals in the same column belonging to different nets. In this situation we have to make sure that the trunk that connects to the top of the channel is placed above the lower trunk. Otherwise two branches will overlap and short the nets together. In the next section we shall examine this situation more closely.</P>
</DIV>
<DIV>
<H2 CLASS="Heading2">
<A NAME="pgfId=949">
 </A>
17.2.5&nbsp;<A NAME="42052">
 </A>
Constraints and Routing Graphs</H2>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=961">
 </A>
Two terminals that are in the same column in a channel create a <A NAME="marker=955">
 </A>
<SPAN CLASS="Definition">
vertical constraint</SPAN>
. We say that the terminal at the top of the column imposes a vertical constraint on the lower terminal. We can draw a graph showing the vertical constraints imposed by terminals. The nodes in a <A NAME="marker=958">
 </A>
<SPAN CLASS="Definition">
vertical-constraint graph</SPAN>
 represent terminals. A vertical constraint between two terminals is shown by an edge of the graph connecting the two terminals. A graph that contains information in the direction of an edge is a <A NAME="marker=36682">
 </A>
<SPAN CLASS="Definition">
directed graph</SPAN>
. The arrow on the graph edge shows the direction of the constraint&#8212;pointing to the lower terminal, which is constrained. <A HREF="CH17.2.htm#34432" CLASS="XRef">
Figure&nbsp;17.16</A>
(a) shows an example of a channel, and <A HREF="CH17.2.htm#34432" CLASS="XRef">
Figure&nbsp;17.16</A>
(b) shows its vertical constraint graph. </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=3067">
 </A>
<IMG SRC="CH17-16.gif" ALIGN="BASELINE">
&nbsp;</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigureTitle">
<A NAME="pgfId=3069">
 </A>
FIGURE&nbsp;17.16&nbsp;<A NAME="34432">
 </A>
Routing graphs. (a)&nbsp;Channel with a global density of 4. (b)&nbsp;The vertical constraint graph. If two nets occupy the same column, the net at the top of the channel imposes a vertical constraint on the net at the bottom. For example, net 2 imposes a vertical constraint on net 4. Thus the interconnect for net 4 must use a track above net 2. (c)&nbsp;Horizontal-constraint graph. If the segments of two nets overlap, they are connected in the horizontal-constraint graph. This graph determines the global channel density.</P>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=71982">
 </A>
We can also define a <A NAME="marker=71980">
 </A>
<SPAN CLASS="Definition">
horizontal constraint</SPAN>
 and a corresponding <A NAME="marker=71981">
 </A>
<SPAN CLASS="Definition">
horizontal-constraint graph</SPAN>
. If the trunk for net 1 overlaps the trunk of net 2, then we say there is a horizontal constraint between net 1 and net 2. Unlike a vertical constraint, a horizontal constraint has no direction. <A HREF="CH17.2.htm#34432" CLASS="XRef">
Figure&nbsp;17.16</A>
(c) shows an example of a horizontal constraint graph and shows a group of 4 terminals (numbered 3, 5, 6, and 7) that must all overlap. Since this is the largest such group, the global channel density is 4.</P>
<P CLASS="Body">
<A NAME="pgfId=979">
 </A>
If there are no vertical constraints at all in a channel, we can guarantee that the LEA will find the minimum number of routing tracks. The addition of vertical constraints transforms the restricted routing problem into an NP-complete problem. There is also an arrangement of vertical constraints that none of the algorithms based on the LEA can cope with. In <A HREF="CH17.2.htm#27130" CLASS="XRef">
Figure&nbsp;17.17</A>
(a) net 1 is above net 2 in the first column of the channel. Thus net 1 imposes a vertical constraint on net 2. Net 2 is above net 1 in the last column of the channel. Then net 2 also imposes a vertical constraint on net 1. It is impossible to route this arrangement using two routing layers with the restriction of using only one trunk for each net. If we construct the vertical-constraint graph for this situation, shown in <A HREF="CH17.2.htm#27130" CLASS="XRef">
Figure&nbsp;17.17</A>
(b), there is a loop or cycle between nets 1 and 2. If there is any such <A NAME="marker=994">
 </A>
<SPAN CLASS="Definition">
vertical-constraint cycle</SPAN>
 (or <A NAME="marker=997">
 </A>
<SPAN CLASS="Definition">
cyclic constraint</SPAN>
) between two or more nets, the LEA will fail. A <A NAME="marker=3189">
 </A>
<SPAN CLASS="Definition">
dogleg router</SPAN>
 removes the restriction that each net can use only one track or trunk. <A HREF="CH17.2.htm#27130" CLASS="XRef">
Figure&nbsp;17.17</A>
(c) shows how adding a dogleg permits a channel with a cyclic constraint to be routed. </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigTitleSide">
<A NAME="pgfId=50078">
 </A>
FIGURE&nbsp;17.17&nbsp;<A NAME="27130">
 </A>
The addition of a dogleg, an extra trunk, in the wiring of a net can resolve cyclic vertical constraints.</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=50049">
 </A>
<IMG SRC="CH17-17.gif" ALIGN="BASELINE">
&nbsp;</P>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=50028">
 </A>
The channel-routing algorithms we have described so far do not allow interconnects on one layer to run on top of other interconnects on a different layer. These algorithms allow interconnects to cross at right angles to each other on different layers, but not to <A NAME="marker=1128">
 </A>
<SPAN CLASS="Definition">
overlap</SPAN>
. When we remove the restriction that horizontal and vertical routing must use different layers, the density of a channel is no longer the lower bound for the number of tracks required. For two routing layers the ultimate lower bound becomes half of the channel density. The practical reasoning for restricting overlap is the parasitic <SPAN CLASS="Definition">
overlap capacitance</SPAN>