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

3.18.2009

Cache Memory - Fully Associative Mapped Cache

If a Main memory block can be placed in any of the Cache slots, then the cache is said to be mapped in fully associative.

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.

In fully associative mapping any one of the 128M (i.e. 227) Main memory blocks can be mapped into any of the single Cache slot. To keep track of which one of the 227 possible blocks is in each slot, a 27-bit tag field is added to each slot which holds an identifier in the range from 0 to 227 – 1. The tag field is the most significant 27 bits of the 32-bit memory address presented to the cache.
Fully Associative Mapped Cache
In an associative mapped cache, each Main memory block can be mapped to any slot. The mapping from main memory blocks to cache slots is performed by partitioning an address into fields for the tag and the word (also known as the “byte” field) as shown below:
Fully Associative Mapped Cache
When a reference is made to a Main memory address, the cache hardware intercepts the reference and searches the cache tag memory to see if the requested block is in the cache. For each slot, if the valid bit is 1, then the tag field of the referenced address is compared with the tag field of the slot. All of the tags are searched in parallel, using an associative memory. If any tag in the cache tag memory matches the tag field of the memory reference, then the word is taken from the position in the slot specified by the word field. If the referenced word is not found in the cache, then the main memory block that contains the word is brought into the cache and the referenced word is then taken from the cache. The tag, valid, and dirty fields are updated, and the program resumes execution.

Associative mapped cache has the advantage of placing any main memory block into any cache line. This means that regardless of how irregular the data and program references are, if a slot is available for the block, it can be stored in the cache. This results in considerable hardware overhead needed for cache bookkeeping.

Although this mapping scheme is powerful enough to satisfy a wide range of memory access situations, there are two implementation problems that limit performance.
  • The process of deciding which slot should be freed when a new block is brought into the cache can be complex. This process requires a significant amount of hardware and introduces delays in memory accesses.
  • When the cache is searched, the tag field of the referenced address must be compared with all 214 tag fields in the cache.

10 comments :

  1. It is excellent tutorial for fundamentalls and basic level people.It can be understood by assuming.{MAHESWARA 9493818580

    ReplyDelete
  2. very nice,vivid and clear explanation. thanks a lot man.

    Addishiwot T. from Ethiopia

    ReplyDelete
  3. Very Good explaination !

    ReplyDelete
  4. i want to say one thing, that there is no clear cut explanation whether cache memory and associative memory carry the same meaning or they are diffrent, if they are diffrent than what is the meaning of the word associative cache.

    however, i am lecturer of computer applications but i am confused regarding associative memory.

    ReplyDelete
    Replies
    1. being an lecturer of cmp app, u dnt knw tht, whether the "Associative is a kind of memory or technique"..

      Delete
  5. Can everyone help me? I need to calculate the size of the block Number for (fully) associative mapping? How we can do it? I do not have any idea. I just know hot to find the offset and the tag size. Thanks in advance!

    ReplyDelete
  6. Cache Memory is a memory that has high access speed than main memory.
    "Associative Memory"-it is not a memory.
    "Associative Mapped Cache" or "Associative Mapping" is the technique used by cache memory

    to decide which block of main memory reside in the cache memory and also decide the way how CPU search a block in cache memory,

    so that CPU access it directly from cache memory than from main memory.

    ReplyDelete
  7. Associative - Denoting computer storage in which items are identified by content rather than address.

    ReplyDelete
  8. Apparent explanation!

    Thanks
    Dixit

    ReplyDelete

Your comments are moderated