Week 7 Mapping Function Set Associative.pdf

Week 6 Mapping Function: Set Associative Ms. Ayyah Fadhl Objective ❑By the end of the lecture, you will know : ❑Set Associative Cache Mapping Function. ❑Advantage of Set Associative Mapping. Mapping Function ❑Why do we need Mapping Function? ❑There are fewer cache lines than ma...

Week 6 Mapping Function: Set Associative Ms. Ayyah Fadhl Objective ❑By the end of the lecture, you will know : ❑Set Associative Cache Mapping Function. ❑Advantage of Set Associative Mapping. Mapping Function ❑Why do we need Mapping Function? ❑There are fewer cache lines than main memory blocks, an algorithm is needed for mapping main memory blocks into cache lines. ❑A method is needed to determining which main memory block currently occupies a cache line. Mapping Function ❑The choice of the mapping function dictates how the cache is organized. ❑Three techniques can be used: ❑Direct. ❑Associative. ❑Set-associative. Direct Mapping. ❑Advantage: The direct mapping technique is simple and inexpensive to implement. ❑Disadvantage: ❑There is a fixed cache location for any given block. ❑Thus, if a program happens to reference words repeatedly from two different blocks that map into the same line, then the blocks will be continually swapped in the cache, and the hit ratio will be low (Conflict Miss). Associative Mapping. ❑Advantage: with associative mapping, there is flexibility as to which block to replace when a new block is read into the cache. (Problem of Conflict Miss resolved). ❑Disadvantage: The principal disadvantage of associative mapping is the complex circuitry required to examine the tags of all cache lines in parallel. Set Associative Mapping ❑Set- associative mapping is a compromise that exhibits the strengths of both the direct and associative approaches while reducing their disadvantages. Set Associative Mapping ❑In set associative, the cache consists of number sets, each of which consists of a number of lines. m=v*k i = j modulo v ❑Where ❑i = cache set number ❑j = main memory block number ❑m = number of lines in the cache ❑v = number of sets. ❑k = number of lines in each set. Set Associative Mapping ❑This is referred to as k-way set-associative mapping. ❑With set-associative mapping, block Bj can be mapped into any of the lines of set i. Set Associative Mapping ❑The figure illustrates this mapping for the first v blocks of main memory. In the figure we have v sets, each with k lines. Set Associative Mapping ❑For set- associative mapping, the memory address is interpreting the memory address as three fields: ❑Word: the w word bits identify a unique word within a block of main memory. ❑Set: The d set bits identifies one of v sets of the cache (which cache line a particular block will be mapped to). ❑Tag: The s-d bits identify which particular block is inside the line. ❑(Set+Tag ): The s bits of the Tag and Set fields specify one of the 2𝑠 blocks of main memory.  Physical Address Interpretation In Direct vs Associative Mapping. Direct Mapping Associative Mapping Set Associative Mapping ❑ Address length = (s + w) bits. ❑ Address length = (s + w) bits ❑ Address length = (s + w) bits ❑ Number of addressable units = ❑ Number of addressable units = ❑ Number of addressable units = 2𝑠+𝑤 words or bytes. 2𝑠+𝑤. 2𝑠+𝑤. ❑ Block size = line size = 2𝑤 bits. ❑ Block size = line size = 2𝑤 bits. ❑ Block size = line size = 2𝑤 bits. ❑ Number of blocks in main ❑ Number of blocks in main ❑ Number of blocks in main memory memory = memory = 𝑀𝑎𝑖𝑛 𝑀𝑒𝑚𝑚𝑜𝑟𝑦 𝑆𝑖𝑧𝑒 2𝑠+𝑤 𝑠 𝑀𝑎𝑖𝑛 𝑀𝑒𝑚𝑚𝑜𝑟𝑦 𝑆𝑖𝑧𝑒 2𝑠+𝑤 𝑠 𝑀𝑎𝑖𝑛 𝑀𝑒𝑚𝑚𝑜𝑟𝑦 𝑆𝑖𝑧𝑒 2𝑠+𝑤 𝑠 = = 𝑤 = 2 = = 2 = = 2 𝐵𝑙𝑜𝑐𝑘 𝑆𝑖𝑧𝑒 2 𝐵𝑙𝑜𝑐𝑘 𝑆𝑖𝑧𝑒 2 𝑤 𝐵𝑙𝑜𝑐𝑘 𝑆𝑖𝑧𝑒 2 𝑤  Physical Address Interpretation In Direct vs Associative Mapping. Direct Mapping Associative Mapping Set Associative Mapping ❑Number of lines in cache = m = 2𝑟 ❑Number of lines in cache = ❑Number of Lines in set= k undetermined ❑Size of cache = 2 𝑟+𝑤 bits. ❑Number of sets= v= 𝟐𝒅 ❑ Size of tag = s bits. ❑Size of tag = (s - r) bits. ❑Number of lines in cache = m=kv= k* 𝟐𝒅. ❑Size of Cache = k* 𝟐𝒅+𝒘. ❑ Size of tag = (s-d) bits. Set Associative Mapping: Advantage ❑With fully associative mapping, the tag in a memory address is quite large and must be compared to the tag of every line in the cache. (Disadvantage of Fully associative). ❑With k- way set- associative mapping, the tag in a memory address is much smaller and is only compared to the k tags within a single set. (Advantage of Set associative). Notes on Set Associative Mapping. ❑In the extreme case of v = m, k = 1, the set-associative technique reduces to direct mapping. (Direct Mapping). ❑In the extreme case of v = 1, k = m, the set-associative technique reduces to fully associative mapping. (Associative Mapping). Summary ❑Now, you should know : ❑Set Associative Cache Mapping Function. ❑Advantage of Set Associative Mapping.