Slide 1Last time in Lecture 9Slide 3Hierarchical Page TablePage-Based Virtual-Memory Machine (Hardware Page-Table Walk)Address Translation: putting it all togetherHandling VM-related exceptionsAddress Translation in CPU PipelineVirtual-Address CachesVirtually Addressed Cache (Virtual Index/Virtual Tag)Aliasing in Virtual-Address CachesCS152 AdministriviaQuiz ResultsQuiz ResultsQuiz ResultsQuiz ResultsConcurrent Access to TLB & Cache (Virtual Index/Physical Tag)Virtual-Index Physical-Tag Caches: Associative OrganizationSlide 19A solution via Second Level CacheAnti-Aliasing Using L2: MIPS R10000Anti-Aliasing using L2 for a Virtually Addressed L1Page Fault HandlerAtlas RevisitedHashed Page Table: Approximating Associative AddressingPower PC: Hashed Page TableVM features track historical uses:Virtual Memory Use Today - 1Virtual Memory Use Today - 2AcknowledgementsFebruary 23, 2011 CS152, Spring 2011CS 152 Computer Architecture and Engineering Lecture 9 - Virtual MemoryKrste AsanovicElectrical Engineering and Computer SciencesUniversity of California at Berkeleyhttp://www.eecs.berkeley.edu/~krstehttp://inst.eecs.berkeley.edu/~cs152February 23, 2011 CS152, Spring 20112Last time in Lecture 9•Protection and translation required for multiprogramming–Base and bounds was early simple scheme•Page-based translation and protection avoids need for memory compaction, easy allocation by OS–But need to indirect in large page table on every access•Address spaces accessed sparsely–Can use multi-level page table to hold translation/protection information, but implies multiple memory accesses per reference•Address space access with locality–Can use “translation lookaside buffer” (TLB) to cache address translations (sometimes known as address translation cache)–Still have to walk page tables on TLB miss, can be hardware or software talk•Virtual memory uses DRAM as a “cache” of disk memory, allows very cheap main memoryFebruary 23, 2011 CS152, Spring 20113Modern Virtual Memory Systems Illusion of a large, private, uniform storeProtection & Privacyseveral users, each with their private address space and one or more shared address spacespage table name spaceDemand PagingProvides the ability to run programs larger than the primary memoryHides differences in machine configurationsThe price is address translation on each memory referenceOSuseriPrimaryMemorySwappingStoreVA PAmappingTLBFebruary 23, 2011 CS152, Spring 20114Hierarchical Page TableLevel 1 Page TableLevel 2Page Tables Data Pagespage in primary memory page in secondary memoryRoot of the CurrentPage Tablep1offsetp2Virtual Address(ProcessorRegister)PTE of a nonexistent pagep1 p2 offset0111221223110-bitL1 index10-bit L2 indexPhysical MemoryFebruary 23, 2011 CS152, Spring 20115Page-Based Virtual-Memory Machine(Hardware Page-Table Walk)PCInst. TLBInst. CacheDDecodeE MData CacheW+Page Fault?Protection violation?Page Fault?Protection violation?•Assumes page tables held in untranslated physical memoryData TLBMain Memory (DRAM)Memory ControllerPhysical AddressPhysical AddressPhysical AddressPhysical AddressPage-Table Base RegisterVirtual AddressPhysical AddressVirtual AddressHardware Page Table WalkerMiss?Miss?February 23, 2011 CS152, Spring 20116Address Translation:putting it all togetherVirtual AddressTLBLookupPage TableWalkUpdate TLBPage Fault(OS loads page)ProtectionCheckPhysicalAddress(to cache)misshit the page is Ï memory Î memorydeniedpermittedProtectionFaulthardwarehardware or softwaresoftwareSEGFAULTRestart instructionFebruary 23, 2011 CS152, Spring 2011Handling VM-related exceptions•Handling a TLB miss needs a hardware or software mechanism to refill TLB •Handling a page fault (e.g., page is on disk) needs a restartable exception so software handler can resume after retrieving page–Precise exceptions are easy to restart–Can be imprecise but restartable, but this complicates OS software•Handling protection violation may abort process–But often handled the same as a page fault7PCInst TLBInst. CacheDDecodeE MData TLBData CacheW+TLB miss? Page Fault?Protection violation?TLB miss? Page Fault?Protection violation?February 23, 2011 CS152, Spring 20118Address Translation in CPU Pipeline•Need to cope with additional latency of TLB:– slow down the clock?– pipeline the TLB and cache access?– virtual address caches– parallel TLB/cache accessPCInst TLBInst. CacheDDecodeE MData TLBData CacheW+TLB miss? Page Fault?Protection violation?TLB miss? Page Fault?Protection violation?February 23, 2011 CS152, Spring 20119Virtual-Address Caches•one-step process in case of a hit (+)•cache needs to be flushed on a context switch unless address space identifiers (ASIDs) included in tags (-)•aliasing problems due to the sharing of pages (-)•maintaining cache coherence (-) (see later in course)CPUPhysicalCacheTLBPrimaryMemoryVAPAAlternative: place the cache before the TLBCPUVA(StrongARM)VirtualCachePATLBPrimaryMemoryFebruary 23, 2011 CS152, Spring 2011Virtually Addressed Cache(Virtual Index/Virtual Tag)10PCInst. TLBInst. CacheDDecodeE MData CacheW+Data TLBMain Memory (DRAM)Memory ControllerPhysical AddressInstruction dataPhysical AddressPhysical AddressPage-Table Base RegisterVirtual AddressVirtual AddressHardware Page Table WalkerMiss?Miss?Translate on missFebruary 23, 2011 CS152, Spring 201111Aliasing in Virtual-Address CachesVA1VA2Page TableData PagesPAVA1VA21st Copy of Data at PA2nd Copy of Data at PATag DataTwo virtual pages share one physical pageVirtual cache can have two copies of same physical data. Writes to one copy not visible to reads of other!General Solution: Prevent aliases coexisting in cacheSoftware (i.e., OS) solution for direct-mapped cacheVAs of shared pages must agree in cache index bits; this ensures all VAs accessing same PA will conflict in direct-mapped cache (early SPARCs)February 23, 2011 CS152, Spring 201112CS152 AdministriviaFebruary 23, 2011 CS152, Spring 2011Quiz Results13February 23, 2011 CS152, Spring 2011Quiz Results14February 23, 2011 CS152, Spring 2011Quiz Results15February 23, 2011 CS152, Spring 2011Quiz Results16February 23, 2011 CS152, Spring 201117Concurrent Access to TLB & Cache(Virtual Index/Physical Tag)Index L is available without consulting the TLBcache and TLB accesses can begin simultaneously!Tag comparison is made after both accesses are completedCases: L + b = k, L + b < k, L + b > k VPN L bTLBDirect-map Cache 2L
View Full Document
Unlocking...