CPSC 330 - Fall 2006
Homework 1
REVISED: Due by class time on Friday, September 15
Each student must turn in a separate set of homework solutions, but you may
work together in study groups with other students from the class. Include
their names in parentheses under your name on the solution set you submit.
Purposes:
(1) selected historical questions;
(2) work with units and prefixes;
(3) work with the execution time equation and CPI;
(4) work with combinational logic;
(5) work with sequential logic.
Note:
For main memory size, interpret K, M, and G as powers of two.
Otherwise, interpret K, M, and G as powers of ten.
1. Name three computer organization attributes that are non-von-Neumann.
2. Define the term "minicomputer", as it would have been understood in
1980. To what market niche, if any, would that term correspond today?
Explain your answer.
3. Briefly state Moore's Law.
Example:
For a processor with 100 MHz clock frequency (a.k.a. clock rate),
what is the clock cycle time?
CCT = 1 / clock rate = 1 / ( 100 * 10^6 cycles per sec )
= 10 / 10^9 secs per cycle = 10 nsec
4. Clock cycle time (or clock period) is the reciprocal of clock frequency.
Fill in the following table.
clock clock
year processor frequency cycle time
1949 EDSAC 500 KHz ________
1978 Intel 8086 ________ 200 nsec
1993 Intel Pentium 66 MHz ________
1998 PPC 750 ________ 3 nsec
2000 AMD Athlon 1 GHz 1 nsec
2004 Intel Pentium 4 3.6 GHz ________
Example:
Consider making a complete backup of a full 40 GB hard drive using a
250 MB zip drive. How many 250 MB zip disks will be needed?
Use powers of ten for capacities other than main memory.
# of zip disks = 40 GB / 250 MB = 4*10^10 / 2.5*10^8 = 160
5. A keychain storage device (jump drive) writes at 0.85 MB/sec. How long
will it take to transfer a 4.25 MB file to the device?
6. Consider a weather prediction model with the following dimensions
120 x 120 2-dimensional grid points, 45 vertical layers
a) If each grid point in each layer requires 1,000 instructions to perform
the necessary calculations for one time step, how many total instructions
are required for the model to run for 100 time steps?
b) If a computer can process 2 billion instructions per second (2000 MIPS),
how long will the model take to run those 100 time steps?
c) If the model resolution is increased to 320 x 320 2-dimensional grid
points and 60 vertical layers, how long will the model take to run 100
time steps?
Example:
Find the execution time for a program that executes 30 million instructions
on a processor with an avg. CPI of 2.0 and a clock cycle time of 33.3 nsec.
exec. time = IC * CPI * CCT = 30M insts. * 2 cycles/inst * 33.3 nsec/cycle
= 1.998 seconds = 2 seconds (rounded)
7. What is the execution time for a program that executes 10 billion
instructions on a processor with an avg. CPI of 3.0 and a clock rate
of 2.5 GHz?
Example:
For the following instruction set workload and cycle values, find the
average CPI.
type | freq cycles
-------+--------------
alu | 0.5 2
branch | 0.2 6
ld/st | 0.3 6
avg. CPI = (0.5 * 2) + (0.2 * 6) + (0.3 * 6) = 4.0
8. A current 1.0 GHz computer design has the following workload and CPI
characteristics
type | freq cycles
-----+--------------
A | 0.4 2
B | 0.25 3
C | 0.25 3
D | 0.1 5
A set of proposed improvements would result in a 1.5 GHz computer with
improved CPI values
type | freq cycles
-----+--------------
A | 0.4 2
B | 0.25 2
C | 0.25 3
D | 0.1 4
What is the overall speedup of the proposed improvements?
9. Problem 1.5(a) on page 23 of your text.
10. Problem 1.6(a) and (b) on page 23 of your text.
Example:
Consider A*( (~A) + B ) = A*B. Show by truth table that this is true.
A B | ~A | ~A + B | A*(~A+B) | A*B
-----+----+--------+----------+-----
0 0 | 1 | 1 | 0 | 0
0 1 | 1 | 1 | 0 | 0
1 0 | 0 | 0 | 0 | 0 true because the last
1 1 | 0 | 1 | 1 | 1 two columns are the same
Show by algebraic manipulation that this is true.
A*( (~A) + B )
= A*(~A) + A*B by distributive postulate
= 0 + A*B by inverse postulate
= A*B by identity postulate
11. Problem A.2(b) on page 724 of your text.
Example:
\BC
A\ 00 01 11 10
+----+----+----+----+ _ _ _ _ _ _ _ _
0 | 1 | 1 | 0 | 0 | sum of products = A*B*C + A*B*C + A*B*C + A*B*C
+----+----+----+----+ _
1 | 1 | d | d | 1 | don't cares = A*B*C + A*B*C
+----+----+----+----+
_
minimal sum of products = A + B
12. Problem A.3 on page 725 of your text -- use Karnaugh maps.
Example
Design a 2-input circuit that gives an output of 1 only when the two
inputs are equal. First, show the truth table; and, second, show the
gate implementation.
A B | F in SOP form, A----*-----.
----+-- _ _ | AND-.
0 0 | 1 F = A*B + A*B B-*--------' | _ _
0 1 | 0 | | OR = A*B + A*B
1 0 | 0 | `-NOT-. |
1 1 | 1 | AND-'
`----NOT-'
13. A majority function is implemented by a combinational circuit when the
output is one if and only if the input variables have more ones than
zeros. Otherwise, the output is zero. Design a 3-input majority
function. First, show the truth table. Second, show the gate
implementation using AND, OR, and NOT gates.
Example
Consider again the equality function F= A*B + (~A)*(~B). Implement
this expression using one OR gate and two NAND gates.
A. check: __________
NAND-. _____________ __ ____ ____
B' | _____ A B | AB AB A+B | (AB)*(A+B) (AB)*(A+B)
NAND = (A*B) * (A+B) ----+-----------+----------------------
A. | 0 0 | 0 1 0 | 0 1
OR---' 0 1 | 0 1 1 | 1 0
B' 1 0 | 0 1 1 | 1 0
1 1 | 1 0 1 | 0 1
14. Problem A.13 on page 726 of your text.
Example
A sequential circuit has one D flip-flop, two inputs X and Y, and one
output A. The combinational logic consists of two cascaded xor gates
with the output of the second gate being used as the next state.
A = Q(t)
D_in = Q(t) xor (X xor Y)
.--------------------------.
| |
| +-----+ |
+-----+ `-->| | D_in +---+ Q |
X--->| | | xor |------->| |---*-----> A
| xor |------>| | | D |
Y--->| | +-----+ CLK->| |
+-----+ +---+
The truth table for this circuit is
current next
inputs state output state
X Y Q(t) | X xor Y | A D_in == Q(t+1)
---------------+-----------+-----------------------
0 0 0 | 0 | 0 0 0
0 0 1 | 0 | 1 1 1
0 1 0 | 1 | 0 1 1
0 1 1 | 1 | 1 0 0
1 0 0 | 1 | 0 1 1
1 0 1 | 1 | 1 0 0
1 1 0 | 0 | 0 0 0
1 1 1 | 0 | 1 1 1
or you may find it easier to order the table with the current state
listed first (the tables are equivalent)
current next
state inputs output state
Q(t) X Y | X xor Y | A D_in == Q(t+1)
----------------+-----------+-----------------------
0 0 0 | 0 | 0 0 0
0 0 1 | 1 | 0 1 1
0 1 0 | 1 | 0 1 1
0 1 1 | 0 | 0 0 0
1 0 0 | 0 | 1 1 1
1 0 1 | 1 | 1 0 0
1 1 0 | 1 | 1 0 0
1 1 1 | 0 | 1 1 1
The state diagram for this circuit as a Moore machine (where the
outputs are associated with the states) is:
01,10
.---. .-----------. .---.
/ v.===./ v.===./ \
00,11 | |0/0| |1/1| | 00,11
\ /`==='^ /`==='^ /
`---' `-----------' `---'
01,10
(Note that a part of this circuit is essentially a T flip-flop.)
15. Problem A.38 on page 731 of your text.