1
$\begingroup$

Given a non-associative, direct-mapped cache and its cache capacity, block size, and address size, how would I go about determining what bits of the address are used to access to cache? Is there a generalized formula?

If there is a generalized formula, how would that formula change or stay the same for an X-way set associative cache?

$\endgroup$
1
1
$\begingroup$

A direct-mapped cache is another name for a one-way set associative cache.

Calculating number of bits in address space

Number of bits in address space = log2(Memory size)

Bits in (Tag + Index + offset) = Number of bits in address space

In order to know the number of bits in Tag field, we would need to figure out the number of bits in Index and Offset fields. Then the above equation can be used to get the number of bits in the Tag field.

The index bits are used to select the row in the cache. The offset would then be used to get the cache block. This means we definitely need those number of bits to access information from the cache and the remaining bits from the total address space can be used to store the tag information.

Calculating the number of bits for the offset

The offset fields can be calculated using the information about the block size. A cache block is the basic unit of storage for the cache. For these set of problems the offset should be able to index every byte from within the cache block.

offset bits = log2(block size)

Calculating the number of bits for the cache index

The index bits are needed to select the cache row but before that we need to figure out the number of rows for a given cache configuration.
The number of rows would be equal to the cache size divided by the block size for a direct mapped cache (there's just one way). For a n-way set associative cache, the number of rows would be cache size divided by the number of ways and the block size, i.e.

Number of rows = Cache Size / (Block Size x Number of Ways)

Once the number of rows are known, the number of index bits would simply be the log base 2 of the number of rows:

Index bits = log2(Number of rows)

Now, we can calculate the number of Tag bits using the following relationship:

Tag + Index + Offset = Address bits

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.