Please explain step-by-step how to solve this (a) Suppose you have a 4-way set a
ID: 3874996 • Letter: P
Question
Please explain step-by-step how to solve this
(a) Suppose you have a 4-way set associative cache with a block size of 32 bytes and a capacity of 4096 bytes. What sizes (in bits) are then the tag field and the set fielod, assuming that it is a 16-bit processor? (2 points) (b) Suppose you have a 32-bit processor with separate data and instruction caches. Both caches are direct mapped, each with a capacity of 16384 bytes. The data cache has a block size of 8 bytes and the instruction cache has a block size of 16 bytes. Assume that the processor is executing a loop that contains in total 5 instructions, where there is only one memory access instruction: lb $t0,-4 ($t1) In each iteration, directly after the load byte instruction, register $t1 is incremented by one. The first instruction of the loop is located at memory address 0x00401008 and register $t1 is initiated to value 0x60000006 before the loop starts. The loop executes 8 iterations. Assume also that all valid bits in both caches are zero before the loop starts. What are then the instruction cache miss rate and the data cache miss rate? For this program, are the instruction and/or the data caches utilizing temporal locality or spatial locality or both? (6 points)Explanation / Answer
For a 4 way set associative memory with 32 Bytes of cache line, each set occupies 32 bytes times 4 bytes i.e.128Bytes. Total number of sets possible for a 4K memory with that set size is 4k / 128 Bytes. that is 2^12 / 2^7 = 2^ 5 = 32 sets.
With 32 Byte cache line Offset address bits are 5 because 2^5=32.
Similarly Set field size is again 5 bits to distinguish between 32 possible number of sets.
remaining of the 16 bit address lines are Tag filed i.e. 16-5-5 = 6 bits.
Part B.
For data cache with 8 bytes of cache line ; offset is 3 bits.
Total number of cache lines for give 16384 byte of cache is 16384 / 8 = 2048 Lines
thus number of Set field bits = 11 (2^11 = 2048 = 2K)
for the data access starting at address 0x6000_0006 (0110_0000_0000_0000_0000_0000_0000_0110)
offset value is 110 and set field value is 00000000000
so for access to first addresses 06 causes a cache miss as they are all zero before start.
for second address 07 offset value changes to 111 and set field value reamins unchanged
So cache line is present because of previous access.hence a cache hit.
for third address set field value changes to 0000_0000_001 for next 6 data acccess to addresses 08 to 0d.
so there is one data cache miss at 08 and 5 cache Hits thereafter.
summing up for data cache:
total number of cache access = 8
total number of cache hit = 6
so data cache hit rate = 6/8 = 0.75
Working similarly for Instruction cache we have offset bits of 4 bits and set field bits of size 10 bits.
address access to 0x0040_1008 (0000_0000_0100_0000_0001_0000_0000_1000)
offset address for first access is 1000 and set field is 01_0000_0000
first access is a miss ;
the second access is at address 0040_100C
that still has the same set field as the previous one so a cache hit.
by third instruction the set field address changes to 01_0000_0001
for the next 3 instructions
the third instruction is a miss
but instruction 4 and 5 are a hit
This happens 8 times in an iteration.
summing up
Instruction cache memory access = 5 * 8 = 40
cache hit = 3 * 8 = 24
instruction cache hit rate = 24/40 = 0.6
While executing the program, accesses are made to locations that are close in time (same location several times) or in space (locations near to each other).
If memory locations are accessed frequently over a period of time it is said to have temporal locality. This applies to our case of instruction memory cache where the same set of instructions is accessed in an iteration.
If memory locations accessed are near to each other that get used only once, it is said to have spatial locality. This applies to our case of data memory cache where the data accessed is near to data accessed in previous instruction.