CS61C Spring 2014 Homework 3

TA: Alan Christopher

Due Sunday, March 2nd, 2014 @ 23:59:59

Updates/Clarifications

Goals

This assignment will cover MIPS coding, floating point numbers, and caches.

Submission

Put all your answers in hw3.txt and curry.s. Submit your solution by creating a directory named hw3 that contains the file hw3.txt and curry.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: Curried MIPS - 8pts

First, a bit of friendly advice. This is a fun problem to work on, and a great learning opportunity, but it's also definitely the lion's share of the work for this homework. If you've got an unusually heavy load this week I'd recommend completing the questions after this one first.

Currying is an idea present in some functional languages that allows us to think of all functions as functions of a single variable. It works by thinking of a function (x1,x2,x3,...,xn)-->y as a function x1-->(x2-->(x3-->...(xn-->y)...)). That is, instead of mapping from n inputs to our output all at once, we map from one input to another function of one input, and so on until we get to the last input, which maps to the actual output. For concreteness we've implemented a function asCurryable2() in python, which maps from a normal 2-argument python function to one which can be curried. We've also shown how it might be used on some sample inputs. 

>>> from math import pow
>>> def asCurryable2(f):
>>>     return lambda (x) : lambda (y) : f(x,y);
>>> p = asCurryable2(pow)
>>> pow(2, 4)
16.0
>>> p(2)(4)
16.0
Your task is to do this in MIPS. Implement asCurryable in curry.s so that given a pointer to a destination buffer, a pointer to a function f() to be curryable-ized, and the number of arguments that f() will fill in the destination buffer with code for the curryable function. To make things a little easier we'll assume that the number of arguments will be somewhere between one and four.

We'll also require that our curryable-ized functions don't allocate new functions, as that would require you to deal with closures. Instead repeated calls to it will always return a pointer to the same function, whilst setting some variable (or modifying some code) so that future calls will see its argument. To make that a little clearer, here's an updated version of asCurryable2() which would conform to the expected behavior of your MIPS code, at least for 2-input functions. 

def asCurryable2(f):
    args = [0,0]
    def h(y):
        args[1] = y
        return f(args[0], args[1])
    def g(x):
        args[0] = x
        return h
    return g

Problem 2: Floating Points - 8pts

If you're starting this homework early and we haven't covered this yet don't worry. We'll be going over floating point representation in Wednesday's lecture. For the following questions, we will be referring to the IEEE 32-bit floating point representation except with a 6 bit exponent (bias of 2^6/2 - 1 = 31) and a denorm implicit exponent of -30.
  1. Convert -25.25 to floating point format. Write your answer in hexadecimal.
  2. What's the smallest positive integer (an integer has nothing to the right of the decimal) it CANNOT represent? Leave your answer in terms of powers 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 16 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 0x75?
  3. The block containing the byte at 0x75 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.