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

3.18.2009

Cache Memory - Set Associative Mapped Cache

Set Associative mapping scheme combines the simplicity of Direct mapping with the flexibility of Fully Associative mapping. It is more practical than Fully Associative mapping because the associative portion is limited to just a few slots that make up a set.

In this mapping mechanism, the cache memory is divided into 'v' sets, each consisting of 'n' cache lines. A block from Main memory is first mapped onto a specific cache set, and then it can be placed anywhere within that set. This type of mapping has very efficient ratio between implementation and efficiency. The set is usually chosen by

Cache set number = (Main memory block number) MOD (Number of sets in the cache memory)

If there are 'n' cache lines in a set, the cache placement is called n-way set associative i.e. if there are two blocks or cache lines per set, then it is a 2-way set associative cache mapping and four blocks or cache lines per set, then it is a 4-way set associative cache mapping.

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.

Let us try 2-way set associative cache mapping i.e. 2 cache lines per set. We will divide 16K cache lines into sets of 2 and hence there are 8K (214/2 = 213) sets in the Cache memory.

Cache Size = (Number of Sets) * (Size of each set) * (Cache line size)

So even using the above formula we can find out number of sets in the Cache memory i.e.

219 = (Number of Sets) * 2 * 25

Number of Sets = 219 / (2 * 25) = 213.

Set Associative Mapped CacheWhen an address is mapped to a set, the direct mapping scheme is used, and then associative mapping is used within a set.

The format for an address has 13 bits in the set field, which identifies the set in which the addressed word will be found if it is in the cache. There are five bits for the word field as before and there is 14-bit tag field that together make up the remaining 32 bits of the address as shown below:
Set Associative Mapped CacheAs an example of how the set associative cache views a Main memory address, consider again the address (A035F014)16. The leftmost 14 bits form the tag field, followed by 13 bits for the set field, followed by five bits for the word field as shown below:
cache memory - Set Associative mapped
In the below example we have chosen the block 14 from Main memory and compared it with the different block replacement algorithms. In Direct Mapped cache it can be placed in Frame 6 since 14 mod 8 = 6. In Set associative cache it can be placed in set 2.
cache memory - Set Associative mappedCheckout one more solved problem below.
cache memory - Set Associative mapped
References


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

2. Computer Architecture And Organization: An Integrated Approach - By Murdocca & Vincent Heuring

23 comments :

  1. Michael Antragon

    2^19 / (2^2 * 2^5) = 2^13.???????

    19-(2+5)= 12

    ReplyDelete
  2. "We will divide 16K cache lines into sets of 2 and hence there are 8K (2^14/2 = 2^12) sets in the Cache memory."

    (2^14/2^1 = 2^12) ???
    14-1=13

    Excellent explanations, thanks!

    ReplyDelete
  3. in the explanation you said
    14 mod 8=6
    thats why it is placed in set6
    how?

    ReplyDelete
  4. It is not placed in set 6. In direct Mapped cache we place it in cache slot 6.

    "In Direct Mapped cache it can be placed in Frame 6 since 14 mod 8 = 6."

    "In Set associative cache it can be placed in set 2."

    Just check the post on Direct Mapped cache even

    ReplyDelete
  5. I had a question.

    I can't understand exactly how does the set associative caching helps improve speed(not to continually replace blocks in cache like in direct map caching, which causes cash trashing)?

    When you stated:

    if we take block 14 it can be placed in set 2

    lets say:
    the next instruction requires block 18( 18 mod 4 = 2), so it can be placed in set 2 again, does it remove the data which was there, which we got when we placed block 14? Can block 14 be placed in set 2 frame 0 and block 18 be placed in set 2 frame 1 at same time( or only 1 block in the set can have a valid bit)?

    When is a set replaced in cache with a new set( new information) from main memory?


    If the questions I asked are not clear I can try to explain in more detail if needed?

    Can someone help? Thx

    ReplyDelete
  6. I can't understand exactly how does the set associative caching helps improve speed(not to continually replace blocks in cache like in direct map caching, which causes cash trashing)?

    >>Incase of set associative the placing of a mainmemory block into cache memory is random not like direct mapping where we say n memory blocks to one single cache slot. In that case if my data is in continous memory blocks in main memory then I should keep on replacing the same cache slot.

    lets say:
    the next instruction requires block 18( 18 mod 4 = 2), so it can be placed in set 2 again, does it remove the data which was there, which we got when we placed block 14? Can block 14 be placed in set 2 frame 0 and block 18 be placed in set 2 frame 1 at same time( or only 1 block in the set can have a valid bit)?

    >>It just chooses the set then depending upon the set size we can place in any of the frames.

    When is a set replaced in cache with a new set( new information) from main memory?

    >> We dont replace the whole set once as u said if u trying to use memory block 14 and 18 then the set will be replaced.

    ReplyDelete
  7. so in the end just to clarify, like the example you gave about 2 -way set associative cash mapping. When we choose block 14 and place it in set 2 and we choose for example to put it in block 0 (so it will be in set 2, block 0) and then the program request block 18 from main memory, will it store the information/data in set 2, block 1 or will it replace the set with the new data from block 18 of the main memory.

    In a sense what i am asking is can the frames(blocks) 0 and 1 of set 2 in cache be occupied at the same time with different mappings to different block in main memory( such as block 14 & 18)?


    If they can occupy the same set at different frames(0 and 1):


    Then if the next instruction(address) is main memory block 22( 22 mod 4 = 2), it will be mapped(placed) in set 2 of the cache but the two frames(blocks), which are 0 and 1 are already taken by 14,18 so it will have to overwrite one of them?


    Thank you in advance.

    ReplyDelete
  8. Sorry I am not able to get your question ..

    In set associative mapping as you said if main memory blocks 14 and 18 are in cache set 2 at blocks 0 and 1 and if you want main memory block 22 then one block from cache set has to be replaced with main memory block 22. It might be block 0 or 1 and it depends purely on the usage criteria of those blocks.

    Just consider if you got cache set of size more than 5 then if you are using continuous main memory blocks then we dont need to replace blocks in cache more often as we do in direct mapping.

    ReplyDelete
  9. Thx, i think i got it now.

    ReplyDelete
  10. How do we determine the total number of bits in 'the whole cache' directory in a 4-way set associative cache directory ? Thank you

    ReplyDelete
  11. now, since we know how to find which set to load/store our data, i can't understand how to determine which way to load/store our data to?
    (in two-way set associative cache)

    ReplyDelete
  12. salam! Very comprehensive explanation.................

    ReplyDelete
  13. Very useful, thanks a lot for the explanation.

    ReplyDelete
  14. Thank You Very Much...

    ReplyDelete
  15. How do we estimate number of n-way set associative?

    ReplyDelete
  16. sir,
    is the tag in set assosiative assosiated to each word or a block in a set

    ReplyDelete
  17. Cache Size = (Number of Sets) * (Size of each set) * (Cache line size)


    it's wrong, i thought

    Cache Size = (Number of Sets) * (no of cache lines per each set) * (size of each block)

    ReplyDelete
  18. Great man! Very well explained document.
    Thanks

    ReplyDelete
  19. This is a great tutorial. Thanks.

    ReplyDelete
  20. Assume the following information regarding a 2-level memory-hierarchy system:

    The physical address is 16 bits.

    The block size is 32 bytes.

    The cache capacity is 8 KB.

    Number of cache entries is a power of 2.

    If a set-associative cache is to be used, what are the possible options to partition the address to fill the following table. Based on your answer, reduce or increase the table size appropriately to find all possibilities.

    Option Block-offset size Number of cache entries Set-associativity Number of segments in memory

    1

    2

    3

    ReplyDelete

Your comments are moderated