Effective access time vs average access time

Question

Can anyone explains when to use this formulas?

Average memory access time (AMAT)

AMAT = Hit Time + Miss Rate * Miss Penality

OR

• Effective Access Time:

1. Hit Rate * Hit time+ Miss Rate * Miss Penality

2. [ (H)(TLB access time + mem access time) + (1-H)(TLB access + PT access + mem access)]

Answer 1

I'm not going to say when to use these formulas. Because even if I say all the formula there is very little chance any one get it right. Because IIT profs. are not making questions for those remembering formula to answer. They just want to check if one knows the concept properly.

In terms of memory, there are so many scenarios even if we consider GATE level questions. Some common cases are

1. Cache memory
   Effective Memory Access Time = Cache access time * hit rate + miss rate * Miss penalty
   The above formula is too simple and given in many texts. But it hides what is exactly miss penalty. Because it depends on the implementation and there are simultenous cache look up and hierarchical. Unless otherwise stated in question always assume hierarchical access (case for write through cache explained below). So, for hierarchical cache, we can have the formula:
   Effective Memory Access Time = Cache access time * hit rate + (1 - hit rate) * (cache access time + main memory access time)
   = Cache access time + (1 - hit rate) * main memory access time
2. Multi level cache
   The above formula can be extended to $n+1$ levels for $n$ levels of caches and main memory
3. Write Through Cache
   This is applicable when question distinguishes between read and write accesses. When the cache is write through it means all writes going to main memory as well as to cache. Considering the best practical implementation, this should always be considered to be done in parallel and hence only the main memory write matters.
4. Memory access times can be given in unit of blocks/words and we must use the appropriate one as per the question. When a level 1 access from level 2, block size to be used is of level 1 and similarly for other levels.
5. In all the above cases we considered only cache and main memory. But if virtual memory is used, we have to consider TLB, page table access etc. TLB is like a cache for page table.
6. Cache access can be before TLB access - if cache is virtually indexed and virtually tagged - less common
7. Cache access is after TLB access - if cache is physically indexed and physically tagged - again less common as if TLB is missed we need a main memory lookup for page tables before coming to cache
8. Cache access is together with TLB acess - if cache is virtually indexed and physically tagged - most common. Here, cache indexing and TLB look-up happens simultaneoulsy and at time of tag comparison, we require physical address.
9. So, question can come from any of the above cases, so what formula should I give?

Comments

Thanks for this detailed answer.

---

What i summarize is :

By default cache access is Hierarchical.[ here by default means if no hint is given in the question ] { Reason : simultaneous is a more specialized technique and it also reduces access time even though marginally , hence not a practical scenario . }

Snap from Stallings :

The picture shows it follows Hierarchical technique ..

In all previous gate papers at least some hint is given whether to follow simultaneous access or hierarchical access . And most of the cases we follow simultaneous technique through some hint or keywords. 

In case of Write - Through Technique 

we take Simultaneous access .

in case of Write - Back Technique 

we take Hierarchical access . 

Also for read access normally data is searched hierarchically . 

---

Thanx Bikram sir. Nice explanation and great observation. Thanx for clearing the doubts.

---

One doubt- in write through cache why are we taking reads also simultaneous??

---

@sushmita

1) write back means writing on the cache and only when a block has to be replaced in the cache we write back the contents of that block to the main memory thus making it a Hierarchical access  . 

2) write through means writing on to the cache and main memory simultaneously whenever the contents  are modified , thus making it simultaneous access.
 

---

I just wanna know that in write through, i know we write simultaneously in memory and cache, but is it necessary that reads are also simultaneous?? It it mandatory for read and write to follow same policies?

---

@Sushmita No, not a requirement to follow same policy. In fact by default we should not assume the same. In write through cache, why is it simultaneous access? Because it makes more sense as 100% of time (no decision to be made here) cache and main memory are going to be accessed for write operation. For read operation, we never know if main memory will be accessed until cache is accessed. So, hierarchical access makes more practical sense.

---

Thanx Arjun sir. understood. :)

---

Why isn't practical to do the same for read?

We'll be certainly saving some time if we're doing the reads simultaneously.If some architecture provides the simultaneously access for write the same should go for read.

---

@prayas

No if we do simultaneous read as well, then performance will decline, because for all accesses we are going to memory, then what is the benefit of using cache ? Actually cache was introduced so that we have to acccess main memory less number of times.

---

What is the difference between two formulae mentioned in point 1? when do we not multiply hit ratio with cache access time? I used first formula in a question but ended up with wrong answer, because the given solution used the latter one. But I couldn't understand the logic behind it. Kindly explain. @Arjun

---

What do you mean by getting wrong answer? Most of the test series answers are wrong anyway especially in this topic.

---

This link says:

 The processor uses both for each memory operation: it first uses the TLB to convert from virtual address to physical address, then it checks the data cache to speed up the process of reading the value stored in memory at that address.

This also makes sense because each cache entry contains a physical address and the value of memory at that address, So to get a value from the cache we first need to find its physical address (which could be found on our TLB).

So my question to Sir is how can we access the cache together with TLB access? Should’nt we always go to the TLB first no matter what? 

Answer 2

When u get a hit in the TLB,it generates the physical address or the frame address that maps onto the appropriate frame in the main memory...so TLB access time + main memory time..

 

But when its a miss, that means u have searched the entire TLB for the page number but u didnt get so TLB access is there.. Now u have to access the page table to search the appropriate page number so the page table  access time is included. Now comes the mapping to the appropriate frame.. Once u do that main memory time wud be included.. Hence the equation.. Remember that If u don't find the page in the page table it will generate a page fault then u have to fetch it from the disk...

Answer 3

Average Memory Access time is used in the context of Cache. AMAT = Hit time + Miss Rate * Miss Penalty.

Effective Memory Access time is used in the context of paging. EMAT = Hit Rate * TLB Time + Miss Rate * Miss Penalty

The difference lies in the fact that the cache will always be serached for, irrespective of if it's a hit or a miss, and this is what constitutes the majority of cache access time; whereas in case of TLB the search time is a negligible fraction of TLB access time and hence it is taken into consideration only when there is a hit.

Comments

what is "search" in TLB? Aren't the entries indexed?

Also, what about paging with caching?

---

Yes, the entries are indexed. That's why the time taken to locate/search an entry is negligible compared to access time of TLB itself. Although the formulas themselves are not bound to any particular mechanism, but i guess most of the text books mention Average Mem access time while talking about cache and Effective Mem access time otherwise.

---

No. Your logic is not sound. TLB and first level of cache are mostly located at same level of memory and so, should follow the same formula. If hit time is negligible for TLB it must be the same for first level cache. We always consider TLB time or cache time irrespective of "hit rate" when cache/TLB access is hierarchical.

---

What's your conclusion on the two formulas which are given in books?
In Computer Organization-Peterson, Hennessey, Avg Memory Access Time = Hit Time + Miss Rate * Miss Penalty. This formular is given in the context of a cache hit/miss. If I compare it to the formula Effective Memory Access Time = Cache access time * hit rate + miss rate * Miss penalty, it makes sense only if Miss Penalty is equal to Memory access time in case of cahe. Is  that so?