Cache memory Replacement Policy, Virtual MemorySlide 2Slide 3Slide 4Slide 5Slide 6Slide 7Memory/Cache Related TermsReplacing DataReplacement Policies for Associative CacheReplacement in Set-Associative CacheWriting DataCache PerformanceAssociative CacheDirect-Mapped Cache2-Way Set Associative CacheAssociative Cache (FIFO Replacement Policy)Two-way set associative cache (LRU Replacement Policy)Associative Cache with 2 byte line size (FIFO Replacement Policy)Direct-mapped Cache with line size of 2 bytesTwo-way set Associative Cache with line size of 2 bytesPage Replacement - FIFOSlide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Before VM…Solution to Memory ConstraintsImplementations of VMMemory IssuesPagingAddress MappingSlide 47Slide 48Paging ImplementationSlide 50Memory MappingMemory MappingMemory Management UnitDemand PagingSlide 55Working SetPage Replacement PolicyReplacement PolicyBasic Replacement AlgorithmsSlide 60Slide 61Slide 62Slide 63Slide 64Slide 65Slide 66Slide 67Slide 68Slide 69Slide 70Cache memory Replacement Policy, Virtual MemoryProf. Sin-Min LeeDepartment of Computer ScienceQ2x4DecoderX Y Z JKQCLKX Y Z Q J K Q+0 0 0 0 0 1 00 0 1 0 0 1 00 1 0 0 0 1 00 1 1 0 0 1 01 0 0 0 1 1 11 0 1 0 1 1 11 1 0 0 0 1 01 1 1 0 0 1 0X Y Z Q J K Q+0 0 0 1 1 0 10 0 1 1 1 0 10 1 0 1 1 0 10 1 1 1 1 1 01 0 0 1 1 0 11 0 1 1 1 0 11 1 0 1 1 0 11 1 1 1 1 1 0J K Q+0 0 Q0 1 01 0 11 1 Q0 1000,001,010,011,110,111000,001,010,100,101,110100,101011,111There are three methods in block placement: Direct mapped : if each block has only one place it can appear in the cache, the cache is said to be direct mapped. The mapping is usually (Block address) MOD (Number of blocks in cache) Fully Associative : if a block can be placed anywhere in the cache, the cache is said to be fully associative. Set associative : if a block can be placed in a restricted set of places in the cache, the cache is said to be set associative . A set is a group of blocks in the cache. A block is first mapped onto a set, and then the block can be placed anywhere within that set. The set is usually chosen by bit selection; that is, (Block address) MOD (Number of sets in cache)• •A pictorial example for a cache with only 4 blocks and a memory with only 16 blocks.Direct mapped cache: A block from main memory can go in exactly one place in the cache. This is called direct mapped because there is direct mapping from any block address in memory to a single location in the cache. cacheMain memoryFully associative cache : A block from main memory can be placed in any location in the cache. This is called fully associative because a block in main memory may be associated with any entry in the cache. cacheMain memoryMemory/Cache Related Terms Set associative cache : The middle range of designs between direct mapped cache and fully associative cache is called set-associative cache. In a n-way set-associative cache a block from main memory can go into n (n at least 2) locations in the cache.2-way set-associative cacheMain memoryReplacing Data•Initially all valid bits are set to 0•As instructions and data are fetched from memory, the cache is filling and some data need to be replaced. •Which ones?•Direct mapping – obviousReplacement Policies for Associative Cache 1. FIFO - fills from top to bottom and goes back to top. (May store data in physical memory before replacing it)2. LRU – replaces the least recently used data. Requires a counter.3. RandomReplacement in Set-Associative Cache•Which if n ways within the location to replace?•FIFO•Random•LRUAccessed locations are D, E, AWriting Data•If the location is in the cache, the cached value and possibly the value in physical memory must be updated.•If the location is not in the cache, it maybe loaded into the cache or not (write-allocate and write-noallocate)•Two methodologies:1. Write-through•Physical memory always contains the correct value2. Write-back•The value is written to physical memory only it is removed from the cacheCache Performance•Cache hits and cache misses.•Hit ratio is the percentage of memory accesses that are served from the cache•Average memory access timeTM = h TC + (1- h)TPTc = 10 nsTp = 60 nsAssociative Cache•Access order A0 B0 C2 A0 D1 B0 E4 F5 A0 C2 D1 V0 G3 C2 H7 I6 A0 B0Tc = 10 nsTp = 60 nsFIFOh = 0.389TM = 40.56 nsDirect-Mapped Cache•Access order A0 B0 C2 A0 D1 B0 E4 F5 A0 C2 D1 V0 G3 C2 H7 I6 A0 B0Tc = 10 nsTp = 60 nsh = 0.167TM = 50.67 ns2-Way Set Associative Cache•Access order A0 B0 C2 A0 D1 B0 E4 F5 A0 C2 D1 V0 G3 C2 H7 I6 A0 B0Tc = 10 nsTp = 60 nsLRUh = 0.31389TM = 40.56 nsAssociative Cache(FIFO Replacement Policy)Data A B C A D B E F A C D B G C H I A BCACHEA A A A A A A A A A A A A A A I I I B B B B B B B B B B B B B B B A A C C C C C C C C C C C C C C C B D D D D D D D D D D D D D D E E E E E E E E E E E E F F F F F F F F F F F G G G G G G H H H HHit? * * * * * * * Hit ratio = 7/18Hit ratio = 7/18A0 B0 C2 A0 D1 B0 E4 F5 A0 C2 D1 B0 G3 C2 H7 I6 A0 B0Two-way set associative cache(LRU Replacement Policy)Hit ratio = 7/18Hit ratio = 7/18A0 B0 C2 A0 D1 B0 E4 F5 A0 C2 D1 B0 G3 C2 H7 I6 A0 B0Data A B C A D B E F A C D B G C H I A BCACHE0 A-0 A-1 A-1 A-0 A-0 A-1 E-0 E-0 E-1 E-1 E-1 B-0 B-0 B-0 B-0 B-0 B-1 B-00 B-0 B-0 B-1 B-1 B-0 B-1 B-1 A-0 A-0 A-0 A-1 A-1 A-1 A-1 A-1 A-0 A-11 D-0 D-0 D-0 D-1 D-1 D-1 D-0 D-0 D-0 D-0 D-0 D-0 D-0 D-01 F-0 F-0 F-0 F-1 F-1 F-1 F-1 F-1 F-1 F-1 F-12 C-0 C-0 C-0 C-0 C-0 C-0 C-0 C-0 C-0 C-0 C-0 C-0 C-0 C-1 C-1 C-12 I-0 I-0 I-03 G-0 G-0 G-1 G-1 G-1 G-13 H-0 H-0 H-0 H-0Hit? * * * * * * *Associative Cache with 2 byte line size (FIFO Replacement Policy)Hit ratio = 11/18Hit ratio = 11/18A0 B0 C2 A0 D1 B0 E4 F5 A0 C2 D1 B0 G3 C2 H7 I6 A0 B0A and J; B and D; C and G; E and F; and I and HA and J; B and D; C and G; E and F; and I and HData A B C A D B E F A C D B G C H I A BCACHE A A A A A A A A A A A A A A I I I I J J J J …
View Full Document
Unlocking...