Calculating the set field of associative cache

In this example:

Assume a system’s memory has 128M words. Blocks are 64 words in length
and the cache consists of 32K blocks. Show the format for a main
memory address assuming a 2-way set associative cache mapping scheme.
Be sure to include the fields as well as their sizes.

The following is supposed to be the solution:

Each address has 27 bits, and there are 7 in the tag field, 14 in the
set field and 6 in the word field.

I understand how the word field was calculated (2^6 = 64), but I don’t understand how is the set field 14?.

Block size is 64 words, to find the number of sets we divide total number of blocks 32K by set size which is 64*2=128B (multiply by 2 since it’s 2-way), my calculation should be correct, am I missing something?

32KB/(64*2)B = 32KB/128B = 256 = 2^8

(Which implies that we need 8 bits for the set field)

Computer Science Asked by user3125670 on January 1, 2021

The memory has $128$M words = $2^{7+20}$ = $2^{27}$ words. Hence it needs needs $27$ bits for address space.

Each block has $64$ words, so the block offset = $2^6$ words. So Block offset field can be represented by $6$ bits.

Number of lines in the cache = $frac{Cache Size}{Block Size}$ =Number of blocks = $32$K blocks = $2^{5+10}$ = $2^{15}$ blocks.

Number of sets in the cache = $frac{Number of Lines}{Set Associativity}$ = $2^{15}$ blocks / $2$ blocks per set = $2^{14}$ sets. Hence number of bits to represent set field = $14$ bits.

Number of tag bits = $27 - (14+6) = 7$ bits.

Answered by Sagnik on January 1, 2021

To calculate the size of set we know that main memory address is a 2-way set associative cache mapping scheme,hence each set contains 2 blocks.

Hence Total no. of sets = Size of cache / Size of set
= (2^15/2^1)
= 2^14

(Which implies that we need 14 bits for the set field)

Answered by Shiv Shankar on January 1, 2021

Related Questions

What is Big O of a loop with square root inside?

0  Asked on October 21, 2021 by lukasz-dynowski

Help understanding a theorem Kleinberg proves related to sequence alignment

0  Asked on October 21, 2021 by mooglin

Is it posssible to calculate the intersection area of rectangles with sweep Line and Interval or Segment Tree

0  Asked on October 21, 2021 by thunderat

can it be said that NL^NL = NL?

2  Asked on October 21, 2021 by yankovs

How does computer memory store the file name?

1  Asked on October 21, 2021 by shane-studio

Why do we should not to use simple count instead of cumulative count in Counting Sort?

1  Asked on October 21, 2021 by alihaydar-gubatov

Factoring algorithms after number field sieves

1  Asked on October 21, 2021 by zirui-wang

How to calculate the dimension of a convex polyhedron?

1  Asked on October 21, 2021

Difficulty in few steps in proof of “Amortized cost of $text{Find-Set}$ operation is $Theta(alpha(n))$”assuming union by rank, path compression

1  Asked on October 21, 2021

How to determine the maximum valued play in Rummikub?

2  Asked on October 21, 2021

Clique vs Complete Graph

2  Asked on October 21, 2021 by ninja-bug

Why does the GS1 DataMatrix encode diagonally instead of vertically or horizontally?

1  Asked on October 21, 2021 by kittendestroyer-9000

How to design a formal grammar to convert EBNF description to a list of CFG production rules

1  Asked on October 21, 2021 by phamsodiep

Is protein folding really NP-hard and how to show that?

1  Asked on October 21, 2021

Enumerator for Word and Halting Problem

1  Asked on October 21, 2021 by felixouttaspace

Is there a way to simplify redundant conditionals?

0  Asked on October 21, 2021

algorithm to find shortest path connecting EVERY node

1  Asked on October 21, 2021 by peter-s

Range search in a max-heap

1  Asked on February 27, 2021

Is deletion and insertion easier in B+ trees compared to B trees?

0  Asked on February 26, 2021 by ayush