ch17.2.htm

介绍asci设计的一本书

<A NAME="marker=6126">
 </A>
 between signal interconnects. As the dimensions of the metal interconnect are reduced, the capacitance between adjacent interconnects on the same layer (<SPAN CLASS="Definition">
coupling capacitance</SPAN>
<A NAME="marker=6129">
 </A>
) is comparable to the capacitance of interconnects that overlap on different layers (<SPAN CLASS="Definition">
overlap capacitance</SPAN>
<A NAME="marker=68057">
 </A>
). Thus, allowing a short overlap between interconnects on different layers may not be as bad as allowing two interconnects to run adjacent to each other for a long distance on the same layer. Some routers allow you to specify that two interconnects must not run adjacent to each other for more than a specified length.</P>
<P CLASS="Body">
<A NAME="pgfId=1219">
 </A>
The channel height is fixed for channeled gate arrays; it is variable in discrete steps for channelless gate arrays; it is continuously variable for cell-based ASICs. However, for all these types of ASICs, the channel wiring is fully customized and so may be compacted or compressed after a channel router has completed the interconnect. The use of <A NAME="marker=1217">
 </A>
<SPAN CLASS="Definition">
channel-routing compaction</SPAN>
 for a two-layer channel can reduce the channel height by 15 percent to 20 percent [<A NAME="Cheng92">
 </A>
Cheng et al., 1992]. </P>
<P CLASS="Body">
<A NAME="pgfId=50137">
 </A>
Modern channel routers are capable of routing a channel at or near the theoretical minimum density. We can thus consider channel routing a solved problem. Most of the difficulty in detailed routing now comes from the need to route more than two layers and to route arbitrary shaped regions. These problems are best handled by area routers.</P>
</DIV>
<DIV>
<H2 CLASS="Heading2">
<A NAME="pgfId=1223">
 </A>
17.2.6&nbsp;<A NAME="34551">
 </A>
Area-Routing Algorithms</H2>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=1235">
 </A>
There are many algorithms used for the detailed routing of general-shaped areas (see the paper by Ohtsuki in [<A NAME="Ohtsuki86">
 </A>
Ohtsuki, 1986]). Many of these were originally developed for PCB wiring. The first group we shall cover and the earliest to be used historically are the <A NAME="marker=1227">
 </A>
<SPAN CLASS="Definition">
grid-expansion</SPAN>
 or <A NAME="marker=1230">
 </A>
<SPAN CLASS="Definition">
maze-running</SPAN>
 algorithms. A second group of methods, which are more efficient, are the <A NAME="marker=1232">
 </A>
<SPAN CLASS="Definition">
line-search</SPAN>
 algorithms. </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigTitleSide">
<A NAME="pgfId=68104">
 </A>
FIGURE&nbsp;17.18&nbsp;<A NAME="19502">
 </A>
The Lee maze-running algorithm. The algorithm finds a path from source (X) to target (Y) by emitting a wave from both the source and the target at the same time. Successive outward moves are marked in each bin. Once the target is reached, the path is found by backtracking (if there is a choice of bins with equal labeled values, we choose the bin that avoids changing direction). (The original form of the Lee algorithm uses a single wave.)</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=50484">
 </A>
<IMG SRC="CH17-18.gif" ALIGN="BASELINE">
&nbsp;</P>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=1245">
 </A>
<A HREF="CH17.2.htm#19502" CLASS="XRef">
Figure&nbsp;17.18</A>
 illustrates the <A NAME="marker=1241">
 </A>
<SPAN CLASS="Definition">
Lee maze-running algorithm</SPAN>
. The goal is to find a path from X to Y&#8212;i.e., from the start (or source) to the finish (or target)&#8212;avoiding any obstacles. The algorithm is often called <A NAME="marker=1244">
 </A>
<SPAN CLASS="Definition">
wave propagation</SPAN>
 because it sends out waves, which spread out like those created by dropping a stone into a pond. </P>
<P CLASS="Body">
<A NAME="pgfId=76471">
 </A>
Algorithms that use lines rather than waves to search for connections are more efficient than algorithms based on the Lee algorithm. <A HREF="CH17.2.htm#40560" CLASS="XRef">
Figure&nbsp;17.19</A>
 illustrates the <A NAME="marker=76476">
 </A>
<SPAN CLASS="Definition">
Hightower algorithm</SPAN>
&#8212;a <A NAME="marker=76477">
 </A>
<SPAN CLASS="Definition">
line-search algorithm</SPAN>
 (or <SPAN CLASS="Definition">
line-probe algorithm</SPAN>
<A NAME="marker=76478">
 </A>
):</P>
<OL>
<LI CLASS="NumberFirst">
<A NAME="pgfId=76479">
 </A>
Extend lines from both the source and target toward each other. </LI>
<LI CLASS="NumberList">
<A NAME="pgfId=1306">
 </A>
When an extended line, known as an <A NAME="marker=1302">
 </A>
<SPAN CLASS="Definition">
escape line</SPAN>
, meets an obstacle, choose a point on the escape line from which to project another escape line at right angles to the old one. This point is the <A NAME="marker=1305">
 </A>
<SPAN CLASS="Definition">
escape point</SPAN>
. </LI>
<LI CLASS="NumberList">
<A NAME="pgfId=1308">
 </A>
Place an escape point on the line so that the next escape line just misses the edge of the obstacle. Escape lines emanating from the source and target intersect to form the path.</LI>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigTitleSide">
<A NAME="pgfId=76702">
 </A>
FIGURE&nbsp;17.19&nbsp;<A NAME="40560">
 </A>
Hightower area-routing algorithm. (a) Escape lines are constructed from source (X) and target (Y) toward each other until they hit obstacles. (b) An escape point is found on the escape line so that the next escape line perpendicular to the original misses the next obstacle. The path is complete when escape lines from source and target meet.</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=76708">
 </A>
<IMG SRC="CH17-19.gif" ALIGN="BASELINE">
&nbsp;</P>
</TD>
</TR>
</TABLE>
</OL>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=9553">
 </A>
The Hightower algorithm is faster and requires less memory than methods based on the Lee algorithm. </P>
</DIV>
<DIV>
<H2 CLASS="Heading2">
<A NAME="pgfId=23395">
 </A>
17.2.7&nbsp;<A NAME="22224">
 </A>
Multilevel Routing</H2>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=33514">
 </A>
Using <SPAN CLASS="Definition">
two-layer routing</SPAN>
<A NAME="marker=72065">
 </A>
, if the logic cells do not contain any m2, it is possible to complete some routing in m2 using over-the-cell (OTC) routing. Sometimes poly is used for short connections in the channel in a two-level metal technology; this is known as <SPAN CLASS="Definition">
2.5-layer routing</SPAN>
<A NAME="marker=72060">
 </A>
. Using a third level of metal in <SPAN CLASS="Definition">
three-layer routing</SPAN>
<A NAME="marker=72068">
 </A>
, there is a choice of approaches. <SPAN CLASS="Definition">
Reserved-layer routing</SPAN>
<A NAME="marker=33576">
 </A>
 restricts all the interconnect on each layer to flow in one direction in a given routing area (for example, in a channel, either parallel or perpendicular to the channel spine). <SPAN CLASS="Definition">
Unreserved-layer routing</SPAN>
<A NAME="marker=33577">
 </A>
 moves in both horizontal and vertical directions on a given layer. Most routers use reserved routing. Reserved three-level metal routing offers another choice: Either use m1 and m3 for horizontal routing (parallel to the channel spine), with m2 for vertical routing (<SPAN CLASS="Definition">
HVH routing</SPAN>
<A NAME="marker=33587">
 </A>
<A NAME="marker=39146">
 </A>
) or use <SPAN CLASS="Definition">
VHV routing</SPAN>
<A NAME="marker=33588">
 </A>
<A NAME="marker=39147">
 </A>
. Since the logic cell interconnect usually blocks most of the area on the m1 layer, HVH routing is normally used. It is also important to consider the pitch of the layers when routing in the same direction on two different layers. Using HVH routing it is preferable for the m3 pitch to be a simple multiple of the m1 pitch (ideally they are the same). Some processes have more than three levels of metal. Sometimes the upper one or two metal layers have a coarser pitch than the lower layers and are used in <SPAN CLASS="Definition">
multilevel routing</SPAN>
<A NAME="marker=72069">
 </A>
 for power and clock lines rather than for signal interconnect.</P>
<P CLASS="Body">
<A NAME="pgfId=37294">
 </A>
<A HREF="CH17.2.htm#16305" CLASS="XRef">
Figure&nbsp;17.20</A>
 shows an example of three-layer channel routing. The logic cells are 64 <SPAN CLASS="Symbol">
l</SPAN>
 high, the m1 routing pitch is 8 <SPAN CLASS="Symbol">
l,</SPAN>
 and the m2 and m3 routing pitch is 16 <SPAN CLASS="Symbol">
l</SPAN>
. The channel in <A HREF="CH17.2.htm#16305" CLASS="XRef">
Figure&nbsp;17.20</A>
 is the same as the channel using two-layer metal shown in <A HREF="CH17.2.htm#31067" CLASS="XRef">
Figure&nbsp;17.13</A>
, but using three-level metal reduces the channel height from 40 <SPAN CLASS="Symbol">
l</SPAN>
 ( = 5 <SPAN CLASS="Symbol">
&#165;</SPAN>
 8 <SPAN CLASS="Symbol">
l</SPAN>
) to 16 <SPAN CLASS="Symbol">
l</SPAN>
. Submicron processes try to use the same metal pitch on all metal layers. This makes routing easier but processing more difficult. </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=37301">
 </A>
<IMG SRC="CH17-20.gif" ALIGN="BASELINE">
&nbsp;</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigureTitle">
<A NAME="pgfId=37304">
 </A>
FIGURE&nbsp;17.20&nbsp;<A NAME="16305">
 </A>
Three-level channel routing. In this diagram the m2 and m3 routing pitch is set to twice the m1 routing pitch. Routing density can be increased further if all the routing pitches can be made equal&#8212;a difficult process challenge.</P>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=50588">
 </A>
With three or more levels of metal routing it is possible to reduce the channel height in a row-based ASIC to zero. All of the interconnect is then completed over the cell. If all of the channels are eliminated, the core area (logic cells plus routing) is determined solely by the logic-cell area. The point at which this happens depends on not only the number of metal layers and channel density, but also the routing resources (the blockages and feedthroughs) in the logic cell. This the <SPAN CLASS="Definition">
cell porosity</SPAN>
<A NAME="marker=50598">
 </A>
. Designing porous cells that help to minimize routing area is an art. For example, it is quite common to be able to produce a smaller chip using larger logic cells if the larger cells have more routing resources.</P>
</DIV>
<DIV>
<H2 CLASS="Heading2">
<A NAME="pgfId=20546">
 </A>
17.2.8&nbsp;<A NAME="18743">
 </A>
Timing-Driven Detailed Routing</H2>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=20549">
 </A>
In detailed routing the global router has already set the path the interconnect will follow. At this point little can be done to improve timing except to reduce the number of vias, alter the interconnect width to optimize delay, and minimize overlap capacitance. The gains here are relatively small, but for very long branching nets even small gains may be important. For high-frequency clock nets it may be important to shape and <SPAN CLASS="Definition">
chamfer</SPAN>
<A NAME="marker=50539">
 </A>
 (round) the interconnect to match impedances at branches and control reflections at corners. </P>
</DIV>
<DIV>
<H2 CLASS="Heading2">
<A NAME="pgfId=21621">
 </A>
17.2.9&nbsp;Final Routing Steps</H2>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=21622">
 </A>
If the algorithms to estimate congestion in the floorplanning tool accurately perfectly reflected the algorithms used by the global router and detailed router, routing completion should be guaranteed. Often, however, the detailed router will not be able to completely route all the nets. These problematical nets are known as <SPAN CLASS="Definition">
unroutes</SPAN>
<A NAME="marker=50188">
 </A>
. Routers handle this situation in one of two ways. The first method leaves the problematical nets unconnected. The second method completes all interconnects anyway but with some design-rule violations (the problematical nets may be shorted to other nets, for example). Some tools flag these problems as a warning (in fact there can be no more serious error).</P>
<P CLASS="Body">
<A NAME="pgfId=21633">
 </A>
If there are many unroutes the designer needs to discover the reason and return to the floorplanner and change channel sizes (for a cell-based ASIC) or increase the base-array size (for a gate array). Returning to the global router and changing bin sizes or adjusting the algorithms may also help. In drastic cases it may be necessary to change the floorplan. If just a handful of difficult nets remain to be routed, some tools allow the designer to perform hand edits using a <A NAME="marker=21673">
 </A>
<A NAME="marker=21674">
 </A>
<A NAME="marker=21675">
 </A>
<SPAN CLASS="Definition">
rip-up and reroute</SPAN>
 router (sometimes this is done automatically by the detailed router as a last phase in the routing procedure anyway). This capability also permits <SPAN CLASS="Definition">
engineering change orders</SPAN>
<A NAME="marker=21679">
 </A>
 (<A NAME="marker=21680">
 </A>
<SPAN CLASS="Definition">
ECO</SPAN>
)&#8212;corresponding to the little yellow wires on a PCB. One of the last steps in routing is <SPAN CLASS="Definition">
via removal</SPAN>
<A NAME="marker=21689">
 </A>
&#8212;the detailed router looks to see if it can eliminate any vias (which can contribute a significant amount to the interconnect resistance) by changing layers or making other modifications to the completed routing. <A NAME="marker=70614">
 </A>
<SPAN CLASS="Definition">
Routing compaction</SPAN>
 can then be performed as the final step.</P>
</DIV>
<HR><P>[&nbsp;<A HREF="CH17.htm">Chapter&nbsp;start</A>&nbsp;]&nbsp;[&nbsp;<A HREF="CH17.1.htm">Previous&nbsp;page</A>&nbsp;]&nbsp;[&nbsp;<A HREF="CH17.3.htm">Next&nbsp;page</A>&nbsp;]</P></BODY>

<!--#include file="Copyright.html"--><!--#include file="footer.html"-->