📄 ch15.9.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.9 Problems</TITLE></HEAD><!--#include file="top.html"--><!--#include file="header.html"-->
<DIV>
<P>[ <A HREF="CH15.htm">Chapter start</A> ] [ <A HREF="CH15.8.htm">Previous page</A> ] [ <A HREF="CH15.a.htm">Next page</A> ]</P><!--#include file="AmazonAsic.html"--><HR></DIV>
<H1 CLASS="Heading1">
<A NAME="pgfId=176259">
</A>
15.9 <A NAME="35104">
</A>
Problems</H1>
<P CLASS="Exercise">
<A NAME="pgfId=184010">
</A>
* = Difficult, ** = Very difficult, *** = Extremely difficult</P>
<P CLASS="ExerciseHeadFirst">
<A NAME="pgfId=184011">
</A>
15.1 (Complexity, 10 min.) Suppose the workstations we use to design ASICs increase in power (measured in MIPS—a million instructions per second) by a factor of 2 every year. If we want to keep the length of time to solve an ASIC design problem fixed, calculate how much larger chips can get each year if constrained by an algorithm with the following complexities:</P>
<UL>
<LI CLASS="ExercisePartFirst">
<A NAME="pgfId=184012">
</A>
a. O<SPAN CLASS="EquationVariables">
(k). </SPAN>
</LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=184013">
</A>
b. O<SPAN CLASS="EquationVariables">
(n).</SPAN>
</LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=184014">
</A>
c. O(log<SPAN CLASS="EquationVariables">
n</SPAN>
). </LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=184015">
</A>
d. O(<SPAN CLASS="EquationVariables">
n</SPAN>
log<SPAN CLASS="EquationVariables">
n</SPAN>
). </LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=184016">
</A>
e. O(<SPAN CLASS="EquationVariables">
n</SPAN>
<SUP CLASS="Superscript">
2</SUP>
).</LI>
</UL>
<P CLASS="ExerciseHead">
<A NAME="pgfId=184017">
</A>
15.2 (Complexity, 10 min.) In a film the main character looks 12 moves ahead to win a chess championship. </P>
<UL>
<LI CLASS="ExercisePartFirst">
<A NAME="pgfId=184018">
</A>
a. Estimate (stating your assumptions) the number of possible chess moves looking 12 moves ahead.</LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=184019">
</A>
b. How long would it take to evaluate all these moves on a modern workstation?</LI>
</UL>
<P CLASS="ExerciseHead">
<A NAME="pgfId=184021">
</A>
15.3 <A NAME="13829">
</A>
(Chips and towns, 20 min.) This problem is adapted from an analogy credited to Chuck <A NAME="marker=184022">
</A>
Seitz. Complete the entries in <A HREF="CH15.9.htm#16714" CLASS="XRef">
Table 15.8</A>
, which shows the progression of integrated circuit complexity using the analogy of town and city planning. If <SPAN CLASS="Symbol">
l</SPAN>
is half the minimum feature size, assume that a transistor is a square 2 <SPAN CLASS="Symbol">
l</SPAN>
on a side and is equivalent to a city block (which we estimate at 200 m on a side). </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="7">
<P CLASS="TableTitle">
<A NAME="pgfId=184029">
</A>
TABLE 15.8 <A NAME="16714">
</A>
Complexity of ASICs (Problems <A HREF="CH15.9.htm#13829" CLASS="XRef">
15.3</A>
and <A HREF="CH15.9.htm#25957" CLASS="XRef">
15.4</A>
).</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLeft">
<A NAME="pgfId=188707">
</A>
<SPAN CLASS="TableHeads">
Year</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=188709">
</A>
<SPAN CLASS="Symbol">
l</SPAN>
<SPAN CLASS="TableHeads">
/ </SPAN>
<SPAN CLASS="Symbol">
m</SPAN>
<SPAN CLASS="TableHeads">
m</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=188711">
</A>
<SPAN CLASS="TableHeads">
Chip size</SPAN>
</P>
<P CLASS="Table">
<A NAME="pgfId=188712">
</A>
<SPAN CLASS="TableHeads">
(mm on a side)</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=188714">
</A>
<SPAN CLASS="TableHeads">
Transistor size</SPAN>
</P>
<P CLASS="Table">
<A NAME="pgfId=188715">
</A>
<SPAN CLASS="TableHeads">
( </SPAN>
<SPAN CLASS="Symbol">
m</SPAN>
<SPAN CLASS="TableHeads">
m on a side)</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=188717">
</A>
<SPAN CLASS="TableHeads">
Transistors = city blocks</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=188719">
</A>
<SPAN CLASS="TableHeads">
City size</SPAN>
</P>
<P CLASS="Table">
<A NAME="pgfId=188720">
</A>
<SPAN CLASS="TableHeads">
(km on a side,</SPAN>
</P>
<P CLASS="Table">
<A NAME="pgfId=188721">
</A>
<SPAN CLASS="TableHeads">
1 block = 200m)</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=188723">
</A>
<SPAN CLASS="TableHeads">
Example</SPAN>
</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=184064">
</A>
1970</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=184066">
</A>
50</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=184068">
</A>
5</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=184070">
</A>
200</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=184072">
</A>
25 <SPAN CLASS="Symbol">
¥</SPAN>
25 = 625</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=184074">
</A>
5</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=184076">
</A>
Palo Alto</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=184078">
</A>
1980</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=184080">
</A>
5</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=184082">
</A>
10</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=184084">
</A>
20</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=184086">
</A>
500 <SPAN CLASS="Symbol">
¥</SPAN>
500 = 25 <SPAN CLASS="Symbol">
¥</SPAN>
10<SUP CLASS="Superscript">
3</SUP>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=184088">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=184090">
</A>
</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=184092">
</A>
1990</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=184094">
</A>
0.5</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=184096">
</A>
20</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=184098">
</A>
1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=184100">
</A>
1,000 <SPAN CLASS="Symbol">
¥</SPAN>
1,000 = 1 <SPAN CLASS="Symbol">
¥</SPAN>
10<SUP CLASS="Superscript">
6</SUP>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=184102">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=184104">
</A>
</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=184106">
</A>
2000</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=184108">
</A>
0.05</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=184110">
</A>
40</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=184112">
</A>
0.2 </P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=184114">
</A>
20,000 <SPAN CLASS="Symbol">
¥</SPAN>
20,000 = 400 <SPAN CLASS="Symbol">
¥</SPAN>
10<SUP CLASS="Superscript">
6</SUP>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=184116">
</A>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=184118">
</A>
</P>
</TD>
</TR>
</TABLE>
<P CLASS="ExerciseHead">
<A NAME="pgfId=184215">
</A>
15.4 <A NAME="25957">
</A>
(Polygons, 10 min.) Estimate (stating and explaining all your assumptions) how many polygons there are on the layouts for each of the chips in <A HREF="CH15.9.htm#16714" CLASS="XRef">
Table 15.8</A>
.</P>
<P CLASS="ExerciseHead">
<A NAME="pgfId=184219">
</A>
15.5 (Algorithm complexity, 10 min.) I think of a number between 1 and 100. You guess the number and I shall tell you whether you are high or low. We then repeat the process. If you were to write a computer program to play this game, what would be the complexity of your algorithm?</P>
<P CLASS="ExerciseHead">
<A NAME="pgfId=184220">
</A>
15.6 (Algorithms, 60 min.) For each of these problems write or find (stating your source) an algorithm to solve the problem:</P>
<UL>
<LI CLASS="ExercisePartFirst">
<A NAME="pgfId=184221">
</A>
a. An algorithm to sort <SPAN CLASS="EquationVariables">
n</SPAN>
numbers.</LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=184222">
</A>
b. An algorithm to discover whether a number <SPAN CLASS="EquationVariables">
n</SPAN>
is prime.</LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=184223">
</A>
c. An algorithm to generate a random number between 1 and <SPAN CLASS="EquationVariables">
n</SPAN>
.</LI>
</UL>
<P CLASS="Exercise">
<A NAME="pgfId=184224">
</A>
List the algorithm using a sequence of steps, pseudocode, or a flow chart. What is the complexity of each algorithm?</P>
<P CLASS="ExerciseHead">
<A NAME="pgfId=184225">
</A>
15.7 (Measurement, 30 min.) The traveling-salesman problem is a well-known example of an NP-complete problem (you have a list of cities and their locations and you have to find the shortest route between them, visiting each only once). Propose a simple measure to estimate the length of the solution. If I had to visit the 50 capitals of the United States, what is your estimate of my frequent-flyer mileage?</P>
<P CLASS="ExerciseHead">
<A NAME="pgfId=184226">
</A>
15.8 (Construction, 30 min.) Try and make a quantitative comparison (stating and explaining all your assumptions) of the difficulty and complexity of construction (for example, how many components in each?) for each of the following: a Boeing 747 jumbo jet, the space shuttle, and an Intel Pentium microprocessor. Which, in your estimation, is the most complex and why? Smailagic [<A NAME="Smailagic95">
</A>
1995] proposes measures of design and construction complexity in a description of the wearable computer project at Carnegie-Mellon University.</P>
<P CLASS="ExerciseHead">
<A NAME="pgfId=184228">
</A>
15.9 (Productivity, 20 min.). If I have six months to design an ASIC:</P>
<UL>
<LI CLASS="ExercisePartFirst">
<A NAME="pgfId=184229">
</A>
a. What is the productivity (in transistors/day) required for each of the chips in <A HREF="CH15.9.htm#16714" CLASS="XRef">
Table 15.8</A>
?</LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=184233">
</A>
b. What does this translate to in terms of a productivity increase (measured in percent increase in productivity per month)?</LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=184235">
</A>
c. <A NAME="marker=184234">
</A>
Moore’s Law says that chip sizes double every 18 months. What does this correspond to in terms of a percentage increase per month?</LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=184236">
</A>
d. Comment on your answers.</LI>
</UL>
<P CLASS="ExerciseHeadFirst">
<A NAME="pgfId=176261">
</A>
15.10 <A NAME="42413">
</A>
(Graphs and edges, 30 min.) We know a net with two connections requires a single edge in the network graph, a net with three connections requires three edges, and a net with four connections requires six edges.</P>
<UL>
<LI CLASS="ExercisePartFirst">
<A NAME="pgfId=13099">
</A>
a. Can you guess a formula for the number of edges in the network graph corresponding to a net with <SPAN CLASS="EquationVariables">
n</SPAN>
connections?</LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=15578">
</A>
b. Can you prove the formula you guessed in part a? <SPAN CLASS="Emphasis">
Hint:</SPAN>
How many edges are there from one node to <SPAN CLASS="EquationVariables">
n</SPAN>
– 1 other nodes?</LI>
<LI CLASS="ExercisePart">
<A NAME="pgfId=13074">
</A>
c. Large nets cause problems for partitioning algorithms based on a connectivity matrix (edges rather than wires). Suppose we have a 50-net connection that is no more critical for timing than any other net. Suggest a way to fool the partitioning algorithm so this net does not drag all its logic cells into one partition.</LI>
</UL>
<P CLASS="Exercise">
<A NAME="pgfId=13104">
</A>
Most CAD programs treat large nets (like the clock, reset, or power nets) separately, but the nets are required to have special names and you only can have a limited number of them. The average net in an ASIC has between two and four connections and as a rule of thumb 80 percent of nets have a fanout of 4 or less (a fanout of 4 means a gate drives four others, making a total of five connections on the net).</P>
<P CLASS="ExerciseHead">
<A NAME="pgfId=16699">
</A>
15.11 <A NAME="32235">
</A>
(PC partitioning, 60 min.) Open an IBM-compatible PC, Apple Macintosh, or PowerPC that has a motherboard that you can see easily. Make a list of the chips (manufacturer and type), their packages, and pin counts. Make intelligent guesses as to the function of most of the chips. Obviously manufacturer’s logos and chip identification markings help—perhaps they are in a data book. Identify the types of packages (pin-grid array, quad flat pack). Look for nearby components that may give a hint—crystals for clock generators or the video subsystem. Where are the chips located on the board—are they near the connectors for the floppy disk subsystem, the modem or serial port, or video output? To help you, <A HREF="CH15.9.htm#16295" CLASS="XRef">
Table 15.9</A>
shows an example—a list of the first row of chips on an old H-P Vectra ES/12 motherboard. Use the same format for your list. </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="5">
<P CLASS="TableTitle">
<A NAME="pgfId=80360">
</A>
TABLE 15.9 <A NAME="16295">
</A>
A list of the chips on the first row of an HP Vectra PC (Problem <A HREF="CH15.9.htm#32235" CLASS="XRef">
15.11</A>
).</P>
</TD>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -