Q.2. Suppose you have a machine with a 16 entry direct-mapped cache. Each cache

Question

Q.2. Suppose you have a machine with a 16 entry direct-mapped cache. Each cache entry can hold 256 bytes of data. A program is run on this machine that makes the following memory accesses in hexadecimal (each memory address addresses a byte of data): complete all parts and show work 3F8E, 4F8E, 4F8D, 4FC2, 0000, 0000, 2F01, 4F8E, 2F67,2268,2F69, 2E32 a. How many bits wide is the cache's tag field? b. Assuming the cache is initially empty, what are the final contents of the cache after the program runs? Draw a diagram of the cache similar to the one on page 267 of the textbook, and fill in the tag fields. c. Suppose a cache hit takes 20 ns, a cache miss takes 200 ns, and a memory access without a cache takes 160 ns. How much time is saved by this cache on this program over an equivalent cacheless machine running this program? d. Give an example each of spatial and temporal memory access locality exhibited by this program

Explanation / Answer

======================================================================

Each Physical address consists of three parts: Tag, index and offset.

Tag: It is the first part of the address

Index: It is the next part of the address

Offset: The last part of the address

======================================================================

A.

Each cache entry can hold 256 bytes i.e. 2048 bits of data

and there are 16 such entries.

Sincere the number of entries is 16 the index has a length of 4 bits.

2048 bits corresponds to 11 bits (since 2^11 ---> 2048), therefore the

offest has a length of 11 bits.

Each physical memory address has a length of 16 bits (Each address consists

of 4 Hexadecimal numbers and hence requires 16 bits for addressing)

Thus the length of tag field is = 16-11-4 = 1

========================================================================

B.

Since page 267 has not been shown, an appropriate table showing the contents

of the Cache and the status of whether the address was a hit or a miss is

shown below:

----------------------------------------------------------------------------------------------------------

No. |Address |Tag |Index |offset |Hit or a miss |Reason |

----------------------------------------------------------------------------------------------------------

1. |3F8E |0 |0111 |11110001110 |Miss |Access for first Time |

2. |4F8E |1 |0001 |11110001110 |Miss |Access for first time |

3. |4F8D |1 |0001 |11110001101 |Hit |From 2's index and Tag |

4. |4FC2 |1 |0001 |11110110010 |Hit |From 2's index and Tag |

5. |0000 |0 |0000 |00000000000 |Miss |Access for first Time |

6. |0000 |0 |0000 |00000000000 |Hit |From 5's index and tag |

7. |2F01 |0 |0101 |11100000001 |Miss |differs from 1's and 5's index |

8. |4F8E |1 |0001 |11110001110 |Hit |Same as 2 |

9. |2F67 |0 |0101 |11101100111 |Hit |From 7's Tag and Index |

10. |2268 |0 |0100 |01001100111 |Miss |differs from 9's index |

11. |2F69 |0 |0101 |11101101001 |Hit |same as 7's Index and Tag |

12. |2E32 |0 |0101 |11000110010 |hit |same as 7's Index and Tag |

------------------------------------------------------------------------------------------------------------

Cache Diagram:

------------------------------------------

Index | Data |

------------------------------------------

0111 |1's data |

------------------------------------------

0001 |2's data |

|8's data |

------------------------------------------

0000 |5's data |

------------------------------------------

0101 |7's data |

------------------------------------------

====================================================================================

C. From the above tables we can see that there are 7 hits and 5 misses:

There for access time using the cache is: 7 x 20 + 5 x 200 = 1140 ns

Without using cache the access time is : 12 x 160 = 1920 ns

Time saved using the cache : = 780 ns

====================================================================================

D. This program exhibits temporal and spacial locality properties:

Temporal locality means that items that have been recently referred are likely

to be refered in the near future:

eg: Memory Location 0000 has been refered successively

Spatial locality means that the address that are spacially close are likely to be

addressed with a small separation in time.

eg: Address 4F8E and 4F8D were addressed successively

=====================================================================================

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.