/* Ajith - Syntax Higlighter - End ----------------------------------------------- */

3.18.2009

Cache Memory - Direct Mapped Cache

If each block from main memory has only one place it can appear in the cache, the cache is said to be Direct Mapped. Inorder to determine to which Cache line a main memory block is mapped we can use the formula shown below

Cache Line Number = (Main memory Block number) MOD (Number of Cache lines)

Let us assume we have a Main Memory of size 4GB (232), with each byte directly addressable by a 32-bit address. We will divide Main memory into blocks of each 32 bytes (25). Thus there are 128M (i.e. 232/25 = 227) blocks in Main memory.

We have a Cache memory of 512KB (i.e. 219), divided into blocks of each 32 bytes (25). Thus there are 16K (i.e. 219/25 = 214) blocks also known as Cache slots or Cache lines in cache memory. It is clear from above numbers that there are more Main memory blocks than Cache slots.

NOTE: The Main memory is not physically partitioned in the given way, but this is the view of Main memory that the cache sees.

NOTE: We are dividing both Main Memory and cache memory into blocks of same size i.e. 32 bytes.

A set of 8k (i.e. 227/214 = 213) Main memory blocks are mapped onto a single Cache slot. In order to keep track of which of the 213 possible Main memory blocks are in each Cache slot, a 13-bit tag field is added to each Cache slot which holds an identifier in the range from 0 to 213 – 1.

All the tags are stored in a special tag memory where they can be searched in parallel. Whenever a new block is stored in the cache, its tag is stored in the corresponding tag memory location.
Direct Mapped Cache
When a program is first loaded into Main memory, the Cache is cleared, and so while a program is executing, a valid bit is needed to indicate whether or not the slot holds a block that belongs to the program being executed. There is also a dirty bit that keeps track of whether or not a block has been modified while it is in the cache. A slot that is modified must be written back to the main memory before the slot is reused for another block. When a program is initially loaded into memory, the valid bits are all set to 0. The first instruction that is executed in the program will therefore cause a miss, since none of the program is in the cache at this point. The block that causes the miss is located in the main memory and is loaded into the cache.

This scheme is called "direct mapping" because each cache slot corresponds to an explicit set of main memory blocks. For a direct mapped cache, each main memory block can be mapped to only one slot, but each slot can receive more than one block.

The mapping from main memory blocks to cache slots is performed by partitioning an main memory address into fields for the tag, the slot, and the word as shown below:
Direct Mapped Cache
The 32-bit main memory address is partitioned into a 13-bit tag field, followed by a 14-bit slot field, followed by a 5-bit word field. When a reference is made to a main memory address, the slot field identifies in which of the 214 cache slots the block will be found if it is in the cache.

If the valid bit is 1, then the tag field of the referenced address is compared with the tag field of the cache slot. If the tag fields are the same, then the word is taken from the position in the slot specified by the word field. If the valid bit is 1 but the tag fields are not the same, then the slot is written back to main memory if the dirty bit is set, and the corresponding main memory block is then read into the slot. For a program that has just started execution, the valid bit will be 0, and so the block is simply written to the slot. The valid bit for the block is then set to 1, and the program resumes execution.

Check out one more solved problem below


References


1. Computer Architecture Tutorial - By Gurpur M. Prabhu.

32 comments :

  1. kamu bikin sendirikah programnya??? kalo iya, boleh liat source codenya ???

    ReplyDelete
  2. Hey what is the language you are speaking hanna .... i did not get you

    ReplyDelete
  3. Hi,

    Does the size of each main memory blocks must be the same as cache block's size?

    For instance, if size of each of main memory blocks is 16bytes, does the cache block's size also 16bytes?

    By the way, how can I get the memory calculator?

    Thanks..

    ReplyDelete
  4. Hi,

    Does the size of each main memory blocks must be the same as cache block's size?

    For instance, if size of each of main memory blocks is 16bytes, does the cache block's size also 16bytes?

    By the way, how can I get the memory calculator?

    Thanks..

    ReplyDelete
  5. Does the size of each main memory blocks must be the same as cache block's size?

    'YES' it should be same so that the data can be swapped directly into the exact location.

    What do u mean by "Memory Calculator" ?

    ReplyDelete
  6. Replies
    1. Offset byte is used to locate on of the 32 bytes (Block size)

      Dixit

      Delete
  7. Hanna is probably speaking in Bahasa Indon a subset of the Malay Language. She says,"Did you make the program yourself? If yes, can I see the source code?" -which makes completely no sense here. lol.

    Anyway thanks for the blog post. It has been really helpful in clarifying some doubts I've. Currently pursuing this subject in my course.

    Thanks

    ReplyDelete
  8. Denz, it is "Bahasa Indonesia" not Bahasa Indon. Try polite to other people.

    Thanks for article codingfreak.

    ReplyDelete
  9. nice explanation!

    Thanks

    from KFUPM
    Saudi Arabia

    ReplyDelete
  10. Thanks for the explanation! Very detailed and clear. Great job!

    ReplyDelete
  11. thanku - this is not only just one word

    arigatho !

    ReplyDelete
  12. hey this is very usefull and its language is mindblasting......
    i like i............t sapana

    ReplyDelete
  13. nice work!!

    well explained.... txx :)

    ReplyDelete
  14. Thanks for the explanations. Much clearer than my uni's lecture notes!

    ReplyDelete
  15. @denz
    may be hanna is talking about the s/ware used in screenshot of solved example... and she wants to use it...

    ReplyDelete
  16. very nic post i am studing computer architecture its help me lot..very nic
    VEry nic!

    ReplyDelete
  17. very nic post i am studing computer architecture its help me lot..very nic
    VEry nic!

    ReplyDelete
  18. Great example and informative post. Thank you!

    ReplyDelete
  19. Hi,
    Just a question

    When an entry in cache needs to be written back to main memory, how is the address in main memory calculated? Because a single cache entry can hold entries from different possible main memory locations?
    In the same line, along with cache, does the main mem addres?also stored?

    Thanks Madhu

    ReplyDelete
  20. Thank you for such a good explanation and example. Keep it up

    ReplyDelete
  21. awsome explanation, great.... i love it

    ReplyDelete
  22. in the solved example you are taking no. of tag bits as 5 but if we see the example before that ... u calculated number of tag bits as 13. The method u solved for 13 tag bits if we use the same method for the latter example .. the number if tag bits must be 2. Could you explain how u did the calculations for the latter example ?

    ReplyDelete
  23. very nice explaination in very simple language... thnx..

    ReplyDelete
  24. I have a main memory with a size of 256KB. What should be the size of the cache?

    ReplyDelete
  25. hi , how can i calculate the tag in decimal? i mean is there any direct way of calculating the tag other than getting the bits and convert it ?

    ReplyDelete
  26. Oh my word this makes so much sense now. Thanks a lot for the upload. (My UNI lecturer fails and finals is in 3 days so this is greatly appreciated)

    ReplyDelete

Your comments are moderated