[COA][ Hamacher 1.6] Cache memory

Question

1.6 Suppose that execution time for a program is directly proportional to instruction access time and that access to an instruction in the cache is 20 times faster than access to an instruction in the main memory. Assume that a requested instruction is found in the cache with probability 0.96, and also assume that if an instruction is not found in the cache, it must first be fetched from the main memory to the cache and then fetched from the cache to be executed. Compute the ratio of program execution time without the cache to program execution time with the cache. This ratio is usually defined as the speedup factor resulting from the presence of the cache.

(b) If the size of the cache is doubled, assume that the probability of not finding a requested instruction there is cut in half. Repeat Part a for a doubled cache size.

Doubt :-

Part a:)

Now in case the data is not there for cache ,then we will take from access cache first and then main memory and then cache again as per highlighted part above?So will it be Tmem+Tcache+Tcache(to fetch from cache again as per highlighted text).If cache needs to be added only one then please explain why?

part B) Does doubling cache means access time of cache is also doubled?

Answer 1

Speedup = ( execution time of without cache)/(execution time with cache)

(20+20)/(0.96*(1÷20)+(1-0.96)*((1÷20 ) +(1÷20)+20))

For part b make (1-0.96)÷2 to make it half

Comments

Care to explain?

---

It must be 20/(.96*1+.04*(20+1))

=11.1

Answer 2

part a)  to access the contents from cache it is Tcache

whenever ther is a miss , your not accessing the cache

you take from memory and load it in cache (Tmem)

now access from cache (Tcache)

thereby it is Tmem + Tcache

Answer 3

This answer is based on my understanding of what memory is:

Accessing anything from memory/cache has three stages

1. Specifying memory location by the processor to memory/cache
2. Data transfer from memory/cache to processor.
3. Memory/cache sends a signal to the processor that the data transfer is complete.

Time taken for steps 1 and 3 is negligible and we can assume that the memory access time by memory/cache is the same as data transfer time by memory/cache.

Answering Doubt a) 

If data is in the cache, these are the following sequence of steps that happen during the data transfer:

1. The processor requests the data for a memory address.
2. Cache sees that the memory address is stored in it.
3. It transfers the data
4. And sends a signal that the transfer is complete.

So here, the time taken in steps 1,2, and 4 is negligible and the time taken by step 3 is (Tcache).

If data is not in the cache:

1. The processor requests the data for a memory address.
2. Cache sees that the data for the specified memory address location is not already stored.
3. Now cache sends a request to memory to access the data of the memory address.
4. Data transfer happens between memory and cache.
5. Memory sends a signal that the transfer is complete
6. Now data transfer happens between cache and processor
7. Cache sends a signal that the data transfer is complete.

Here time taken in steps 1, 2, 3, 5, and 7 is negligible. and time taken for steps 4 and 6 is (Tmem + Tcache).

Answering Doubt b)

If the cache size is huge then it’s intuitive to think that the required data for a memory address is already stored in it. Therefore the probability of finding data of a memory location is higher when the cache size is doubled. Cache access time has nothing to do with cache size. Cache access time completely depends on the way cache is organized by hardware.

 

It’s given that Tmem = 20*Tcache.

p = 0.96

p’ = 0.04

Answer a)

(Tmem / (p*Tcache + p’(Tmem+Tcache)))

=(20*Tcache/(0.96*Tcache+0.04*(21*Tcache)))

=(20/(0.96+(0.04*21)))

= 1.111111…. is the speedup factor.

b)

here everything is same as part a) except 

p = 0.98

p’ = 0.02

Therefore speedup factor is 14.2857….