📄 ch15.2.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML EXPERIMENTAL 970324//EN">
<HTML>
<HEAD>
<META NAME="GENERATOR" CONTENT="Adobe FrameMaker 5.5/HTML Export Filter">
<TITLE> 15.2 CAD Tools</TITLE></HEAD><!--#include file="top.html"--><!--#include file="header.html"-->
<DIV>
<P>[ <A HREF="CH15.htm">Chapter start</A> ] [ <A HREF="CH15.1.htm">Previous page</A> ] [ <A HREF="CH15.3.htm">Next page</A> ]</P><!--#include file="AmazonAsic.html"--><HR></DIV>
<H1 CLASS="Heading1">
<A NAME="pgfId=183802">
</A>
15.2 <A NAME="34307">
</A>
CAD Tools</H1>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=183803">
</A>
In order to develop a CAD tool it is necessary to convert each of the physical design steps to a problem with well-defined goals and objectives. The <A NAME="marker=183804">
</A>
goals for each physical design step are the things we must achieve. The <A NAME="marker=183805">
</A>
objectives for each step are things we would like to meet on the way to achieving the goals. Some examples of goals and objectives for each of the ASIC physical design steps are as follows:</P>
<P CLASS="Body">
<A NAME="pgfId=183806">
</A>
System partitioning:</P>
<UL>
<LI CLASS="BulletFirst">
<A NAME="pgfId=183807">
</A>
Goal. Partition a system into a number of ASICs.</LI>
<LI CLASS="BulletLast">
<A NAME="pgfId=183808">
</A>
Objectives. Minimize the number of external connections between the ASICs. Keep each ASIC smaller than a maximum size.</LI>
</UL>
<P CLASS="Body">
<A NAME="pgfId=183809">
</A>
Floorplanning:</P>
<UL>
<LI CLASS="BulletFirst">
<A NAME="pgfId=183810">
</A>
Goal. Calculate the sizes of all the blocks and assign them locations.</LI>
<LI CLASS="BulletLast">
<A NAME="pgfId=183811">
</A>
Objective. Keep the highly connected blocks physically close to each other.</LI>
</UL>
<P CLASS="Body">
<A NAME="pgfId=183812">
</A>
Placement:</P>
<UL>
<LI CLASS="BulletFirst">
<A NAME="pgfId=183813">
</A>
Goal. Assign the interconnect areas and the location of all the logic cells within the flexible blocks.</LI>
<LI CLASS="BulletLast">
<A NAME="pgfId=183814">
</A>
Objectives. Minimize the ASIC area and the interconnect density.</LI>
</UL>
<P CLASS="Body">
<A NAME="pgfId=183815">
</A>
Global routing:</P>
<UL>
<LI CLASS="BulletFirst">
<A NAME="pgfId=183816">
</A>
Goal. Determine the location of all the interconnect.</LI>
<LI CLASS="BulletLast">
<A NAME="pgfId=183817">
</A>
Objective. Minimize the total interconnect area used.</LI>
</UL>
<P CLASS="Body">
<A NAME="pgfId=183818">
</A>
Detailed routing:</P>
<UL>
<LI CLASS="BulletFirst">
<A NAME="pgfId=183819">
</A>
Goal. Completely route all the interconnect on the chip.</LI>
<LI CLASS="BulletLast">
<A NAME="pgfId=183820">
</A>
Objective. Minimize the total interconnect length used.</LI>
</UL>
<P CLASS="Body">
<A NAME="pgfId=183821">
</A>
There is no magic recipe involved in the choice of the ASIC physical design steps. These steps have been chosen simply because, as tools and techniques have developed historically, these steps proved to be the easiest way to split up the larger problem of ASIC physical design. The boundaries between the steps are not cast in stone. For example, floorplanning and placement are often thought of as one step and in some tools placement and routing are performed together.</P>
<DIV>
<H2 CLASS="Heading2">
<A NAME="pgfId=183823">
</A>
15.2.1 Methods and Algorithms</H2>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=183826">
</A>
A CAD tool needs <A NAME="marker=183824">
</A>
methods or <A NAME="marker=183825">
</A>
algorithms to generate a solution to each problem using a reasonable amount of computer time. Often there is no best solution possible to a particular problem, and the tools must use <A NAME="marker=183827">
</A>
heuristic algorithms, or rules of thumb, to try and find a good solution. The term <SPAN CLASS="Emphasis">
algorithm</SPAN>
is usually reserved for a method that always gives a solution.</P>
<P CLASS="Body">
<A NAME="pgfId=183828">
</A>
We need to know how practical any algorithm is. We say the <A NAME="marker=183829">
</A>
complexity of an algorithm is <A NAME="marker=183830">
</A>
O (<SPAN CLASS="EquationVariables">
f</SPAN>
(<SPAN CLASS="EquationVariables">
n</SPAN>
)) (read as <A NAME="marker=183831">
</A>
order <SPAN CLASS="EquationVariables">
f</SPAN>
<SPAN CLASS="EquationVariables">
</SPAN>
(<SPAN CLASS="EquationVariables">
n</SPAN>
)) if there are constants k and n<SUB CLASS="Subscript">
0</SUB>
so that the running time of the algorithm T (<SPAN CLASS="EquationVariables">
n</SPAN>
) is less than k <SPAN CLASS="EquationVariables">
f</SPAN>
(<SPAN CLASS="EquationVariables">
n</SPAN>
) for all <SPAN CLASS="EquationVariables">
n</SPAN>
> n<SUB CLASS="Subscript">
0</SUB>
[<A NAME="Sedgewick88">
</A>
Sedgewick, 1988]. Here <SPAN CLASS="EquationVariables">
n</SPAN>
is a measure of the size of the problem (number of transistors, number of wires, and so on). In ASIC design <SPAN CLASS="EquationVariables">
n</SPAN>
is usually very large. We have to be careful, though. The notation does not specify the units of time. An algorithm that is O (<SPAN CLASS="EquationVariables">
n</SPAN>
<SUP CLASS="Superscript">
2</SUP>
) nanoseconds might be better than an algorithm that is O (<SPAN CLASS="EquationVariables">
n</SPAN>
) seconds, for quite large values of <SPAN CLASS="EquationVariables">
n</SPAN>
. The notation O (<SPAN CLASS="EquationVariables">
n</SPAN>
) refers to an upper limit on the running time of the algorithm. A practical example may take less running time—it is just that we cannot prove it. We also have to be careful of the constants k and n<SUB CLASS="Subscript">
0</SUB>
. They can hide overhead present in the implementation and may be large enough to mask the dependence on <SPAN CLASS="EquationVariables">
n</SPAN>
, up to large values of <SPAN CLASS="EquationVariables">
n</SPAN>
. The function <SPAN CLASS="EquationVariables">
f (n)</SPAN>
is usually one of the following kinds:</P>
<UL>
<LI CLASS="BulletFirst">
<A NAME="pgfId=183835">
</A>
<SPAN CLASS="EquationVariables">
f (n)</SPAN>
= constant. The algorithm is <A NAME="marker=183834">
</A>
constant in time. In this case, steps of the algorithm are repeated once or just a few times. It would be nice if our algorithms had this property, but it does not usually happen in ASIC design.</LI>
<LI CLASS="BulletList">
<A NAME="pgfId=183837">
</A>
<SPAN CLASS="EquationVariables">
f (n)</SPAN>
= log<SPAN CLASS="EquationVariables">
n</SPAN>
. The algorithm is <A NAME="marker=183836">
</A>
logarithmic in time. This usually happens when a big problem is (possibly recursively) transformed into a smaller one.</LI>
<LI CLASS="BulletList">
<A NAME="pgfId=183839">
</A>
<SPAN CLASS="EquationVariables">
f (n) = n</SPAN>
. The algorithm is <A NAME="marker=183838">
</A>
linear in time. This is a good situation for an ASIC algorithm that works with <SPAN CLASS="EquationVariables">
n</SPAN>
objects.</LI>
<LI CLASS="BulletList">
<A NAME="pgfId=183840">
</A>
<SPAN CLASS="EquationVariables">
f (n)</SPAN>
= <SPAN CLASS="EquationVariables">
n </SPAN>
log<SPAN CLASS="EquationVariables">
n</SPAN>
. This type of algorithm arises when a large problem is split into a number of smaller problems, each solved independently.</LI>
<LI CLASS="BulletLast">
<A NAME="pgfId=183842">
</A>
<SPAN CLASS="EquationVariables">
f (n)</SPAN>
= <SPAN CLASS="EquationVariables">
n</SPAN>
<SUP CLASS="Superscript">
2</SUP>
. The algorithm is <A NAME="marker=183841">
</A>
quadratic in time and usually only practical for small ASIC problems.</LI>
</UL>
<P CLASS="Body">
<A NAME="pgfId=183843">
</A>
If the time it takes to solve a problem increases with the size of the problem at a rate that is polynomial but faster than quadratic (or worse in an exponential fashion), it is usually not appropriate for ASIC design. Even after subdividing the ASIC physical design problem into smaller steps, each of the steps still results in problems that are hard to solve automatically. In fact, each of the ASIC physical design steps, in general, belongs to a class of mathematical problems known as <A NAME="marker=183844">
</A>
NP-complete problems. This means that it is unlikely we can find an algorithm to solve the problem exactly in polynomial time.</P>
<P CLASS="Body">
<A NAME="pgfId=183845">
</A>
Suppose we find a practical method to solve our problem, even if we can find a solution we now have a dilemma. How shall we know if we have a good solution if, because the problem is NP-complete, we cannot find the optimum or best solution to which to compare it? We need to know how close we are to the optimum solution to a problem, even if that optimum solution cannot be found exactly. We need to make a quantitative <A NAME="marker=183850">
</A>
measurement of the quality of the solution that we are able to find. Often we combine several parameters or <A NAME="marker=183851">
</A>
metrics that measure our goals and objectives into a <A NAME="marker=183852">
</A>
measurement function or <A NAME="marker=183853">
</A>
objective function. If we are minimizing the measurement function, it is a <A NAME="marker=183854">
</A>
cost function. If we are maximizing the measurement function, we call the function a <A NAME="marker=183855">
</A>
gain function (sometimes just <A NAME="marker=183856">
</A>
gain).</P>
<P CLASS="Body">
<A NAME="pgfId=183857">
</A>
Now we are ready to solve each of the ASIC physical design steps with the following items in hand: a set of goals and objectives, a way to measure the goals and objectives, and an algorithm or method to find a solution that meets the goals and objectives. As designers attempt to achieve a desired ASIC performance they make a continuous trade-off between speed, area, power, and several other factors. Presently CAD tools are not smart enough to be able to do this alone. In fact, current CAD tools are only capable of finding a solution subject to a few, very simple, objectives. </P>
</DIV>
<HR><P>[ <A HREF="CH15.htm">Chapter start</A> ] [ <A HREF="CH15.1.htm">Previous page</A> ] [ <A HREF="CH15.3.htm">Next page</A> ]</P></BODY>
<!--#include file="Copyright.html"--><!--#include file="footer.html"-->
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -