ch17.1.htm
来自「介绍asci设计的一本书」· HTM 代码 · 共 2,690 行 · 第 1/5 页
HTM
2,690 行
</SUB>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=83935">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=83937">
</A>
+ (500 + 6)(0.02 + 0.2 + 0.2)</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=83939">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=83941">
</A>
<SPAN CLASS="Symbol">
</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=83943">
</A>
</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=83945">
</A>
<SUB CLASS="Subscript">
</SUB>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=83947">
</A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=83949">
</A>
344 ps .</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=83951">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=83953">
</A>
<SPAN CLASS="Symbol">
</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=83955">
</A>
</P>
</TD>
</TR>
</TABLE>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=38241">
</A>
and <SPAN CLASS="Symbol">
t</SPAN>
<SUB CLASS="SubscriptVariable">
D</SUB>
<SUB CLASS="Subscript">
4</SUB>
– <SPAN CLASS="Symbol">
t</SPAN>
<SUB CLASS="SubscriptVariable">
D</SUB>
<SUB CLASS="Subscript">
2</SUB>
= (425 – 344) = 81 ps.</P>
<P CLASS="Body">
<A NAME="pgfId=37963">
</A>
A <SPAN CLASS="Definition">
lumped-delay model</SPAN>
<A NAME="marker=67087">
</A>
neglects the effects of interconnect resistance and simply sums all the node capacitances (the <SPAN CLASS="Definition">
lumped capacitance</SPAN>
<A NAME="marker=67143">
</A>
) as follows: </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=84055">
</A>
<SPAN CLASS="Symbol">
t</SPAN>
<SUB CLASS="SubscriptVariable">
D</SUB>
<SUB CLASS="Subscript">
</SUB>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=84057">
</A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=84059">
</A>
<SPAN CLASS="EquationVariables">
R</SPAN>
<SUB CLASS="SubscriptVariable">
pd</SUB>
(<SPAN CLASS="EquationVariables">
C</SPAN>
<SUB CLASS="Subscript">
1</SUB>
+ <SPAN CLASS="EquationVariables">
C</SPAN>
<SUB CLASS="Subscript">
2</SUB>
+ <SPAN CLASS="EquationVariables">
C</SPAN>
<SUB CLASS="Subscript">
3</SUB>
+ <SPAN CLASS="EquationVariables">
C</SPAN>
<SUB CLASS="Subscript">
4</SUB>
) </P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=84061">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=84063">
</A>
<SPAN CLASS="Symbol">
</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=84065">
</A>
<A NAME="30163">
</A>
(17.8)</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=84091">
</A>
<SUB CLASS="Subscript">
</SUB>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=84093">
</A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=84095">
</A>
(500) (0.02 + 0.04 + 0.2 + 0.42)</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=84097">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=84099">
</A>
<SPAN CLASS="Symbol">
</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=84101">
</A>
</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=84115">
</A>
<SUB CLASS="Subscript">
</SUB>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=84117">
</A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=84119">
</A>
340 ps .</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=84121">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=84123">
</A>
<SPAN CLASS="Symbol">
</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=84125">
</A>
</P>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=67142">
</A>
Comparing Eqs. <A HREF="CH17.1.htm#10892" CLASS="XRef">
17.6</A>
–<A HREF="CH17.1.htm#30163" CLASS="XRef">
17.8</A>
, we can see that the delay of the inverter can be assigned as follows: 20 ps (the intrinsic delay, 0.2 ns, due to the cell output capacitance), 340 ps (due to the pull-down resistance and the output capacitance), 4 ps (due to the interconnect from A to B), and 65 ps (due to the interconnect from A to C). We can see that the error from neglecting interconnect resistance can be important.</P>
<P CLASS="Body">
<A NAME="pgfId=67201">
</A>
Even using the Elmore constant we still made the following assumptions in estimating the path delays:</P>
<UL>
<LI CLASS="BulletFirst">
<A NAME="pgfId=67101">
</A>
A step-function waveform drives the net.</LI>
<LI CLASS="BulletList">
<A NAME="pgfId=67102">
</A>
The delay is measured from when the gate input changes.</LI>
<LI CLASS="BulletFirst">
<A NAME="pgfId=67103">
</A>
The delay is equal to the time constant of an exponential waveform that approximates the actual output waveform.</LI>
<LI CLASS="BulletLast">
<A NAME="pgfId=67104">
</A>
The interconnect is modeled by discrete resistance and capacitance elements.</LI>
</UL>
<P CLASS="Body">
<A NAME="pgfId=39282">
</A>
The global router could use more sophisticated estimates that remove some of these assumptions, but there is a limit to the accuracy with which delay can be estimated during global routing. For example, the global router does not know how much of the routing is on which of the layers, or how many vias will be used and of which type, or how wide the metal lines will be. It may be possible to estimate how much interconnect will be horizontal and how much is vertical. Unfortunately, this knowledge does not help much if horizontal interconnect may be completed in either m1 or m3 and there is a large difference in parasitic capacitance between m1 and m3, for example.</P>
<P CLASS="Body">
<A NAME="pgfId=67131">
</A>
When the global router attempts to minimize interconnect delay, there is an important difference between a path and a net. The path that minimizes the delay between two terminals on a net is not necessarily the same as the path that minimizes the total path length of the net. For example, to minimize the path delay (using the Elmore constant as a measure) from the output of inverter A in <A HREF="CH17.1.htm#28148" CLASS="XRef">
Figure 17.3</A>
(a) to the input of inverter B requires a rather complicated algorithm to construct the best path. We shall return to this problem in <A HREF="CH17.1.htm#20908" CLASS="XRef">
Section 17.1.6</A>
.</P>
</DIV>
<DIV>
<H2 CLASS="Heading2">
<A NAME="pgfId=37943">
</A>
17.1.3 <A NAME="16846">
</A>
Global Routing Methods</H2>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=611">
</A>
Global routing cannot use the interconnect-length approximations, such as the half-perimeter measure, that were used in placement. What is needed now is the actual path and not an approximation to the path length. However, many of the methods used in global routing are still based on the solutions to the tree on a graph problem.</P>
<P CLASS="Body">
<A NAME="pgfId=36511">
</A>
One approach to global routing takes each net in turn and calculates the shortest path using tree on graph algorithms—with the added restriction of using the available channels. This process is known as <A NAME="marker=3942">
</A>
<SPAN CLASS="Definition">
sequential routing</SPAN>
. As a sequential routing algorithm proceeds, some channels will become more congested since they hold more interconnects than others. In the case of FPGAs and channeled gate arrays, the channels have a fixed channel capacity and can only hold a certain number of interconnects. There are two different ways that a global router normally handles this problem. Using <A NAME="marker=36482">
</A>
<SPAN CLASS="Definition">
order-independent routing</SPAN>
, a global router proceeds by routing each net, ignoring how crowded the channels are. Whether a particular net is processed first or last does not matter, the channel assignment will be the same. In order-independent routing, after all the interconnects are assigned to channels, the global router returns to those channels that are the most crowded and reassigns some interconnects to other, less crowded, channels. Alternatively, a global router can consider the number of interconnects already placed in various channels as it proceeds. In this case the global routing is <A NAME="marker=628">
</A>
<SPAN CLASS="Definition">
order dependent</SPAN>
—the routing is still sequential, but now the order of processing the nets will affect the results. Iterative improvement or simulated annealing may be applied to the solutions found from both order-dependent and order-independent algorithms. This is implemented in the same way as for system partitioning and placement: A constructed solution is successively changed, one interconnect path at a time, in a series of random moves. </P>
<P CLASS="Body">
<A NAME="pgfId=36512">
</A>
In contrast to sequential global-routing methods, which handle nets one at a time, <A NAME="marker=33390">
</A>
<SPAN CLASS="Definition">
hierarchical routing</SPAN>
handles all nets at a particular level at once. Rather than handling all of the nets on the chip at the same time, the global-routing problem is made more tractable by dividing the chip area into levels of hierarchy. By considering only one level of hierarchy at a time the size of the problem is reduced at each level. There are two ways to traverse the levels of hierarchy. Starting at the whole chip, or highest level, and proceeding down to the logic cells is the top-down approach. The bottom-up approach starts at the lowest level of hierarchy and globally routes the smallest areas first.</P>
</DIV>
<DIV>
<H2 CLASS="Heading2">
<A NAME="pgfId=37158">
</A>
17.1.4 <A NAME="12692">
</A>
Global Routing Between Blocks</H2>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=37172">
</A>
<A HREF="CH17.1.htm#12255" CLASS="XRef">
Figure 17.4</A>
illustrates the global-routing problem for a cell-based ASIC. Each edge in the <A NAME="marker=37173">
</A>
<SPAN CLASS="Definition">
channel-intersection graph</SPAN>
in <A HREF="CH17.1.htm#12255" CLASS="XRef">
Figure 17.4</A>
(c) represents a channel. The global router is restricted to using these channels. The weight of each edge in the graph corresponds to the length of the channel. The global router plans a path for each interconnect using this graph. </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=37598">
</A>
<IMG SRC="CH17-4.gif" ALIGN="BASELINE">
</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigureTitle">
<A NAME="pgfId=37602">
</A>
FIGURE 17.4 <A NAME="12255">
</A>
Global routing for a cell-based ASIC formulated as a graph problem. (a) A cell-based ASIC with numbered channels. (b) The channels form the edges of a graph. (c) The channel-intersection graph. Each channel corresponds to an edge on a graph whose weight corresponds to the channel length.</P>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=37180">
</A>
<A HREF="CH17.1.htm#11878" CLASS="XRef">
Figure 17.5</A>
shows an example of global routing for a net with five terminals, labeled A1 through F1, for the cell-based ASIC shown in <A HREF="CH17.1.htm#12255" CLASS="XRef">
Figure 17.4</A>
. If a designer wishes to use minimum total interconnect path length as an objective, the global router finds the minimum-length tree shown in <A HREF="CH17.1.htm#11878" CLASS="XRef">
Figure 17.5</A>
(b). This tree determines the channels the interconnects will use. For example, the shortest connection from A1 to B1 uses channels 2, 1, and 5 (in that order). This is the information the global router passes to the detailed router. <A HREF="CH17.1.htm#11878" CLASS="XRef">
Figure 17.5</A>
(c) shows that minimizing the total path length may not correspond to minimizing the path delay between two points.</P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=76583">
</A>
</P>
<DIV>
<IMG SRC="CH17-5.gif">
</DIV>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigureTitle">
<A NAME="pgfId=76585">
</A>
FIGURE 17.5 <A NAME="11878">
</A>
Finding paths in global routing. (a) A cell-based ASIC (from <A HREF="CH17.1.htm#12255" CLASS="XRef">
Figure 17.4</A>
) showing a single net with a fanout of four (five terminals). We have to order the numbered channels to complete the interconnect path for terminals A1 through F1. (b) The terminals are projected to the center of the nearest channel, forming a graph. A minimum-length tree for the net that uses the channels and takes into account the channel capacities. (c) The minimum-length tree does not necessarily correspond to minimum delay. If we wish to minimize the delay from terminal A1 to D1, a different tree might be better.</P>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=37206">
</A>
Global routing is very similar for cell-based ASICs and gate arrays, but there is a very important difference between the types of channels in these ASICs. The size of the channels in sea-of-gates arrays, channelless gate arrays, and cell-based ASICs can be varied to make sure there is enough space to complete the wiring. In channeled gate-arrays and FPGAs the size, number, and location of channels are fixed. The good news is that the global router can allocate as many interconnects to each channel as it likes, since that space is committed anyway. The bad news is that there is a maximum number of interconnects that each channel can hold. If the global router needs more room, even in just one channel on the whole chip, the designer has to repeat the placement-and-routing steps and try again (or use a bigger chip).</P>
</DIV>
<DIV>
<H2 CLASS="Heading2">
<A NAME="pgfId=67253">
</A>
17.1.5 <A NAME="22489">
</A>
Global Routing Inside Flexible Blocks</H2>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=67257">
</A>
We shall illustrate global routing using a gate array. <A HREF="CH17.1.htm#35690" CLASS="XRef">
Figure 17.6</A>
(a) shows the routing resources on a sea-of-gates or channelless gate array. The gate array base cells are arranged in 36 blocks, each block containing an array of 8-by-16 gate-array base cells, making a total of 4068 base cells. </P>
<P CLASS="Body">
<A NAME="pgfId=42952">
</A>
The horizontal interconnect resources are the routing channels that are formed from unused rows of the gate-array base cells, as shown in <A HREF="CH17.1.htm#35690" CLASS="XRef">
Figure 17.6</A>
(b) and (c). The vertical resources are feedthroughs. For example, the logic cell shown in <A HREF="CH17.1.htm#35690" CLASS="XRef">
Figure 17.6</A>
(d) is an inverter that contains two types of feedthrough. The inverter logic cell uses a single gate-array base cell with terminals (or <SPAN CLASS="Emphasis">
connectors</SPAN>
) located at the top and bottom of the logic cell. The inverter input pin has two electrically equivalent terminals that the global router can use as a feedthrough. The output of the inverter is connected to only one terminal. The remaining vertical <SPAN CLASS="Definition">
track</SPAN>
<A NAME="marker=42680">
</A>
is unused by the inverter logic cell, so this track forms an uncommitted feedthrough.</P>
<P CLASS="Body">
<A NAME="pgfId=37016">
</A>
You may see any of the terms <SPAN CLASS="Definition">
landing pad</SPAN>
<A NAME="marker=37017">
</A>
(because we say that we “drop” a via to a landing pad), <SPAN CLASS="Definition">
pick-up point</SPAN>
<A NAME="marker=50281">
</A>
, <SPAN CLASS="Definition">
connector</SPAN>
<A NAME="marker=50282">
</A>
, <SPAN CLASS="Definition">
terminal</SPAN>
<A NAME="marker=50285">
</A>
, <SPAN CLASS="Definition">
pin</SPAN>
<A NAME="marker=50286">
</A>
, or <SPAN CLASS="Definition">
port</SPAN>
<A NAME="marker=50287">
</A>
used for the connection to a logic cell. The term <SPAN CLASS="Emphasis">
pick-up point</SPAN>
refers to the physical pieces of metal (or sometimes polysilicon) in the logic cell to which the router connects. In a three-level metal process, the global router may be able to connect to anywhere in an area—an <SPAN CLASS="Definition">
area pick-up point</SPAN>
<A NAME="marker=37019">
</A>
. In this book we use the term <SPAN CLASS="Emphasis">
connector</SPAN>
to refer to the physical pick-up point. The term <SPAN CLASS="Emphasis">
pin</SPAN>
more often refers to the connection on a logic schematic icon (a dot, square box, or whatever symbol is used), rather than layout. Thus the difference between a pin and a connector is that we can have multiple connectors for one pin. <SPAN CLASS="Emphasis">
Terminal</SPAN>
is often used when we talk about routing. The term <SPAN CLASS="Emphasis">
port</SPAN>
is used when we are using text (EDIF netlists or HDLs, for example) to describe circuits.</P>
<P CLASS="Body">
<A NAME="pgfId=37023">
</A>
In a gate array the channel capacity must be a multiple of the number of <SPAN CLASS="Definition">
horizontal tracks</SPAN>
<A NAME="marker=37027">
</A>
<A NAME="marker=42608">
</A>
in the gate-array base cell. <A HREF="CH17.1.htm#35690" CLASS="XRef">
Figure 17.6</A>
(e) shows a gate-array base cell with seven horizontal tracks (see <A HREF="CH17.2.htm#42292" CLASS="XRef">
Section 17.2</A>
for the factors that determine the track width and track spacing). Thus, in this gate array, we can have a channel with a capacity of 7, 14, 21, ... horizontal tracks—but not between these values. </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=37039">
</A>
<IMG SRC="CH17-6.gif" ALIGN="BASELINE">
</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigureTitle">
<A NAME="pgfId=37042">
</A>
FIGURE 17.6 <A NAME="35690">
</A>
Gate-array global routing. (a) A small gate array. (b) An enlarged view of the routing. The top channel uses three rows of gate-array base cells; the other channels use only one. (c) A further enlarged view showing how the routing in the channels connects to the logic cells. (d) One of the logic cells, an inverter. (e) There are seven horizontal wiring tracks available in one row of gate-array base cells—the channel capacity is thus 7. </P>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=37046">
</A>
<A HREF="CH17.1.htm#10517" CLASS="XRef">
Figure 17.7</A>
shows the inverter macro for the sea-of-gates array shown in <A HREF="CH17.1.htm#35690" CLASS="XRef">
Figure 17.6</A>
. <A HREF="CH17.1.htm#10517" CLASS="XRef">
Figure 17.7</A>
(a) shows the base cell. <A HREF="CH17.1.htm#10517" CLASS="XRef">
Figure 17.7</A>
(b) shows how the internal inverte⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?