This says that there is essentially one set (set 0) and any memory block can res

ID: 3790239 • Letter: T

Question

This says that there is essentially one set (set 0) and any memory block can reside in any cache block.

a. Use the same table format to show which memory blocks map to which cache blocks if the cache is organized as a direct-mapped cache. In this case, the “Set” and “Way” fields are irrelevant.

b. Use the same table format to show which memory blocks map to which cache blocks if the cache is organized as a four-way set associative cache (i.e. four blocks can be stored per set).

c. Give a sequence of memory block accesses that will result in poor cache performance for both (a) and (b). For (b) state what type of replacement policy is being used for the cache.

Cache block Set Way Memory blocks that can reside in cache block M0, M1, M2, M31 M0, M1, M2, M31 M0, M1, M2, M31 M0, M1, M2, M31 M0, M1, M2, M31 M0, M1, M2, M31 M0, M1, M2, M31 M0, M1, M2, M31

Explanation / Answer

a. We know that for direct mapped cache that each line of cache memory can hold only certain memory blocks, and there is no contention (ie. If a line is already taken up by a memory block when a new block needs to be loaded, the old block is removed.).

Now looking at the question we can see that there are 8 cache lines (since cache size is 512B and each memory block size is 64B) and similarly 32 memory blocks. Let us number the lines as C0, C1, ... , C7, and memory blocks as M0, M1, ... , M31. Now the main question arrives, ie. Which block should go to which cache line? To determine the same we need to do simple calculations:

Memory block Mi goes to cache line Cj if and only if after dividing i by total number of cache lines (8 in our case) we get j as remainder.

for example, Memory block M13 goes to cache line C5 since upon dividing 13 by 8 we get remainder 5. Similarly we can fill up the table as

M0, M8, M16, M24

M1, M9, M17, M25

M2, M10, M18, M26

M3, M11, M19, M27

M4, M12, M20, M28

M5, M13, M21, M29

M6, M14, M22, M30

M7, M15, M23, M31

b. From the previous answer we know that we have 8 cache lines in the system. For set associative cache we need to know how many sets are present? We can find the total number of sets by dividing the total cache lines by n, where n comes from n way cache (in our case we have 8 cache lines and n=4, therefore we have 2 Sets namely set 0 and set 1).

We will group n lines together creating a set. Then a block in memory can map to any one of the lines of a specific set. There is still only one set that the block can map to. Similarly to determine to which set we can map a memory block to, we need to do some simple calculation as above.

Memory block Mi goes to set Sj if and only if after dividing i by total number of sets (2 in our case) we get j as remainder.

Since total number of sets is 2 in our case we can easily say that all even numbered memory blocks go to Set 0 and all odd number memory block goes to Set 1.

Considering the above data we can create the following data

c. To reduce the cache performance we must have lower hit-rate or in other way we can say more misses. Misses occur when the cache line (the memory block is intended for) is already blocked by some other memory block. For direct mapping if memory access sequence is :
M0, M8, M16, M24, M0, M8, ...
Hit-rate of the system becomes zero since all memory block are intended for cache line 0 and replacement is required for all memory blocks.

* Bold and underlined memory blocks are replacled already

For Set associative cache a memory block can get into any one of the lines in a particular set, we need a cache replacement strategy. Let us use First In First Out strategy and memory access time as above:
M0, M8, M16, M24, M0, M8, ...
Using the above sequence we will have only 4 compulsary misses initially, and remaining all hits, so this does not solve our problem.

If we add one more even frame in the sequence the hit rate will drom dramatically to zero, but hit rate of directly maped cache increases.
So let us use the following sequence by adding two memory block eligible for cache line 2
M0, M8, M16, M24, M2, M10, M0, M8, M16, M24, M2, M10, M0, ...

So sequence of memory block accesses
M0, M8, M16, M24, M2, M10, M0, M8, M16, M24, M2, M10, M0, ...
will cause 100% misses in both direct mapped and set associative with FIFO replacement strategy.

Cache Block Memory block that can reside 0