Set Associative cache memory with example

Set Associative Mapping

A compromise that provides strengths of both direct and associative approaches

• Cache is divided into a number of sets of lines

• Each set contains a fixed number of lines

• A given block maps to any line in a given set determined by that block’s address

— e.g. Block B can be in any line of set i

• e.g. 2 lines per set

— 2-way associative mapping

— A given block can be in one of 2 lines in only one set

• m = v * k

— Where m = number of lines in cache, v = number of sets and k = lines/set

— Lines in cache = sets * lines per set

• i = j modulo v

— Where I = set number and j = main memory block number

— Set number = block number % number of sets

• This is referred to as a “k-way” set associative mapping

• Block Bi can be mapped only into lines of set j.

K-Way Set Associative Cache Organization

Set Associative Mapping Example

• Assume 13 bit set number

• Block number in main memory is modulo 213 (0010 0000 0000 0000 = 2000h

• 000000, 002000, 004000, … map to same set

Set Associative Mapping Address Structure
• Cache control logic sees address as three fields: tag, set and word

• Use set field to determine cache set to look in

• Compare tag field to see if we have a hit

• e.g     — Address Tag Data Set number

— 1FF 7FFC 1FF 12345678 1FFF

— 001 7FFC 001 11223344 1FFF

• Tags are much smaller than fully associative memories and comparators for simultaneous lookup are much less expensive

Example :

 For more refer : 

                  http://aturing.umcs.maine.edu/~meadow/courses/cos335/COA04.pdf