# GATE2014-2-9

10.4k views
A $4$-way set-associative cache memory unit with a capacity of $16$ KB is built using a block size of $8$ words. The word length is $32$ bits. The size of the physical address space is $4$ GB. The number of bits for the TAG field is ____

edited
3

 20 7 5 Tag Set Offset

$<----32---->$

Assume word addressability. (Cache = 4K words; word size = 4B; PAS = 1G words)

 20 7 3 Tag Set Offset

$<----30---->$

Number of sets$=\dfrac{\text{cache size}}{\text{sizeof a set}}$

Size of a set $=\text{blocksize}\times \text{no. of blocks in a set}$
$= 8 \text{ words}\times 4\text{ (4-way set-associative)}$
$= 8\times 4\times 4\text{ (since a word is 32 bits = 4 bytes)}$
$= 128\text{ bytes}.$

So, number of sets $=\dfrac{16\ KB}{(128\ B)}=128$

Now, we can divide the physical address space equally between these $128$ sets.
So, the number of bytes each set can access
$=\dfrac{4\ GB}{128}$

$={32\ MB}$

$=\dfrac{32}{4}=8\text{ M words}=1 \text{ M blocks. ($2^{20}$blocks)}$

So, we need $20$ tag bits to identify these $2^{20}$ blocks.

edited
0
4 GB space is divided between 128 sets equally.

So each set contains 4GB / 128 = 32 MB.

Set is 4-way set associative , so contains 4 block / set.

32/4 = 8M words / block.  Can u explain further ?? I didnt get how 2^20 came.
0
8M words = 1M blocks since block size is 8 words. Now, 1M = 2^20. So, to address 2^20 blocks we need 20 bits.
3
I am a little confused. If tag field is 20 bits and set field is 7 bits(since there are 128 sets) then we need 5 bits for word field, since there are 32 bits in physical address. But there are just 8 words per block which implies 3 bits . Am I wrong?
7
That is for word addressing where the offset is used for fetching a word and not byte. By default we assume byte addressing. Here, each word is of 32 bits - so we need 2 more bits to access a byte.

(And we always calculate the set bits and offset bits and put the remaining in tag bits, not the other way)
0
"And we always calculate the set bits and offset bits and put the remaining in tag bits, not the other way"....yes that's what I am saying...we first calculate set bits(log 128 = 7), and then word bits(log 8 = 3), and finally tag bits, which equals 32-(7+3) = 22 bits.

In the book I am reading , the author divides the address into 3 parts..TAG : SET : WORD .

"By default we assume byte addressing"...should I solve questions by always assuming byte addressing in gate??

6
yes. Unless specified use byte addressing.
0
Till now all such problems I came across of this type did: TAG_BITS = ADDRESS_BITS - SET_BITS - WORD_BITS. Why here problem is solved in different way?

I solved it like this:

(Given) 4 way set associative $\rightarrow$ 4 lines per set
(Given) Cache size = 16 KB = $2^{14}$B
(Given) words per line = 8
(Given) Main memory size = 4GB $= 2^{32}$B
$\rightarrow$ ADDRESS_BITS = 32
(Given) Word size = 32 bits = 4 bytes per word
$\rightarrow$ WORD_BITS = 2
Line size = 8 words per line $\times$ 4 bytes per word = 32 B
Set size = 4 lines per set $\times$ 32 bytes per line = 128 B $=2^7$B
Number sets in cache = cache size / set size = $2^{14}/2^7=2^7=128$
$\rightarrow$ SET_BITS = 7
TAG_BITS = ADDRESS_BITS $-$ SET_BITS $-$ WORD_BITS
$= 32 - 7 - 2 = 23$ bits

Why above calculations are wrong? @Arjun sir can you please have a look at this?
0
Even im getting 23 bits as answer using the same method.
1

@GateAspirant999

The number of bits needed for the word field is not 2, it's 5

As you said, size of a word is 4 Bytes, and since 1 block contains 8 words, the size of a block is 32 B.

So, to uniquely identify a word from a block, we need 5 bits ( cause 2^5 = 32 )

This is how we get no. of tag bits = 32 - 5 - 7 = 20

1
1 World size = 32 bits = 32/8= 4 Btye

block size = 8 words * 1 word_size = 8 * 4 = 32 Bytes

no of blocks = 4GB/32Btye = $2^{32 }$ / $2^{5 }$ = $2^{27 }$

27 bits is needed for block identification

no of cache lines = cache size / block size =   16KB / 32B = $2^{14 }$ / $2^{5 }$ = $2^{9 }$

no of sets = $2^{9 }$ / 4 =$2^{7 }$

7 bits is used for set identification
tag bit =block identification bits - line bits=  27-7 = 20

Irrespective of byte or word addressable system number of bits required for TAG won't get affected

Let us fist assume that system is byte addressable

Block size= 32byte

Number of blocks in main memory= 16KB/32B= 512 blocks

Number of sets = 512/4= 128 sets

Format is TAG |SET | BLOCK

Set= 7 bit,

block = 5 bit,

tag = 32-5-7=20 bits

Now let us consider word addressable system

Convert everything with respect to word

Cache size is 4K words, physical address space is 1G words

Number of blocks in cache= 4K/8=512 blocks

Number of sets = 128 sets

Format = Tag| set | word

Set = 7 bit

Word = 3 bit

Tag =30-7-3= 20 bits

Conclusion irrespective of byte or word addressable system number of bits required for TAG won't be affected provided we define everything as per byte addressable or word addressable system

edited by
1
After reading this question,it seems to hard to solve.But, reading this conclusion ,now it is quite easy.
2
correct it ... # of sets = 512 / 4 = 128 ...nt 127 ....
0
@Srestha,@Shaik Masthan,Please may I know one thing?Here as word addressable system is mentioned for the second part, then accordingly how 4K words is assumed when the capacity is 16 KB. Also why are we dividing by 8?Please may I know,when the word size is 32 bits. Thanks again. :)
0

" The word length is 32 bits."

0
1
32 bits word length=4B

Cache capacity of 16 KB, which is Byte addressable format

To change it to word addressable $\frac{16KB}{4B}=4K word$
1
@Srestha,Now I got it. Thanks a lot. :)
1
Thankssss a lot! Saved me
1
This should be the best answer with proper editing.

We try to convert in one format either byte addressable or word addressable.both case we will get same tag bits .

0

Total number of bits in a physical address should remain be same either u r doing with Byte addressable format(means converting evreything in to bytes) or word addressable please reply if i m wrong somewhere

1 vote
> Total address length = bits required to represent no of words in Physical Address Space =  Log (Physical address size / Word size)

= Log(4 GB / 32 bits) = 30

> Block size = 8 words = 8 * 32 bits = 32 Bytes

> Bits required for set field = log (cache size / (block size * associativity)) = log(16 KB / (32 Bytes * 4)) = 7

> Bits required for word field = log (no of words in each block) = log 8 = 3

> So bits required for Tag field = 30 - 7 - 3 = 20 bits.

## Related questions

1
4.2k views
If the associativity of a processor cache is doubled while keeping the capacity and block size unchanged, which one of the following is guaranteed to be NOT affected? Width of tag comparator Width of set index decoder Width of way selection multiplexer Width of processor to main memory data bus
2
8.1k views
In designing a computer's cache system, the cache block (or cache line) size is an important parameter. Which one of the following statements is correct in this context? A smaller block size implies better spatial locality A smaller block size implies a smaller ... smaller block size implies a larger cache tag and hence lower cache hit time A smaller block size incurs a lower cache miss penalty
3
2.3k views
The ratio of male to female students in a college for five years is plotted in the following line graph. If the number of female students doubled in $2009$, by what percent did the number of male students increase in $2009$?
Consider the main memory system that consists of $8$ memory modules attached to the system bus, which is one word wide. When a write request is made, the bus is occupied for $100$ nanoseconds (ns) by the data, address, and control signals. During the same $100$ ns, ... be on the bus at any time. The maximum number of stores (of one word each) that can be initiated in $1$ millisecond is ________