I found this concept really hard to memorise during my preparation. Till date gate hasn't asked any specific question on this topic. But chances are pretty fair for this type of questions to come in near future. Don't get upset if you are not able to get it. Just skip it. I too skipped it. Go as relax as possible to gate exam. Even if question comes from this section just leave it. Don't spoil the entire paper for just 2 marks.
Lets get started:
1. WRITE THROUGH CACHE
READ HIT:- No memory access.
READ MISS:- Memory must send number of words required by the Cache.
WRITE HIT:- Cache must send a word to memory.
WRITE MISS:- Memory must send to cache equivalent number of words required and then Cache must send a word to memory.
2. WRITE BACK CACHE
READ HIT:- No memory access.
READ MISS:- If replaced line/block is modified then cache to memory first then memory to cache equivalent number of words required.
If replaced line/block is clean then memory to cache required number of words will be sent.
WRITE HIT:- No memory access
WRITE MISS:- If replaced line is modified then cache to memory first then memory to cache equivalent number of words required.
If replaced line/block is clean then memory to cache required number of words will be sent.
3. WRITE ALLOCATE ( FETCH ON WRITE)
Data at the missed write location is loaded to the Cache, followed by a write-hit operation.
Here write misses are similar to read miss.
Generally, write back caches use write allocate principle.
4. NO-WRITE ALLOCATE (WRITE NO-ALLOCATE OR WRITE AROUND)
Data at the missed write location is not loaded to cache and is written directly to the backing store.
Only the reads are cached.
Generally, write through cache uses no-write principle.
Example:
A 64 word Cache and Main Memory are divided into 16 word blocks...cache access time=10 ns ,,MM access time =50 ns. the hit ratio for read operation is =80% and write operation=90%.
Whenever a page fault occurs,the associated block must be brought from Main memory to cache for both read and write operation....read frequency=40%,write frequency =60%.
Assume CPU bus can transfer 1 word at a time.
1.what is avg access time if write through scheme is used?
Answer:
First write all the things you need for calculation.
Block size = 16 words
Cache access time = 10ns
Main Memory access time = 50ns
Cache Hit ratio:
Read hit = 80%
Read miss = 20%
Write hit = 90%
Write miss = 10%
Read operation frequency = 40%
Write operation frequency = 60%
------------------
1. If write through scheme is used:
First you should do this...
Avg access time = (40%)(Avg Read access time) + (60%) (Avg Write access time)
(We have just divided the total number of operations into read and write operations, as 40% are read operations and 60% are write operations)
.....................................
Now similarly divide the Avg read access time and Avg Write access time,
Avg Read access time = (80%)(Avg Read hit time) + (20%)(Avg Read miss time)
Avg Write access time = (90%)(Avg Write hit time) + (10%)(Avg Write miss time)
......................................
Now refer to the theory part i mentioned above for write through scheme.
Avg Read hit time = 0(Main memory) + 10(cache), since no memory access is required and 1 cache read is required.
Avg Read miss time = 16*50(Main memory) + (1+16+1)*10(cache),1st cache read is a miss, then memory must send 16 words(Block size ) to the cache {note: 16 memory access and 16 cache access are required for this transfer} and then 1 final cache read is required to get the data.
Avg Write hit time = 1*50(Main memory) + 10(cache), here cache must send the word written to the memory
Avg Write miss time = (16+1)*50(Main memory) + (1+16+1)*10(cache), here Memory must send to cache 16 words (Block size) and then Cache must send a word to memory.
........................................
Now just wrap everything up and get the answer.
Avg access time = (40%){ (80%)(10) + 20%(260) } + (60%){ (90%)(60) + (10%)(1030) }
= (0.4) {8 + 52} + (0.6) {54 + 103}
= (0.4) {60} + (0.6) { 157 } = 118.2 ns
There is also another method using stall frequency which is a faster method. But in order to do that you need to be very thorough in applying all data. This method is slower but will always give you the exact accurate answer with no errors.
------------------------------------------------------------
Additional Task:
Do extend the above question for write back cache policy. Here you will need ratio of pages modified. Assume 20% of pages are modified. Now just imagine how we solved it for write through cache and use it to solve for write back cache policy. Post your answers on comments. I will verify it when i get some time...
Lets get started:
1. WRITE THROUGH CACHE
READ HIT:- No memory access.
READ MISS:- Memory must send number of words required by the Cache.
WRITE HIT:- Cache must send a word to memory.
WRITE MISS:- Memory must send to cache equivalent number of words required and then Cache must send a word to memory.
2. WRITE BACK CACHE
READ HIT:- No memory access.
READ MISS:- If replaced line/block is modified then cache to memory first then memory to cache equivalent number of words required.
If replaced line/block is clean then memory to cache required number of words will be sent.
WRITE HIT:- No memory access
WRITE MISS:- If replaced line is modified then cache to memory first then memory to cache equivalent number of words required.
If replaced line/block is clean then memory to cache required number of words will be sent.
3. WRITE ALLOCATE ( FETCH ON WRITE)
Data at the missed write location is loaded to the Cache, followed by a write-hit operation.
Here write misses are similar to read miss.
Generally, write back caches use write allocate principle.
4. NO-WRITE ALLOCATE (WRITE NO-ALLOCATE OR WRITE AROUND)
Data at the missed write location is not loaded to cache and is written directly to the backing store.
Only the reads are cached.
Generally, write through cache uses no-write principle.
Example:
A 64 word Cache and Main Memory are divided into 16 word blocks...cache access time=10 ns ,,MM access time =50 ns. the hit ratio for read operation is =80% and write operation=90%.
Whenever a page fault occurs,the associated block must be brought from Main memory to cache for both read and write operation....read frequency=40%,write frequency =60%.
Assume CPU bus can transfer 1 word at a time.
1.what is avg access time if write through scheme is used?
Answer:
First write all the things you need for calculation.
Block size = 16 words
Cache access time = 10ns
Main Memory access time = 50ns
Cache Hit ratio:
Read hit = 80%
Read miss = 20%
Write hit = 90%
Write miss = 10%
Read operation frequency = 40%
Write operation frequency = 60%
------------------
1. If write through scheme is used:
First you should do this...
Avg access time = (40%)(Avg Read access time) + (60%) (Avg Write access time)
(We have just divided the total number of operations into read and write operations, as 40% are read operations and 60% are write operations)
.....................................
Now similarly divide the Avg read access time and Avg Write access time,
Avg Read access time = (80%)(Avg Read hit time) + (20%)(Avg Read miss time)
Avg Write access time = (90%)(Avg Write hit time) + (10%)(Avg Write miss time)
......................................
Now refer to the theory part i mentioned above for write through scheme.
Avg Read hit time = 0(Main memory) + 10(cache), since no memory access is required and 1 cache read is required.
Avg Read miss time = 16*50(Main memory) + (1+16+1)*10(cache),1st cache read is a miss, then memory must send 16 words(Block size ) to the cache {note: 16 memory access and 16 cache access are required for this transfer} and then 1 final cache read is required to get the data.
Avg Write hit time = 1*50(Main memory) + 10(cache), here cache must send the word written to the memory
Avg Write miss time = (16+1)*50(Main memory) + (1+16+1)*10(cache), here Memory must send to cache 16 words (Block size) and then Cache must send a word to memory.
........................................
Now just wrap everything up and get the answer.
Avg access time = (40%){ (80%)(10) + 20%(260) } + (60%){ (90%)(60) + (10%)(1030) }
= (0.4) {8 + 52} + (0.6) {54 + 103}
= (0.4) {60} + (0.6) { 157 } = 118.2 ns
There is also another method using stall frequency which is a faster method. But in order to do that you need to be very thorough in applying all data. This method is slower but will always give you the exact accurate answer with no errors.
------------------------------------------------------------
Additional Task:
Do extend the above question for write back cache policy. Here you will need ratio of pages modified. Assume 20% of pages are modified. Now just imagine how we solved it for write through cache and use it to solve for write back cache policy. Post your answers on comments. I will verify it when i get some time...
