24
$\begingroup$

Specifically:

1) A direct-mapped cache with 4096 blocks/lines in which each block has 8 32-bit words. How many bits are needed for the tag and index fields, assuming a 32-bit address?

2) Same question as 1) but for fully associative cache?

Correct me if I'm wrong, is it:

tag bits = address bit length - exponent of index - exponent of offset?

[Is the offset = 3 due to 2^3 = 8 or is it 5 from 2^5 = 32?]

Improve this question
$\endgroup$
1

5 Answers 5

Reset to default
25
$\begingroup$

The question as stated is not quite answerable. A word has been defined to be 32-bits. We need to know whether the system is "byte-addressable" (you can access an 8-bit chunk of data) or "word-addressable" (smallest accessible chunk is 32-bits) or even "half-word addressable" (the smallest chunk of data you can access is 16-bits.) You need to know this to know what the lowest-order bit of an address is telling you.

Then you work from the bottom up. Let's assume the system is byte addressable.

Then each cache block contains 8 words*(4 bytes/word)=32=25 bytes, so the offset is 5 bits.

The index for a direct mapped cache is the number of blocks in the cache (12 bits in this case, because 212=4096.)

Then the tag is all the bits that are left, as you have indicated.

As the cache gets more associative but stays the same size there are fewer index bits and more tag bits.

Improve this answer
$\endgroup$
2
  • $\begingroup$ yup it's byte addressable but the question I looked at didn't specifically state it $\endgroup$
    – compski
    Commented Jul 20, 2013 at 15:06
  • $\begingroup$ Well sort of. But you might want to reword it so it doesn't sound like all the blocks have the same index... You're really talking about how many indices you need, and from that how many bits you need. (visualize how it works here with smaller numbers: www2.hawaii.edu/~tvs/cache.html ) $\endgroup$
    – Ted Shaneyfelt
    Commented Jul 21, 2021 at 5:49
3
$\begingroup$

Your formula for tag bits is correct.

Whether the offset is three bits or five bits depends on whether the processor uses byte (octet) addressing or word addressing. Outside of DSPs, almost all recent processors use byte addressing, so it would be safe to assume byte addressing (and five offset bits).

Improve this answer
$\endgroup$
2
  • $\begingroup$ I didn't know there were such distinctions, yes it is byte addressing $\endgroup$
    – compski
    Commented Jul 20, 2013 at 15:05
  • 1
    $\begingroup$ Prior to the mid 1970s we might reasonably assume that a "word" was the size of the smallest addressable unit of data. This table on the wikipedia page on word is amusing (if you like that kind of thing, (which I do.)) $\endgroup$
    – Wandering Logic
    Commented Jul 20, 2013 at 16:47
2
$\begingroup$

There are no index bits in a fully associative cache. The index bits are used to uniquely identify which set the block belongs. In a fully associative cache, all blocks are essentially part of the same set.

Improve this answer
$\endgroup$
1
$\begingroup$

I'm learning for the final exam of subject Computer System, I googled for a while and found this question. And this part of the question is confuse : "in which each block has 8 32-bit words". A word is 4 bytes (or 32 bits) so the question just need to be "...in which each block has 8 words"

The answer is - Each block is 32 bytes (8 words), so we need 5 offset bits to determine which byte in each block - Direct-mapped => number of sets = number of blocks = 4096 => we need 12 index bits to determine which set

=> tag bit = 32 - 12 - 5 = 15

For fully associative, the number of set is 1 => no index bit => tag bit = 32 - 0 - 5 = 27

Improve this answer
$\endgroup$
-1
$\begingroup$

in full associate mapping index is 0 b/s like you say set = 1 so index=log of 1 in base 2 =0 set offset =log of block size of byte base 2 so use 8=2^3 or 32=2^5 tag=32-0-5=27 for direct index=2^12=12 offset=0 bit tag= 32-12-0=20

Improve this answer
$\endgroup$
1
  • $\begingroup$ I find this very impossible to read. Please, use some punctuation. $\endgroup$
    – David Richerby
    Commented Nov 18, 2018 at 18:39

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