Cache

[Nkruti]

1)Here is a series of memory references given as word addresses
1,4 ,8,5,20,17,19,56,9,11,4,43,5,6,9,17.Assuming a direct mapped cache with four word blocks and a total size of 16 words,that are initially empty,label each reference as a hit/miss and show the final contents of the cache


2) how many total bits are required for a direct mapped cache of 64KB of data using 4 word blocks,assuming 32 bit address?

3) Consider three memory organisations
a) One word wide organisation
b) wide memory organisation
c) interleaved organisation

Assume cache block size is 16 words, width of organisation b is 4 words, number of banks of organisation c is 4. If the main memory latency for a new access is 10 cycles and the transfer time is 1 cycle, what are the miss penalties for each of these organisations?

4) Suppose a processor with a 16 word block size has an effective miss rate of 0.5%, CPI without cache misses is 1.2. Using the memories described above, how faster is this processor when using the wide memory than when using narrow or interleaved memories?

[dionysus]

Here is a series of memory references given as word addresses
1,4 ,8,5,20,17,19,56,9,11,4,43,5,6,9,17.Assuming a direct mapped cache with four word blocks and a total size of 16 words,that are initially empty,label each reference as a hit/miss and show the final contents of the cache

I think I got it totally wrong. First of all, I want to clarify what a block means in the context of a cache. Blocks are atomic units of trasfer between main memory and cache. So, when a block contains four words, this means that at a time, a chunk of four words is transfered from the memory to the cache. For example, if the memory address 1 was referenced and was not in the cache, then the entire block of addresses 0 through 3 would be trasferred, making [0,1,2,3] be the block that is moved into the cache.

Nkruti, thanks a lot for the question, as it does clarify some things. Now, I'm going to try to give it another shot:


First of all, the cache has 4 blocks, each with 4 words. Since we'll be transfering blocks in and out, first we should figure out which block a memory address would go to. With direct addressing, the one that makes most sense, is like this: Suppose the k-bit memory address in binary is: a_k a_{k-1} .... a_4 a_3 a_2 a_1. Then the block in cache in which this address is mapped to is {a_4 a_3}.

To run through miss / hit, its like this:

1: Miss. Words 0 - 3 transfered to Cache in Block 0.
4: Miss. Words 4 - 7 transfered to Cache in Block 1.
8: Miss. Words 8 - 11 transfered to Cache in Block 2.
5: Hit. Word 5 already in Cache Block 1.
20: Miss. Words 20 - 23 transfered to Cache in Block 1.
17: Miss. Words 16 - 19 transfered to Cache in Block 0.
19: Hit. Word 19 present in Cache Block 0.
56: Miss. Words 56 - 59 transfered to Cache in Block 2.
9: Miss. Words 8 - 11 transfered to Cache in Block 2.
11: Hit
4: Miss. Words 4 - 7 transfered to Cache in Block 1.
43: Miss. Words 40 - 43 transered to Cache in Block 2.
5: Hit.
6: Hit.
9: Miss. Words 8 - 11 transfered to Cache in Block 2.
17: Hit.

So overall, there are 6 Hits. And the final contents of the Cache are:
Block 0: Words 16 - 19.
Block 1: Words 4 - 7
Block 2: Words 8 - 11
Block 3: Empty.

Am I correct?

[Nkruti]

Perfect Dionysus.

An easy formula for the block to which the address in mapped to is
Direct mapped cache with one word
(Block address) modulo (no of blocks in the cache)

Multiword Direct mapped cache

(Block address) modulo (no of blocks in the cache)
where block address =word address/no.of words in a block OR
=byte address/no.of bytes in a block

How about having a shot at the other two problems?

[dionysus]

How many total bits are required for a direct mapped cache of 64KB of data using 4 word blocks,assuming 32 bit address?

Okay, let me give this one a shot. A direct mapped cache of 64KB data using 4 word blocks, assuming 1 word = 1 byte (is that correct?), there would be 64KB / 4 blocks = 16KB blocks. Therefore, to identify a block, we need 14 bits. Also, two more bits about the specific word within a block are there. So, given a 32 bit address, the last 16 bits are stored in a unique place for every 16 bits. Consider a word w = w_1 w_2, where w_1 and w_2 are both 16 bits long. So the direct map cache would require us to store 16 bits per block to indicate which w_1 the entry in the block corresponds to. Also, we would need one valid bit - for write backs - supposedly. So a total of 17 bits in addition information per block. Total number of blocks is 16KB. So the total amount of information: 16KB x 17 bits / 8 = 34KB. That makes a total of 98KB information for the 64KB cache. Am I correct?

[Nkruti]

The number of bits needed to implement the cache represents the total amount of memory needed for storing all of the data, tags and valid data.

One word=32 bits.

Keeping this in mind
64KB=16K words=2^14 words
Since we have 4 words per block
No.of blocks =2^14/4 =2^12

Each block has 4*32 bits of data, a tag which is(32-14-2) bits plus a valid bit
thus the total cache size is 2^12(32+(32-14-2)+1)=2^12*15
=60K Bits

[dionysus]

Natasha, I'm a bit confused with your solution. The cache capacity itself is 64KB. I think you forgot to multiply by 4 in the last line of your reasoning. I still have some doubts.

When we say assuming 32 bit addresses, then do addresses correspond to different words. What I'm basically asking is that are word addresses in the order 0, 4, 8, 12... (assuming addresses for each byte), or are word addresses in the order 0, 1, 2, ... - I'm sorry for my ignorance.

If we add the valid bits and the tag information on that, it should increase. How has the total number of bits required gone down. Your answer 60K bits < 64KB! If I were to do this question again, keeping in mind that a word = 32 bits = 4 bytes, I would say:

Number of words in Cache: 16K
Number of blocks in Cache: 4K.
To index a block, it takes: 12 bits.
Within a block, there are 4 words = 16 bytes, so 4 bits of the address are stored here.
Therefore, the total number of bits in the tag and the valid bit for one block of the Cache = 32 - (12 + 4) + 1 = 16 + 1 = 17.
So the total size of the Cache is: 4K x (17 + 4 x 4 x 8) bits = 72.5KB.

Please correct my line of thought Natasha!

[Nkruti]

oops I did forget a 4 in the last line.
thus the total cache size is 2^12(4*32+(32-14-2)+1)= 2^12 * 145 =580K bits


Dionysus , have a look at slide 18 in this link. Hope the diagrammatic representation makes things clearer
http://www.cse.psu.edu/~cg331/slides/cse331-week15.pdf

[dionysus]

Natasha,

Thanks for the link. Note, in passing that 580 K Bits = 72.5 KB = so our answers concur!

[Nkruti]

I was trying to understand this line in your explanation

Within a block, there are 4 words = 16 bytes, so 4 bits of the address are stored here


Anyways , I think in the AGRE it is only the final answer that is gonna count. whatever approach we take

how about taking a shot at the 2 problems that are left