CDA3101 F13 Exam1 ANSWERKEY

CDA 3101 Midterm Exam #1 Fall 2013
PRINT YOUR NAME: __________KEY____________ UFID [5:8]: ____________
RECITATION Date/Time: ________________ Your CDA3101 Number: ____________
I have not looked at anyone else’s paper, and I have not obtained unauthorized help in
completing this exam. Also, I have adhered to and upheld all standards of honesty as
stated in the University Honesty Policy and in the course syllabus.
YOUR SIGNATURE: ____________________________ DATE: _________________
YOU ARE ALLOWED TO HAVE ONLY THE FOLLOWING ON YOUR DESK OR

WORKTABLE:
1. A HANDWRITTEN CRIB SHEET 8-1/2 x 11 inches (BOTH SIDES USABLE)

2. A BASIC CALCULATOR – NO GRAPHING, NO PROGRAMMABILITY
3. YOUR PEN OR PENCIL AND AN ERASER
ALL OTHER OF YOUR BELONGINGS BROUGHT INTO THE CLASSROOM MUST

BE ON THE FLOOR, UNLESS YOU REQUIRE EYEGLASSES OR AN OPTICAL
MAGNIFYING GLASS.
PLEASE TURN ALL CELL PHONES, iPHONES, iPADS, AND

OTHER ELECTRONIC DEVICES (EXCEPT CALCULATORS),
OFF AND PUT THEM AWAY – RINGTONES AND CELL
PHONE CONVERSATIONS NOT PERMITTED DURING EXAM.
PRINT YOUR NAME: _________KEY____________ CDA3101 NUMBER: ___________
SCORES: TOTAL EXAM SCORE: ____ / 120 pts This part for Instructor & TAs only.
Q1: ____ Q2: ____ Q3: ____ Q4: ____ Q5: ____ EC-1: ____ EC-2: ____
This exam has six regular questions and one extra-credit question. Complete the questions
that are easiest for you first, then complete what you can of the difficult questions. There is
no penalty for guessing. However, on questions involving calculation, you must show your
work. If you do not show your work, you risk getting only partial credit for any answer.
Q1. (25 pts) Define the following terms using 1-3 sentences or a formula (5 pts each):
(a) Moore’s Law

Moore's law is the observation that, over thehistory of computing hardware, the number
oftransistors on integrated circuits doubles approximately every two years. The period
often quoted as "18 months" is due to Intel executive David House, who predicted that
period for a doubling in chip performance (being a combination of the effect of more
transistors and their being faster).
[Source: http://en.wikipedia.org/wiki/Moore's_law]
(b) Datapath
Part of a computer that does the work of arithmetic and logic calculations and performs
other instructions including but not limited to I/O and branching.
(c) Benchmark
In computing, a benchmark is the act of running a computer program, a set of programs,
or other operations, in order to assess the relative performance of an object, normally by
running a number of standard tests and trials against it. The term 'benchmark' is also
mostly utilized for the purposes of elaborately-designed benchmarking programs
themselves. [Source: http://en.wikipedia.org/wiki/Benchmark_(computing) ]
(d) Von Neumann Bottleneck

The meaning of the term [“von Neumann architecture”] has evolved to mean a stored-
program computer in which an instruction fetch and a data operation cannot occur at the
same time because they share a common bus. This is referred to as the Von Neumann
bottleneck and often limits the performance of the system.
[Source: http://en.wikipedia.org/wiki/Von_Neumann_architecture ]
(e) Register (in a CPU chip)

In computer architecture, a processor register is a small amount of storage available as
part of a CPU or other digital processor. Such registers are (typically) addressed by
mechanisms other than main memory and can be accessed more quickly.
[Source: http://en.wikipedia.org/wiki/Processor_register]
PRINT YOUR NAME: ______KEY_______________ CDA3101 NUMBER: ___________
Q2. (25 pts) Given the following parameters, answer each of the following two questions
for the program P1 on machine M1 (10 pts for 2.1, 15 pts for 2.2):
Instruction Count = 26,395 Average CPI = 2.17

Clock Rate = 3.24 GHz
2.1) Calculate the execution time texe for P1 on M1 (show all work):
texe = IC  CPI  tclock = IC  CPI  (clock_rate)-1

= 26,395 instr  2.17 cycles/instr  (3.24 Gcycles/sec)-1
~ 17,678 x 10-9 sec ~ 17.7 microseconds
2.2) If M1 runs program P2 2.9 times faster than P1 with clock rate and CPI remaining
the same as in 2.1, above, then what variable in the performance equation changed,
and by how much? (Answer using analysis, and show all work to get full credit):
If CPI and clock rate are unchanged, then the remaining variable is IC.
For P2 to run 2.9 times faster, the runtime must be 1 / 2.9 ~ 0.345 that of P1.
This means that IC of P2 must be 0.345 times the IC of P1, so we have
IC(P2) ~ 0.345  IC(P1) = 0.345  26,395 ~ 9,102 instructions
Q3. (30 pts) Diagram and give an example of each of the following MIPS instruction
formats, then tell what each format is used for: (10 pts each)
R-format: ► Used for arithmetic and logic operations

► Ex: add $t0, $s1 $s2 # t0  s1 + s2
I-format: ► Used for load/store, conditional branch, and arithmetic/logic operations

with a constant
► Ex: addi $t0, $s1, 24 # t0  s1 + 24
J-format: ► Used for unconditional branch

► Ex: j Loop # transfer control to statement with label “Loop”
► Diagram for R,I, and J formats at http://www.cise.ufl.edu/~mssz/CompOrg/Figure2.7-

MIPSinstrFmt.gif
PRINT YOUR NAME: _______KEY______________ CDA3101 NUMBER: ___________
Q4. (20 pts) A computer M2 has the following CPIs for instruction types A thru D, and a
program P3 has the following mix of instructions (Note: pct = percent):
M2: Type A CPIA = 1.7 Type B CPIB = 2.1 Type C CPIC = 2.7 Type D CPID = 2.4
P3: Type A = 22 pct Type B = 29 pct Type C = 17 pct Type D = remaining pct
4.1 (10 pts) Calculate the average CPI of Machine M2:
CPIave = i = A..D (CPIi  fractioni)

= 1.7(0.22) + 2.1(0.29) + 2.7(0.17) + 2.4(0.32)
= 0.374 + 0.609 + 0.459 + 0.768
= 2.21
4.2 (10 pts) Calculate the runtime of P3 on M2 if IC = 22,311 and clock rate is 3.3 GHz:
texe = IC  CPI  tclock = IC  CPI  (clock_rate)-1

= 22,311 instr  2.21 cycles/instr  (3.3 Gcycles/sec)-1
~ 14,942 x 10-9 sec ~ 14.9 microseconds
Q5. (20 pts) This question has two parts: 5.1 and 5.2. Explain in detail to get full credit.
5.1) What are the best benchmarks to use, and why? (10 pts)
The best benchmarks are the real programs you plan to run on a given computer.
Measuring the runtime of these programs will measure your actual workload.
452) What are SPEC CPU benchmarks about? Why was SPEC2000 CPU benchmark
suite retired? (5 pts each)
SPEC (Standard Performance Evaluation Corporation) is a non-profit organization that

aims to "produce, establish, maintain and endorse a standardized set" of performance
benchmarks for computers. The benchmarks aim to test "real-life" situations.
[Source: http://en.wikipedia.org/wiki/Standard_Performance_Evaluation_Corporation ]
SPEC CPU2000 benchmark suite was retired because (a) it no longer was found to
represent the actual workload(s) on most machines after 2006, and (b) the SPEC
CPU2006 benchmark suite superseded CPU2000.
PRINT YOUR NAME: ________KEY___________ CDA3101 NUMBER: ___________
Extra Credit Problems:
EC-1. (20 pts) Given a computer M4 with clock rate = 3.1 GHz and a hardware accelerator
that can make Type A instructions go 7 times faster, answer the following:
EC-1.1 (7 pts) If a program P4 has 29 pct Type A instructions and the remainder are
Type B instructions, and its IC = 35,450 – will the accelerator make P4 run at least 2
times faster on M4 than it would without an accelerator? SHOW ALL WORK
From givens: (1) factor of improvement fI = 7;

(2) fraction of system improved or enhanced fE = 0.29
What is the limiting (maximum) speedup in this case?
If runtime t = 1 before accelerator was used, then runtime after

accelerator is used is given by
tA = (1 – fE) + ( fE / fI ) = 0.71 + (0.29 / 7) ~ 0.751
So max. speedup is calculated as

max = t / tA = 1 / 0.751 ~ 1.33 times < 2 times
As a result, the two-fold system speedup cannot be achieved.
EC-1.2 (13 pts) Use Amdahl’s Law to determine how much faster the accelerator
needs to go to make P4 run 5.5 times faster on M4 (with accelerator) than it did without
an accelerator. SHOW ALL WORK
Suppose the accelerator was infinitely fast (as fast as it can go!!).
Then, 0.71 of the program would not be speeded up, so the limiting
speedup in this case would be
   max = t / tA = 1 / 0.71 ~ 1.408 times < 5.5 times
This speedup cannot be achieved, for the same general reason as in EC-1.1.
EC-2. (10 pts) Give two examples from MIPS ISA of the design principle “SIMPLICITY
FAVORS REGULARITY” EXPLAIN IN DETAIL (5 pts each)
Example 1: MIPS has a regular instruction format (32 bits per instruction, 6-bit opcode
for all instructions, etc.) which makes decoding simpler (and faster).
Example 2: MIPS has 32-bit registers only, instead of the multiple register sizes in
CISC architectures like Intel x86. This makes hardware design simpler.

CDA3101 F13 Exam1 ANSWERKEY

Uploaded by

Copyright:

Available Formats

CDA3101 F13 Exam1 ANSWERKEY

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

CDA3101 F13 Exam1 ANSWERKEY

Uploaded by

Copyright:

Available Formats

CDA 3101 Midterm Exam #1 Fall 2013

PRINT YOUR NAME: __________KEY____________ UFID [5:8]: ____________

RECITATION Date/Time: ________________ Your CDA3101 Number: ____________

YOUR SIGNATURE: ____________________________ DATE: _________________

YOU ARE ALLOWED TO HAVE ONLY THE FOLLOWING ON YOUR DESK OR

1. A HANDWRITTEN CRIB SHEET 8-1/2 x 11 inches (BOTH SIDES USABLE)

ALL OTHER OF YOUR BELONGINGS BROUGHT INTO THE CLASSROOM MUST

PLEASE TURN ALL CELL PHONES, iPHONES, iPADS, AND

PRINT YOUR NAME: _________KEY____________ CDA3101 NUMBER: ___________

(a) Moore’s Law

(d) Von Neumann Bottleneck

(e) Register (in a CPU chip)

PRINT YOUR NAME: ______KEY_______________ CDA3101 NUMBER: ___________

Instruction Count = 26,395 Average CPI = 2.17

texe = IC  CPI  tclock = IC  CPI  (clock_rate)-1

R-format: ► Used for arithmetic and logic operations

I-format: ► Used for load/store, conditional branch, and arithmetic/logic operations

J-format: ► Used for unconditional branch

► Diagram for R,I, and J formats at http://www.cise.ufl.edu/~mssz/CompOrg/Figure2.7-

PRINT YOUR NAME: _______KEY______________ CDA3101 NUMBER: ___________

4.1 (10 pts) Calculate the average CPI of Machine M2:

CPIave = i = A..D (CPIi  fractioni)

texe = IC  CPI  tclock = IC  CPI  (clock_rate)-1

SPEC (Standard Performance Evaluation Corporation) is a non-profit organization that

PRINT YOUR NAME: ________KEY___________ CDA3101 NUMBER: ___________

Extra Credit Problems:

From givens: (1) factor of improvement fI = 7;

What is the limiting (maximum) speedup in this case?

If runtime t = 1 before accelerator was used, then runtime after

So max. speedup is calculated as

As a result, the two-fold system speedup cannot be achieved.

You might also like

PRINT YOUR NAME: KEY UFID [5:8]: __

RECITATION Date/Time: ____ Your CDA3101 Number:

YOUR SIGNATURE: ____________ DATE: _

PRINT YOUR NAME: _KEY CDA3101 NUMBER: ___

PRINT YOUR NAME: KEY_ CDA3101 NUMBER: ___

PRINT YOUR NAME: _KEY CDA3101 NUMBER: ___

PRINT YOUR NAME: __KEY_ CDA3101 NUMBER: _______