ch16.2.htm
来自「介绍asci设计的一本书」· HTM 代码 · 共 2,471 行 · 第 1/5 页
HTM
2,471 行
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML EXPERIMENTAL 970324//EN">
<HTML>
<HEAD>
<META NAME="GENERATOR" CONTENT="Adobe FrameMaker 5.5/HTML Export Filter">
<TITLE> 16.2 Placement</TITLE></HEAD><!--#include file="top.html"--><!--#include file="header.html"-->
<DIV>
<P>[ <A HREF="CH16.htm">Chapter start</A> ] [ <A HREF="CH16.1.htm">Previous page</A> ] [ <A HREF="CH16.3.htm">Next page</A> ]</P><!--#include file="AmazonAsic.html"--><HR></DIV>
<H1 CLASS="Heading1">
<A NAME="pgfId=1525">
</A>
16.2 <A NAME="19788">
</A>
Placement</H1>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=19245">
</A>
After completing a floorplan we can begin placement of the logic cells within the flexible blocks. Placement is much more suited to automation than floorplanning. Thus we shall need measurement techniques and algorithms. After we complete floorplanning and placement, we can predict both intrablock and interblock capacitances. This allows us to return to logic synthesis with more accurate estimates of the capacitive loads that each logic cell must drive. </P>
<DIV>
<H2 CLASS="Heading2">
<A NAME="pgfId=70179">
</A>
16.2.1 <A NAME="18750">
</A>
Placement Terms and Definitions</H2>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=70180">
</A>
CBIC, MGA, and FPGA architectures all have rows of logic cells separated by the interconnect—these are <SPAN CLASS="Definition">
row-based ASICs</SPAN>
<A NAME="marker=70181">
</A>
. <A HREF="CH16.2.htm#27992" CLASS="XRef">
Figure 16.18</A>
shows an example of the interconnect structure for a CBIC. Interconnect runs in horizontal and vertical directions in the channels and in the vertical direction by crossing through the logic cells. <A HREF="CH16.2.htm#27992" CLASS="XRef">
Figure 16.18</A>
(c) illustrates the fact that it is possible to use <SPAN CLASS="Definition">
over-the-cell routing</SPAN>
<A NAME="marker=70188">
</A>
(<A NAME="marker=70189">
</A>
<SPAN CLASS="Definition">
OTC</SPAN>
<A NAME="marker=70190">
</A>
routing) in areas that are not blocked. However, OTC routing is complicated by the fact that the logic cells themselves may contain metal on the routing layers. We shall return to this topic in Section 17.2.7, “Multilevel Routing.” <A HREF="CH16.2.htm#42422" CLASS="XRef">
Figure 16.19</A>
shows the interconnect structure of a two-level metal MGA. </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=70199">
</A>
<IMG SRC="CH16-18.gif" ALIGN="BASELINE">
</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigureTitle">
<A NAME="pgfId=70202">
</A>
FIGURE 16.18 <A NAME="27992">
</A>
Interconnect structure. (a) The two-level metal CBIC floorplan shown in <A HREF="CH16.1.htm#36876" CLASS="XRef">
Figure 16.11</A>
b. (b) A channel from the flexible block A. This channel has a channel height equal to the maximum channel density of 7 (there is room for seven interconnects to run horizontally in m1). (c) A channel that uses OTC (over-the-cell) routing in m2.</P>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=70209">
</A>
Most ASICs currently use two or three levels of metal for signal routing. With two layers of metal, we route within the rectangular channels using the first metal layer for horizontal routing, parallel to the channel spine, and the second metal layer for the vertical direction (if there is a third metal layer it will normally run in the horizontal direction again). The maximum number of horizontal interconnects that can be placed side by side, parallel to the channel spine, is the <A NAME="marker=70213">
</A>
<SPAN CLASS="Definition">
channel capacity</SPAN>
. </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=70222">
</A>
<IMG SRC="CH16-19.gif" ALIGN="BASELINE">
</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigureTitle">
<A NAME="pgfId=70225">
</A>
FIGURE 16.19 <A NAME="42422">
</A>
Gate-array interconnect. (a) A small two-level metal gate array (about 4.6 k-gate). (b) Routing in a block. (c) Channel routing showing channel density and channel capacity. The channel height on a gate array may only be increased in increments of a row. If the interconnect does not use up all of the channel, the rest of the space is wasted. The interconnect in the channel runs in m1 in the horizontal direction with m2 in the vertical direction. </P>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=70228">
</A>
Vertical interconnect uses <A NAME="marker=70226">
</A>
<SPAN CLASS="Definition">
feedthroughs</SPAN>
(or <A NAME="marker=70227">
</A>
<SPAN CLASS="Definition">
feedthrus</SPAN>
in the United States) to cross the logic cells. Here are some commonly used terms with explanations (there are no generally accepted definitions):</P>
<UL>
<LI CLASS="BulletFirst">
<A NAME="pgfId=70232">
</A>
An unused <SPAN CLASS="Definition">
vertical track</SPAN>
<A NAME="marker=70229">
</A>
(or just <A NAME="marker=70230">
</A>
<SPAN CLASS="Definition">
track</SPAN>
) in a logic cell is called an <A NAME="marker=70231">
</A>
<SPAN CLASS="Definition">
uncommitted feedthrough</SPAN>
(also <A NAME="marker=70233">
</A>
<SPAN CLASS="Definition">
built-in feedthrough</SPAN>
, <SPAN CLASS="Definition">
implicit feedthrough</SPAN>
<A NAME="marker=70234">
</A>
, or <SPAN CLASS="Definition">
jumper</SPAN>
<A NAME="marker=70235">
</A>
).</LI>
<LI CLASS="BulletList">
<A NAME="pgfId=70237">
</A>
A vertical strip of metal that runs from the top to bottom of a cell (for <SPAN CLASS="Definition">
double-entry cells</SPAN>
<A NAME="marker=70236">
</A>
), but has no connections inside the cell, is also called a feedthrough or jumper.</LI>
<LI CLASS="BulletList">
<A NAME="pgfId=70239">
</A>
Two connectors for the same physical net are <SPAN CLASS="Definition">
electrically equivalent connectors </SPAN>
<A NAME="marker=70238">
</A>
(or <A NAME="marker=91311">
</A>
<SPAN CLASS="Definition">
equipotential connectors</SPAN>
). For double-entry cells these are usually at the top and bottom of the logic cell.</LI>
<LI CLASS="BulletList">
<A NAME="pgfId=70242">
</A>
A dedicated <A NAME="marker=70240">
</A>
<SPAN CLASS="Definition">
feedthrough cell</SPAN>
(or <SPAN CLASS="Definition">
crosser cell</SPAN>
<A NAME="marker=70241">
</A>
) is an empty cell (with no logic) that can hold one or more vertical interconnects. These are used if there are no other feedthroughs available.</LI>
<LI CLASS="BulletList">
<A NAME="pgfId=70245">
</A>
A <A NAME="marker=70243">
</A>
<SPAN CLASS="Definition">
feedthrough pin</SPAN>
or <A NAME="marker=70244">
</A>
<SPAN CLASS="Definition">
feedthrough terminal</SPAN>
is an input or output that has connections at both the top and bottom of the standard cell. </LI>
<LI CLASS="BulletLast">
<A NAME="pgfId=70247">
</A>
A <SPAN CLASS="Definition">
spacer cell</SPAN>
<A NAME="marker=70246">
</A>
(usually the same as a feedthrough cell) is used to fill space in rows so that the ends of all rows in a flexible block may be aligned to connect to power buses, for example. </LI>
</UL>
<P CLASS="Body">
<A NAME="pgfId=70248">
</A>
There is no standard terminology for connectors and the terms can be very confusing. There is a difference between connectors that are joined inside the logic cell using a high-resistance material such as polysilicon and connectors that are joined by low-resistance metal. The high-resistance kind are really two separate <SPAN CLASS="Definition">
alternative connectors </SPAN>
<A NAME="marker=70249">
</A>
(that cannot be used as a feedthrough), whereas the low-resistance kind are <A NAME="marker=70250">
</A>
electrically equivalent connectors. There may be two or more connectors to a logic cell, which are not joined inside the cell, and which must be joined by the router (<SPAN CLASS="Definition">
must-join connectors</SPAN>
<A NAME="marker=70252">
</A>
).</P>
<P CLASS="Body">
<A NAME="pgfId=70295">
</A>
There are also <SPAN CLASS="Definition">
logically equivalent connectors</SPAN>
<A NAME="marker=70253">
</A>
(or<A NAME="marker=70254">
</A>
functionally equivalent connectors, sometimes also called just equivalent connectors—which is very confusing). The two inputs of a two-input NAND gate may be logically equivalent connectors. The placement tool can swap these without altering the logic (but the two inputs may have different delay properties, so it is not always a good idea to swap them). There can also be <SPAN CLASS="Definition">
logically equivalent connector groups</SPAN>
<A NAME="marker=70255">
</A>
. For example, in an OAI22 (OR-AND-INVERT) gate there are four inputs: A1, A2 are inputs to one OR gate (gate A), and B1, B2 are inputs to the second OR gate (gate B). Then group A = (A1, A2) is logically equivalent to group B = (B1, B2)—if we swap one input (A1 or A2) from gate A to gate B, we must swap the other input in the group (A2 or A1). </P>
<P CLASS="Body">
<A NAME="pgfId=70259">
</A>
In the case of channeled gate arrays and FPGAs, the horizontal interconnect areas—the channels, usually on m1—have a fixed capacity (sometimes they are called <SPAN CLASS="Definition">
fixed-resource ASICs</SPAN>
<A NAME="marker=70260">
</A>
for this reason). The channel capacity of CBICs and channelless MGAs can be expanded to hold as many interconnects as are needed. Normally we choose, as an objective, to minimize the number of interconnects that use each channel. In the vertical interconnect direction, usually m2, FPGAs still have fixed resources. In contrast the placement tool can always add vertical feedthroughs to a channeled MGA, channelless MGA, or CBIC. These problems become less important as we move to three and more levels of interconnect.</P>
</DIV>
<DIV>
<H2 CLASS="Heading2">
<A NAME="pgfId=11764">
</A>
16.2.2 <A NAME="26746">
</A>
Placement Goals and Objectives</H2>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=1529">
</A>
The goal of a placement tool is to arrange all the logic cells within the flexible blocks on a chip. Ideally, the objectives of the placement step are to</P>
<UL>
<LI CLASS="BulletFirst">
<A NAME="pgfId=9755">
</A>
Guarantee the router can complete the routing step</LI>
<LI CLASS="BulletList">
<A NAME="pgfId=9761">
</A>
Minimize all the critical net delays</LI>
<LI CLASS="BulletLast">
<A NAME="pgfId=9775">
</A>
Make the chip as dense as possible</LI>
</UL>
<P CLASS="Body">
<A NAME="pgfId=9762">
</A>
We may also have the following additional objectives:</P>
<UL>
<LI CLASS="BulletFirst">
<A NAME="pgfId=9764">
</A>
Minimize power dissipation</LI>
<LI CLASS="BulletLast">
<A NAME="pgfId=9765">
</A>
Minimize <A NAME="marker=80880">
</A>
cross talk between signals</LI>
</UL>
<P CLASS="Body">
<A NAME="pgfId=1533">
</A>
Objectives such as these are difficult to define in a way that can be solved with an algorithm and even harder to actually meet. Current placement tools use more specific and achievable criteria. The most commonly used placement objectives are one or more of the following:</P>
<UL>
<LI CLASS="BulletFirst">
<A NAME="pgfId=1545">
</A>
Minimize the total estimated interconnect length</LI>
<LI CLASS="BulletList">
<A NAME="pgfId=9796">
</A>
Meet the timing requirements for critical nets</LI>
<LI CLASS="BulletLast">
<A NAME="pgfId=1547">
</A>
Minimize the interconnect congestion</LI>
</UL>
<P CLASS="Body">
<A NAME="pgfId=70321">
</A>
Each of these objectives in some way represents a compromise.</P>
</DIV>
<DIV>
<H2 CLASS="Heading2">
<A NAME="pgfId=1555">
</A>
16.2.3 <A NAME="40739">
</A>
Measurement of Placement Goals and Objectives</H2>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=1559">
</A>
In order to determine the quality of a placement, we need to be able to measure it. We need an approximate measure of interconnect length, closely correlated with the final interconnect length, that is easy to calculate.</P>
<P CLASS="Body">
<A NAME="pgfId=9891">
</A>
The graph structures that correspond to making all the connections for a net are known as <SPAN CLASS="Definition">
trees on graphs</SPAN>
<A NAME="marker=9892">
</A>
(or just <SPAN CLASS="Definition">
trees</SPAN>
<A NAME="marker=9893">
</A>
). Special classes of trees—<A NAME="marker=91342">
</A>
<SPAN CLASS="Definition">
Steiner trees</SPAN>
—minimize the total length of interconnect and they are central to ASIC routing algorithms. <A HREF="CH16.2.htm#22348" CLASS="XRef">
Figure 16.20</A>
shows a minimum Steiner tree. This type of tree uses diagonal connections—we want to solve a restricted version of this problem, using interconnects on a rectangular grid. This is called <SPAN CLASS="Definition">
rectilinear routing</SPAN>
<A NAME="marker=9898">
</A>
or <SPAN CLASS="Definition">
Manhattan routing</SPAN>
<A NAME="marker=9899">
</A>
(because of the east–west and north–south grid of streets in Manhattan). We say that the <SPAN CLASS="Definition">
Euclidean distance</SPAN>
<A NAME="marker=9900">
</A>
between two points is the straight-line distance (“as the crow flies”). The <SPAN CLASS="Definition">
Manhattan distance</SPAN>
<A NAME="marker=9901">
</A>
(or <A NAME="marker=9913">
</A>
rectangular distance) between two points is the distance we would have to walk in New York. </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=9907">
</A>
</P>
<DIV>
<IMG SRC="CH16-20.gif">
</DIV>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigureTitle">
<A NAME="pgfId=9910">
</A>
FIGURE 16.20 <A NAME="22348">
</A>
Placement using trees on graphs. (a) The floorplan from <A HREF="CH16.1.htm#36876" CLASS="XRef">
Figure 16.11</A>
b. (b) An expanded view of the flexible block A showing four rows of standard cells for placement (typical blocks may contain thousands or tens of thousands of logic cells). We want to find the length of the net shown with four terminals, W through Z, given the placement of four logic cells (labeled: A.211, A.19, A.43, A.25). (c) The problem for net (W, X, Y, Z) drawn as a graph. The shortest connection is the minimum Steiner tree. (d) The minimum rectilinear Steiner tree using Manhattan routing. The rectangular (Manhattan) interconnect-length measures are shown for each tree.</P>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=1586">
</A>
The <A NAME="marker=1582">
</A>
<SPAN CLASS="Definition">
minimum rectilinear Steiner tree</SPAN>
(<A NAME="marker=1585">
</A>
MRST<A NAME="marker=67923">
</A>
) is the shortest interconnect using a rectangular grid. The determination of the MRST is in general an NP-complete problem—which means it is hard to solve. For small numbers of terminals heuristic algorithms do exist, but they are expensive to compute. Fortunately we only need to estimate the length of the interconnect. Two approximations to the MRST are shown in <A HREF="CH16.2.htm#28123" CLASS="XRef">
Figure 16.21</A>
.</P>
<P CLASS="Body">
<A NAME="pgfId=1613">
</A>
The <A NAME="marker=1609">
</A>
<SPAN CLASS="Definition">
complete graph</SPAN>
has connections from each terminal to every other terminal [<A NAME="Hanan73">
</A>
Hanan, Wolff, and Agule, 1973]. The <A NAME="marker=1612">
</A>
<SPAN CLASS="Definition">
complete-graph measure</SPAN>
adds all the interconnect lengths of the complete-graph connection together and then divides by <SPAN CLASS="EquationVariables">
n</SPAN>
/2, where <SPAN CLASS="EquationVariables">
n</SPAN>
is the number of terminals. We can justify this since, in a graph with <SPAN CLASS="EquationVariables">
n</SPAN>
terminals, (<SPAN CLASS="EquationVariables">
n</SPAN>
– 1) interconnects will emanate from each terminal to join the other (<SPAN CLASS="EquationVariables">
n</SPAN>
– 1) terminals in a complete graph connection. That makes <SPAN CLASS="EquationVariables">
n</SPAN>
(<SPAN CLASS="EquationVariables">
n</SPAN>
– 1) interconnects in total. However, we have then made each connection twice. So there are one-half this many, or <SPAN CLASS="EquationVariables">
n</SPAN>
(<SPAN CLASS="EquationVariables">
n</SPAN>
– 1)/2, interconnects needed for a complete graph connection. Now we actually only need (<SPAN CLASS="EquationVariables">
n</SPAN>
– 1) interconnects to join <SPAN CLASS="EquationVariables">
n</SPAN>
terminals, so we have <SPAN CLASS="EquationVariables">
n</SPAN>
/2 times as many interconnects as we really need. Hence we divide the total net length of the complete graph connection by <SPAN CLASS="EquationVariables">
n</SPAN>
/2 to obtain a more reasonable estimate of minimum interconnect length. <A HREF="CH16.2.htm#28123" CLASS="XRef">
Figure 16.21</A>
(a) shows an example of the complete-graph measure. </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigTitleSide">
<A NAME="pgfId=86512">
</A>
FIGURE 16.21 <A NAME="28123">
</A>
Interconnect-length measures. (a) Complete-graph measure. (b) Half-perimeter measure.</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=7229">
</A>
</P>
<DIV>
<IMG SRC="CH16-21.gif">
</DIV>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=1631">
</A>
The <A NAME="marker=1627">
</A>
<SPAN CLASS="Definition">
bounding box</SPAN>
is the smallest rectangle that encloses all the terminals (not to be confused with a logic cell bounding box, which encloses all the layout in a logic cell). The <A NAME="marker=1630">
</A>
<SPAN CLASS="Definition">
half-perimeter measure</SPAN>
(or <A NAME="marker=27951">
</A>
bounding-box measure) is one-half the perimeter of the bounding box (<A HREF="CH16.2.htm#28123" CLASS="XRef">
Figure 16.21</A>
b) [<A NAME="Schweikert76">
</A>
Schweikert, 1976]. For nets with two or three terminals (corresponding to a fanout of one or two, which usually includes over 50 percent of all nets on a chip), the half-perimeter measure is the same as the minimum Steiner tree. For nets with four or five terminals, the minimum Steiner tree is between one and two times the half-perimeter measure [<A NAME="Hanan66">
</A>
Hanan, 1966]. For a circuit with <SPAN CLASS="EquationVariables">
m</SPAN>
nets, using the half-perimeter measure corresponds to minimizing the cost function, </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=110116">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=110118">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110120">
</A>
1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=110122">
</A>
<SPAN CLASS="EquationVariables">
m</SPAN>
</P>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?