Solved Example Problems on Cache Memories Concepts

Example : 2

Consider a cache consisting of 256 blocks of 16 words each, for a total of 4096 (4 K) words and assume that the main memory is addressable by a 16‒bit address and it consists of 4 K blocks. How many bits are there in each of the TAG, BLOCK/SET and word fields for different mapping techniques ?

Solution : We know that memory address is divided into three fields. We will now find the exact bits required for each field in different mapping techniques.

a) Direct‒mapping

Word bits: We know that each block consists of 16 words. Therefore, to identify each word we must have (24 = 16) four bit reserved for it.

Block bits: The cache memory consists of 256 blocks and using direct‒mapped technique, block k of the main memory maps onto block k modulo 256 of the cache. It has one to one correspondence and requires unique address for each block. To address 128 block we require (28 = 256) eight bits.

Tag bits: The remaining 4 (16‒4‒8) address bits are tag bits which stores the higher address of the main memory.

The main memory address for direct‒mapping technique is divided as shown below :

b) Associative‒mapping

Word bits : The word length will remain same i.e. 4 bits.

• In the associative‒mapping technique, each block in the main memory is identified by the tag bits and an address received from the CPU is compared with the tag bits of each block of the cache to see if the desired block is present. Therefore, this type of technique does not have block bits, but all remaining bits (except word bits) are reserved as tag bits.

Block bits: 0

Tag bits: To address each block in the main memory (212 = 4096) 12 bits are required and therefore, there are 12 tag bits.

The main memory address for direct mapping technique is divided as shown below :

c) Set‒associative mapping

Let us assume that there is a 2‒way set‒associative mapping. Here, cache memory is mapped with two blocks per set. The set field of the address determines which set of the cache might contain the desired block.

Word bits : The word length will remain same i.e. 4 bits.

Set bits: There are 128 sets (256/2). To identify each set (27 = 128) seven bits are required.

Tag bits: The remaining 5 (16‒4‒7) address bits are the tag bits which stores higher address of the main memory.

The main memory address for 2‒way set associative mapping technique is divided as shown below:

Example: 3

A block set‒associative cache consists of 64 blocks divided into 4 block sets. The main memory contains 4096 blocks, each consists of 128 words of 16 bits length:

i) How many bits are there in main memory?

ii) How many bits are there in each of the TAG, SET and WORD fields?

Solution :

i) Number of bits in main memory:

= Number of blocks × Number of words per block × Number of bits per word

= 4096 × 128 × 16

= 8388608 bits

ii) Number of bits in word field:

There are 128 words in each block. Therefore, to identify each word (27 = 128) 7 bits are required.

iii) Number of T bits in set field:

There are 64 blocks and each set consists of 4 blocks.

Therefore, there are 16 (64/4) sets. To identify each set (24 = 16) four bits are required.

iv) Number of bits in tag field:

The total words in the memory are :

4096 × 128 = 524288

To address these words we require (219 = 524288) 19 address lines. Therefore, tag bits are eight (19‒7‒4).

Example: 4

A digital computer has a memory unit of 64 K × 16 and a cache memory of 1 K words. The cache uses direct mapping with a block size of four words. How many bits there in the tag index, block and word field of the address format ?

Solution:

Word bits: Number of word bits = log2 4 = log2 22 = 2‒bits

Block bits: Number of block = Cache size / Words in each block = 1K / 4 = 256

  Number of block bits = log2 256 = log2 28 = 8 bits

Tag bits: Number of bits to address main memory

= log2 64 K = log2 216 = 16 bits

 Number of Tag bits = 16‒8‒2 = 6 bits

Example: 5

A two way set associative cache memory uses block of four words. The cache can accommodate a total of 2048 words from main memory. The main memory size is 128 K × 32.

i) How many bits are there in the tag index, block and word field of address format?

ii) What is size of cache memory?

Solution:

Number of bits in main memory address = log2 128 K = log 217 = 17 bits

Number of blocks in the cache memory = 2048 /4 = 512 blocks

Number of sets in the cache memory = 512 /2 = 256 sets

Number of bits in set field = log2 256 = log2 28 = 8 bits

Number of bits in word field = log2 4 = log2 22 = 2 bits

Number of bits in tag field = 17‒8‒2 = 7 bits

Example: 6

A direct mapped cache has the following parameters : cache size = 1 K words, Block size = 128 words and main memory size is 64 K words. Specify the number of bits in TAG, BLOCK and WORD in main memory address.

Solution:

Word bits = log2 128 = 7‒bits

Number of blocks = Cache size / Words in each block = 1 K / 128 = 8

  Number of block bits = log2 8=3‒bits

Number of address bits to address main memory = log2 64 K = log2 216 = 16‒bits

  Tag bits = 16‒3‒7 = 6‒bits

Example : 7

 How many total bits are required for a direct‒mapped cache with 16 kB of data and 4‒word blocks, assuming a 32‒bit address ?

Solution :

16 kB = 4K words = 212 words

Block size of 4 words = 210 blocks

Each block has 4 × 32 = 128 bits of data + tag + valid bit

Tag + valid bit = (32‒10‒2‒2) + 1= 19

Total cache size = 210 (128 +19) = 210 × 147

Therefore, 147 kB are needed for the cache.

Example : 8

You have been asked to design a cache with the following properties:

1) Data words are 32 bits each.

2) A cache block will contain 2048 bits of data.

3) The cache is direct mapped.

4) The address supplied from the CPU is 32 bits long.

5) There are 2048 blocks in the cache.

6) Addresses are to the word.

In the below Fig. 4.3.11, there are 8 fields (labeled a,b,c,d,e,f,g and h), you will need to indicate

the proper name or number of bits for a particular portion of this cache configuration.

Solution :

f. (name) ‒ You are being asked to show what part of a physical address form the index, offset and tag. < f > refers to the most significant bits of the address ‒so this is the tag.

g. (name) ‒ It follows that the next part of the address is the index.

h. (name) ‒ The least significant bits form the offset.

c. (name) ‒ There are 211 bits / block and there are 25 bits / word. Thus there are 26 words / block so we need 6 bits of offset.

b. (name) ‒ There are 211 blocks and the cache is direct mapped (or "1‒way set associative"). Therefore, we need 11 bits of index.

a. (name) ‒ The remaining bits form the tag. Thus, 32‒6‒11 = 15 bits of tag.

d. (name) ‒ Field< d > refers to the fact that a tag must be stored in each block. Thus, 15 bits are kept in each block.

e. (number) = Field< e > asks you to specify the total number of bits / block. This is 2048.

• We need to compare the valid bit associated with the block, the tag stored in the block and the tag associated with the physical address to determine if the cache entry is useable or not. The tags should be the same and the valid bit should be 1.

Cache size

• There are 2048 blocks in the cache and there are 2048 bits / block. There are 8 bits / byte. Thus, there are 256 bytes/block

2048 blocks × 256 bytes / block = 219 bytes (or 0.5 MB)