1
$\begingroup$
  • There are Two Write Hit policies: Write Through and Write back
  • There are Two Write miss policies: Write Allocate and No Write Allocate
  • There are two memory access techniques: simultaneous and hierarchical access

Can any gentleman PLEASE write formulas for different combinations ?

I am having very important competitive exam that can change my life, and i am struggling with these methods badly.


For instance one may consider following example and please show me relevant modification of this example.
Question : In a certain system the main memory access time is 100 ns. The cache is 10 time faster than the main memory and uses the write though protocol. If the hit ratio for read request is 0.92 and 85% of the memory requests generated by the CPU are for read, the remaining being for write; then the average time consideration both read and write requests is

a) 14.62ns

b) 348.47ns

c) 29.62ns

d) 296.2ns

PS:- I know meaning or working of all techniques but don't know how can i drive formulas. Please do it, i really need that badly. It would be GREAT help.

Thnks in advance.

$\endgroup$

1 Answer 1

1
$\begingroup$

When you want a general formula for a particular case, just derive it.

Let the main memory access time be $x$, and the cache access time be $y$. Let the hit ratio be $h$ and the fraction of requests that are reads be $p$.

Now, $$\begin{align}\text{Average access time}&=\text{Weighted average of read and write times}\\&=\text{Fraction of reads}\times\text{Average read time}+\text{Fraction of writes}\times\text{Average write time}\tag1\end{align}$$

Let us now go through the read process. Firstly, there are two possibilites - a cache hit or a miss. If it is a hit, the cache access time is the total read time. If it is a miss, then the total read time is the sum of the time taken to access the cache and the time taken to access the memory. The fraction of hits is given by the hit ratio. Again, we take the weighted average.

$$\begin{align}\text{Average read time}&=\text{Fraction of hits}\times\text{Cache access time}+\text{Fraction of misses}\times(\text{Cache access time}+\text{Memory access time})\\ &=hy+(1-h)(x+y)\tag2\end{align}$$

Now, the writes. It is given that the write policy is the write through policy. This means that when a write is made, irrespective of a hit or a miss, memory is accessed as well. As the memory access time dominates over the cache access time, and the hit ratio for writes is not given, ignore the difference in the times of accessing just the memory and accessing the cache and the memory.

$$\begin{align}\text{Average write time}&=\text{Main memory access time}=x\tag3\end{align}$$

Combining $(1),(2),(3)$, we get, $$\begin{align}\text{Average access time}&=p\left[hy+(1-h)(x+y)\right]+(1-p)x\end{align}$$

Here, $p=0.85,h=0.92,x=100\text{ns},y=10\text{ns}$. Substituting, $$\begin{align}\text{Average access time}&=0.85\left[0.92\times10+(1-0.92)(100)\right]+(1-0.85)\times100\\ &=0.85\times17.2+15\\ &=29.62\text{ns}\end{align}$$

Similarly, you can attempt the other cases mentioned in your question.

$\endgroup$
1
  • $\begingroup$ thank you so much, please mention Average write time if it were $\text{write back}$. $\endgroup$ Commented Feb 4, 2017 at 6:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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