Name: ID#: X.500:
CS 2021: Practice Exam 3
Fall 2021
University of Minnesota
Exam period: 20 minutes
Points available: 40
Problem 1 (10 pts): Below is an initial memory/cache configuration along with several memory load
operations. Indicate whether these load operations result in cache hits or misses and show the state of the
cache after these loads complete.
MAIN MEMORY DIRECT-MAPPED Cache, 8-byte lines
| Addr | Addr Bits | Value | 4 Sets, 8-bit Address = 3-bit tag
|——+—————-+——-|
| 10 | 000 10 000 | 10 | INITIAL CACHE STATE
| 14 | 000 10 100 | 11 | | | | | Blocks/Line |
| 18 | 000 11 000 | 12 | | Set | V | Tag | 0-3 4-7 |
| 1C | 000 11 100 | 13 | |—–+—+—–+————-|
| 20 | 001 00 000 | 20 | | 00 | 1 | 010 | 200 201 |
| 24 | 001 00 100 | 21 | | 01 | 1 | 001 | 22 23 |
| 28 | 001 01 000 | 22 | | 10 | 1 | 000 | 10 11 |
| 2C | 001 01 100 | 23 | | 11 | 0 | – | – |
| 30 | 001 10 000 | 100 |
| 34 | 001 10 100 | 101 | HITS OR MISSES?
| 38 | 001 11 000 | 102 | | OPEARTION | HIT/MISS? |
| 3C | 001 11 100 | 103 | |————–+———–|
| 40 | 010 00 000 | 200 | | 1. Load 0x48 | |
| 44 | 010 00 100 | 201 | | 2. Load 0x4C | |
| 48 | 010 01 000 | 202 | | 3. Load 0x24 | |
| 4C | 010 01 100 | 203 |
|——+—————-+——-| FINAL CACHE STATE
| | Tag Set Offset | | | | | | Blocks/Line | |
| Set | V | Tag | 0-3 4-7 | Changed? |
|—–+—+—–+————-+———-|
| 00 | | | | |
| 01 | | | | |
| 10 | | | | |
| 11 | | | | |
Problem 2 (5 pts): Pyra Midmem read in a free online blog post “Memory for Morons” that there is
no need to invest much money in buying RAM. Instead, one can configure the operating system’s virtual
memory system to use disk space as main memory leading to a much less expensive computer with a
seemingly large memory. Pyra is quite excited about this as some programs she wants to execute fast need
a lot of main memory and it would be nice to save some cash. Advise her on any risks or performance
drawbacks she may encounter using such an approach.
1/ 2
WRITE ON EVERY PAGE – Name:
Problem 3 (15 pts): Nearby is the definition for
base scalvec() which scales a vector by multiplying
each element by a number. Write an optimized ver-
sion of this function in the space provided. Mention
in comments why you performed certain transforma-
tions.
1 int vget(vector_t vec, int idx){
2 return vec.data[idx];
3 }
4 void vset(vector_t vec, int idx, int x){
5 vec.data[idx] = x;
6 }
7 void base_scalevec(vector_t *vec, int *scale){
8 for(int i=0; i < vec->len; i++){
9 int cur = vget(*vec,i);
10 int new = cur * (*scale);
11 vset(*vec,i,new);
12 }
13 }
Problem 4 (10 pts): Examine the two functions be-
low which add elements of a row or column vector to all
corresponding rows or columns of a matrix. Consider the
benchmark timing of these two provided.
1. Explain which of these two functions is faster and why.
2. Suggest a way to increase the speed of the slower func-
tion with only moderate changes to the code.
1 // add given row to each row of mat
2 void matrix_addrow_vec(matrix_t mat,
3 vector_t row) {
4 for(int i=0; i