Q1 Cache performance 7 Points
You are given the following piece of code to analyze.
Assume we execute this under the following conditions:
sizeof(int) = 4
Array x begins at memory address 0x0 and is stored in row-major order. In each case below, the cache is initially empty.
The only memory accesses are to the entries of the array x. All other variables are stored in registers.
You do not need to consider fetching instructions from memory in this question.
Q1.1
1 Point
What is the memory address of x[0][10]?
0xA 0x0 0x28 0x228 0x8A
Q1.2
1 Point
What is the memory address of x[1][10]?
0xA 0x0 0x28 0x228 0x8A
Q1.3
1 Point
Assume the cache is 512 bytes, direct-mapped, with 16-byte cache blocks. How many set-index bits are there in a memory address? (i.e., how many bits will the machine use to identify the cache set that a cache block belongs to)
3 4 5 8 9
Q1.4
1 Point
Assume the cache is 512 bytes, direct-mapped, with 16-byte cache blocks. What is the miss rate of executing the above loop?
25% 50% 75% 100%
Q1.5
1 Point
What is the miss rate if we double the cache size to 1024 bytes, while keeping all other designs unchanged (i.e., direct mapped, 16-byte cache block)?
25% 50% 75% 100%
Q1.6
1 Point
What type of cache misses do the program encounter in the setting in question 1.5?
Capacity miss
Cold miss
Conflict miss
A combination of above
Q1.7
1 Point
Now assume the cache is 512 bytes, two-way set associative using an LRU replacement policy (the cache line that was least recently used in a set will be
replaced), with 16-byte cache blocks. What is the cache miss rate?
25% 50% 75% 100%
Q2
2 Points
Consider a combination of software and hardware that is quantified in terms of the following variables. All reported latencies are average latencies.
Latency of a non-memory instruction: 1.67 cycles A cache hit takes H = 2 cycle
A cache miss takes extra M = 120 cycles
The breakdown of instruction types is:
34% instructions are memory instructions
66% instructions are non-memory instructions (ALU, register move, etc.)
Q2.1 Latency 1 Point
Assume that the cache hit rate is 60%. What is the average latency of an instruction on this machine?
1.78 17.83 18.10 26.26 33.56 49.41