Bài tập 4-way associative so sánh tối đa tag

Following diagram shows the organization of 2-way set associative 0.5KB cache memory with 32 bytes cache line size.

How does this N-way set associativity works? let us answer this by the example above (2-way set associative cache). Now when an access request address is received by the cache controller, the 'set' address portion of this full address, indicated by green bits, is used to identify a set of 2 cache lines (instead of 1 as in direct mapped cache). The cache controller now compares the TAG of the input address ( 8 bits) vs the 2 TAGS stored in the set identified by the SET Address (3 green bits). If a match occurs, its a cache HIT, and this time the cache HIT also produce where in the set of tags, the match tag is stored. For example the matched TAG could be the 0th tag within set of 2 tags, or it could be the 1st tag within the set of 2 tags. This is the address of the matched tag withing a set of 2 tags. This is shown by purple bits in above diagram. This address is then used by the DATA RAM to identify the cache line with in the 'SET' identified by the set address. And that is how the cache controller gets to right cache line. A word in that cache line is then identified using offset address.

Example: 4-way set associative cache: Full address = 16 bits: Memory size = 0.5 KB Cache line = 32 bytes (256 bits). Associativity = 4-Way

Offset address = Log2(cache line size in bytes) = Log2(32) = 5 bits Total number of cache lines = memory size / cache line size = 512/32 = 16 Number of Sets = Number of cache lines / Associativity = 16/4 = 4. Set address width = Log2(Number of sets) = Log2(4) = 2. TAG width = Full address width - SET width - Offset width = 16 - 2 -5 = 9 Bits.

Example to calculate the TAG width, SET Address width, Offset bits:

Address size = 32 bits, cache line size is 256 bits (32 bytes), cache size is 1 MB. Associativity = 4-way associative.