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.- Convert -25.25 to floating point format. Write your answer in hexadecimal.
- What's the smallest positive integer (an integer has no decimal points) it CANNOT represent? Leave your answer as a power of 2.
- 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?)
- 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.
- How many bits are used for the tag?
- Which other bytes would share a block with the byte at address 0x85?
- 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.
- 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
- if
stride
= 256? - if
stride
= 255?