CS207 Midterm 2, Fall 1999

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.

Give an example of two 12-bit two's complement integers A and B such that A - B < 0, but A >= B. By A - B, I mean the 12-bit sum of A and the two's complement of B.

Complete the following chart, where 0 stands for False, and 1 stands for True.


A < 0?  |  B < 0?  |  A - B < 0?  ||  A < B? 
=============================================
    0   |    0     |      0       ||
    0   |    0     |      1       ||
    0   |    1     |      0       ||
    0   |    1     |      1       ||
    1   |    0     |      0       ||
    1   |    0     |      1       ||
    1   |    1     |      0       ||
    1   |    1     |      1       ||

Write a pseudo-code algorithm for testing whether A < B.

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