CS61C Spring 2013 Homework 3

TA: Paul Ruan

Due Sunday, March 10th, 2013 @ 11:59pm

Goals

This assignment will cover MIPS coding, floating points, and caches.

Submission

Put all your answers in hw3.txt and findMin.s. Submit your solution by creating a directory named hw3 that contains the file hw3.txt and findMin.s. (File names are case-sensitive and the submission program will not accept your submission if your file names differ at all from those specified) From within that directory, type submit hw3. Partners are not allowed on this assignment.

Copy the contents of ~cs61c/hw/03 to a suitable location in your home directory to obtain files you will want for this homework.

    $  cp -r ~cs61c/hw/03 ~/hw3 

Exercises

Problem 1: C to MIPS - 8pts

Translate the C code into MIPS. Make sure to follow all MIPS conventions. Put your answer in findMin.s. You should run your solution with MARS to test. findMin.s should print "21 -2".

/*
    x is a pointer to a linked list node and is not null.
    Return the min value stored in the linked list.
	
    Assume each node is stored in memory as an int (value) followed by a pointer to the next node (next), each a word wide.
    You must write it with recursion.
*/
int findMin(node *x) {
    if(x->next == NULL)
        return x->value;
    else {
        int min = findMin(x->next);
        if(min < x->value) 
            return min;
        else
            return x->value;
    }
}

Problem 2: Floating Points - 8pts

For the following questions, we will be referring to the IEEE 32-bit floating point representation except with a 5 bit exponent (bias of 2^5/2 - 1 = 15) and a denorm implicit exponent of -14.
  1. Convert -25.25 to floating point format. Write your answer in hexadecimal.
  2. What's the smallest positive integer (an integer has no decimal points) it CANNOT represent? Leave your answer as a power of 2.
  3. What's the smallest positive value it can represent that is not a denorm? Leave your answer as a power of 2. (Does the implicit exponent make sense?)
  4. What's the smallest positive value it can represent? Leave your answer as a power of 2.

Problem 3: Caches - 4pts

Assume we have 8 bit byte-addresses. A very tiny direct-mapped cache holds a total of 32 bytes and each cache block is a word wide.

  1. How many bits are used for the tag?
  2. Which other bytes would share a block with the byte at address 0x85?
  3. The block containing the byte at 0x85 is in the cache. What memory accesses are guaranteed to get a cache miss? You may describe what addresses, but be specific.
  4. The hit time is a clock cycle, and the miss penalty is 100. If the miss rate is 50%, what is the AMAT?

Problem 4: Cache Memory Accesses (from P&H Computer Org. & Design) - 5pts

The following C program is run (with no optimizations) on a processor with a direct-mapped cache that has eight-word (32-byte) blocks and holds 256 words of data:

int i,j,c,stride,array[512];
...
for(i=0; i<10000; i++)
    for (j=0; j<512; j+=stride)
        c += i%(array[j]);

If we consider only the cache activity generated by references to the array and we assume that integers are words, what possible miss rates (there may be multiple) can we expect

  1. if stride = 256?
  2. if stride = 255?
Explain your answers clearly in a few sentences.