Virtual MemoryGiven the following implementation using a 38 decoder with negated outputs, what is the function K(A,B,C)?Slide 3Where can a block be placed in Cache? (2)How is a Block Found in the Cache?Which Block should be Replaced on a Cache Miss?What Happens on a Write?Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Memory/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 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Before VM…Solution to Memory ConstraintsImplementations of VMMemory IssuesPagingAddress MappingSlide 50Slide 51Paging ImplementationSlide 53Memory MappingMemory MappingMemory Management UnitDemand PagingSlide 58Working SetPage Replacement PolicyReplacement PolicySlide 62Basic Replacement AlgorithmsSlide 64Slide 65Slide 66Slide 67Page Replacement PoliciesVirtual MemoryProf. Sin-Min LeeDepartment of Computer ScienceGiven the following implementation using a 38 decoder with negated outputs, what is the function K(A,B,C)?a. K(A,B,C) = A.B' + A'.B.Cb. K(A,B,C) = A.B + A'.B' + A'.C'c. K(A,B,C) = (A + B' + C').(A' + B + C).(A' + B + C')d. K(A,B,C) = 1e. K(A,B,C) = 0Q2x4DecoderX 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,111Where can a block be placed in Cache? (2)•Direct mapped Cache–Each block has only one place where it can appear in the cache–(Block Address) MOD (Number of blocks in cache)•Fully associative Cache–A block can be placed anywhere in the cache•Set associative Cache–A block can be placed in a restricted set of places into the cache–A set is a group of blocks into the cache–(Block Address) MOD (Number of sets in the cache)•If there are n blocks in the cache, the placement is said to be n-way set associativeHow is a Block Found in the Cache?•Caches have an address tag on each block frame that gives the block address. The tag is checked against the address coming from CPU–All tags are searched in parallel since speed is critical–Valid bit is appended to every tag to say whether this entry contains valid addresses or not•Address fields:–Block address•Tag – compared against for a hit•Index – selects the set–Block offset – selects the desired data from the block•Set associative cache –Large index means large sets with few blocks per set–With smaller index, the associativity increases•Full associative cache – index field is not existingWhich Block should be Replaced on a Cache Miss?•When a miss occurs, the cache controller must select a block to be replaced with the desired data–Benefit of direct mapping is that the hardware decision is much simplified•Two primary strategies for full and set associative caches–Random – candidate blocks are randomly selected•Some systems generate pseudo random block numbers, to get reproducible behavior useful for debugging–LRU (Last Recently Used) – to reduce the chance that information that has been recently used will be needed again, the block replaced is the least-recently used one. •Accesses to blocks are recorded to be able to implement LRUWhat Happens on a Write?•Two basic options when writing to the cache:–Writhe through – the information is written to both, the block in the cache an the block in the lower-level memory–Write back – the information is written only to the lock in the cache•The modified block of cache is written back into the lower-level memory only when it is replaced•To reduce the frequency of writing back blocks on replacement, an implementation feature called dirty bit is commonly used. –This bit indicates whether a block is dirty (has been modified since loaded) or clean (not modified). If clean, no write back is involvedThe connection between the CPU and cache is very fast; the connection between the CPU and memory is slowerThere 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
View Full Document
Unlocking...