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 (2³²), with each byte directly addressable by a 32-bit address. We will divide Main memory into blocks of each 32 bytes (2⁵). Thus there are 128M (i.e. 2³²/2⁵ = 2²⁷) blocks in Main memory.

We have a Cache memory of 512KB (i.e. 2¹⁹), divided into blocks of each 32 bytes (2⁵). Thus there are 16K (i.e. 2¹⁹/2⁵ = 2¹⁴) 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. 2²⁷) Main memory blocks can be mapped into any of the single Cache slot. To keep track of which one of the 2²⁷ 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 2²⁷ – 1. The tag field is the most significant 27 bits of the 32-bit memory address presented to the 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:

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 2¹⁴ tag fields in the cache.