CS 207
Midterm 2
Ondich
Due 11:10 AM Friday, November 12, 1999
For this exam, you may use your textbook, your notes and assignments,
and your brain. You may not use other books, other people, or
Internet resources. If you get stuck, talk to
Jeff Ondich, but please don't talk to anyone else about the exam.
Explain and justify your answers. Submit your answers on paper.
Numbers
1. (10 points) While grading problem 1 of your first midterm, I realized that
I had forgotten how hard it can be to determine whether one 2's
complement integer is larger than another. In most of your
PDP8/E selection sort algorithms, I found code that looked something
like this:
CLA CLL
TAD I PTR
CMA IAC
TAD MAX
SMA
JMP SOMEWHERE
CLA
TAD I PTR
DCA MAX
That is, to determine whether max < a[i], you compared max - a[i] to 0.
If max - a[i] < 0, you reasoned, then max < a[i], and a switch was
warranted. All of you did it that way, and all of you, as a result,
were wrong. In this exercise, you'll find out why.
Throughout this problem, A and B will represent 12-bit two's complement
integers.
2. (10 points) This problem concerns the layout of the
approximately 2^31 different
real numbers that are representable as IEEE 754 32-bit floating point
numbers. All references to "floating point numbers" refer to the
IEEE 32-bit format.
- What is the floating point representation of the number 2? Write
your answer either in 32-bit binary, or 8-digit hexadecimal?
- What number that is exactly representable as an IEEE floating point format
number is closest to 2 (not including 2 itself)? How far apart are
this number and 2? (By how far apart, I mean the absolute value of
the difference between the two numbers.)
- How far apart are 4 and the IEEE representable number that is closest
to 4 (not including 4 itself)?
- How far apart are 1/2 and the IEEE representable number
that is closest to 1/2?
- Do you see a pattern? That is, how far apart are 2^n and the floating
point number closest to 2^n?
- Finally, as a bit of interesting trivia to share with your friends,
what is the smallest positive integer that is not representable as
a floating point number?
Datapaths
3. (20 points) Consider the following very small instruction architecture,
known hereafter as the Insignificantium 1, or I1 for short. The
I1 has 8 16-bit registers, R0 through R7. R0 always has the value 0.
The instructions are 24 bits long, with the following format:
==================================================
| | | | |
| op | A | B | constant C |
| | | | |
| 2 bits | 3 bits | 3 bits | 16 bits |
==================================================
The A and B fields are register numbers, and C is a 16-bit
two's complement integer.
The four instructions are:
Op code | Name | Example | Meaning
=========================================================
0 | ADD | ADD RA, RB, C | RA = RA + RB + C
1 | SUB | SUB RA, RB, C | RA = RA - RB + C
2 | BEQ | BEQ RA, RB, C | if( RA == RB ) PC = PC + C
3 | BNE | BNE RA, RB, C | if( RA != RB ) PC = PC + C
The following code, for example, would multiply 5 by 6, placing the
resulting product in R3:
SUB R1, R1, 5
SUB R2, R2, 6
SUB R3, R3, 0
BEQ R2, R0, 4
ADD R3, R1, 0
ADD R2, R0, -1
BEQ R0, R0, -3
// once you get here, the product is in R3
Your job, should you choose to accept it (which I recommend), is
to design a datapath and the corresponding control to implement
the I1. In particular:
- Draw the simplest single-cycle datapath you can devise to implement
the I1 instruction set. Include control lines.
- For each of the four op-codes, specify the value of each
control line.
- Is there any way to expand the I1 instruction set without
changing the instruction format? How? What parts of your
datapath would have to be changed regardless of the nature of
the new instruction(s)?
4. (10 points) Do exercise 6.9 on page 530 of Patterson and Hennessy.
Educating Jeff
5. (3 points) I like to keep track of pop culture a little bit,
not for the purposes of being hip or hep (or even hyp or hap--regardless
of the vowel chosen, it's a lost cause), but out of mostly morbid
curiosity. So help me out--what should I read or watch or listen to
if I want to know what's happening in Popland these days?
Caches
6. (12 points) Consider the following caches, each of which can
hold up to 16 32-bit words of data. Assume that addresses are
32 bits long.
- A 16-entry direct-mapped cache with 1-word blocks.
- A 4-entry direct-mapped cache with 4-word blocks.
- A 4-entry 4-way set associative cache with 1-word blocks,
using a "least recently used" strategy for choosing which
block to evict.
For each of these caches, answer the following questions.
- Draw a diagram of the cache. How much memory does it use?
- If the contents of
the following addresses are requested in the indicated
order, what words are in which entries at the end, and
what is the hit ratio?
Assume the cache starts out empty.
13, 3, 19, 14, 21, 3, 21, 3, 5, 25, 9, 6, 8, 6, 8, 24, 19