Question

In a hypothetical system with 1024 bytes of main memory, 128 bytes of cache, blocks of 32-byte size, with direct-map (S = 1) placement policy and LRU replacement policy, answer each of the following questions:

1. Determine the address fields for index, tag and block offset in the memory address.
2. How many sets are there in the cache?
3. How many blocks in the main memory are mapped to the same set of blocks in cache?
4. If associative (parallel) comparison is to be performed with all tags for identification, how many XOR gates are required?
5. Determine the hit ratio in running each of the following program segments (each instruction occupies a word):
   1. m a sequence of 100 consecutive instructions starting from address x148 with each instruction executed once in order
   2. a loop of 32 consecutive instructions starting at location x148 and is iterated 20 times
   3. a loop of 64 consecutive instructions starting at location x148 and is iterated 20 times

Answer 1

main memory=1024 Bytes.

There fore, we need 10 bits to address a word in main memory.

cache=128 Bytes.

Block size=32 Bytes.

Therefore,Block offset =5 bits.

Number of blocks in cache=128/32=4

Hence index=2 bits.

Number of tag bits=10-2-5=3 bits

b-

Number of sets=Number of blocks / associtivity=4/1=4

c-

Number of tag bits=3.

This implies main memory blocks are mapped to one cache block.

d-

We have to compare tag bits of every block with tag bits of address.

If we use 2 input xor gates,we need 1 xor gate for each tag bit.

Hence number of exor gate=Total number of tag bits=number of tag bits per block* number of blocks=3*4=12

but if we have multi input xor gate, we need only 4 xor gates.