CPSC 330 - Spring 2006
Homework 1
Due by class time on Monday, January 30
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.
Purpose:
(1) work with units and prefixes;
(2) work with Amdahl's Law;
(3) work with the execution time equation, CPI, and MIPS
Note:
For main memory size, interpret K, M, and G as powers of two.
Otherwise, interpret K, M, and G as powers of ten.
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
1. 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 ________
1994 PPC 601 100 MHz 10 nsec
1998 PPC 750 ________ 3 nsec
2000 AMD Athlon 1 GHz 1 nsec
2004 PPC 970 2.5 GHz ________
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
2. 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?
3. 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:
Consider a vector computer in which vector mode can provide a speedup of 20.
(a) What is the overall speedup for various percentages of vectorization?
vector speedup = 20
percent vectorization = 10% 20% 30% 40% 50% 60% 70% 80% 90%
overall speedup = 1.1 1.2 1.4 1.6 1.9 2.3 3.0 4.2 6.9
(b) What amount of vectorization is required for an overall speedup of 2?
2 = 1/( 1-f + f/20 ) solving this yields f = .526
(c) What amount of vectorization is required for an overall speedup of 10?
10 = 1/( 1-f + f/20 ) solving this yields f = .947
4. Consider an enhancement to a computer system that provides a three times
speedup when in use. What is the overall speedup if the enhancement can
only be used for one half of a program's original execution time?
5. Consider an enhancement to a computer system that provides a two times
speedup when in use. What is the overall speedup if the enhancement is
measured to be used for one half of a program's _enhanced_ execution time?
(The new execution time is measured rather than the old.)
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.
What is the MIPS value?
exec. time = IC * CPI * CCT = 30M insts. * 2 cycles/inst * 33.3 nsec/cycle
= 1.998 seconds = 2 seconds (rounded)
MIPS = insts./ (execution time * 10^6) = 30M insts. / 2*10^6 seconds
= 15 MIPS
6. (a) What is the execution time for a program that executes 10 billion
instructions on a processor with an avg. CPI of 5.0 and a clock rate
of 2 GHz?
(b) What is the MIPS value?
Example:
For the following instruction set workload and cycle values, find the
average CPI. If the clock rate is 100 MHz, what is the MIPS value?
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
MIPS = clock rate / (CPI * 10^6) = 100 MHz / 4*10^6 cycles/inst.
= 100 / 4 = 25 MIPS
7. Consider the following instruction set workload and cycle values.
type | freq cycles
-------+--------------
alu | 0.5 1
branch | 0.2 2
ld/st | 0.3 5
(a) What is the average CPI?
(b) If the clock rate is 2.4 GHz, what is the MIPS value?
(c) Consider a proposed change in processor design in which the clock
rate can be increased to 3.6 GHz but the CPI values have to change
to those in the table below. Is the proposed design faster than
the original design in part (b)? If so, by what factor?
type | freq cycles
-------+--------------
alu | 0.5 1
branch | 0.2 5
ld/st | 0.3 11
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?