CS 152 Computer Architecture and Engineering Lecture 9 - Address TranslationLast time in Lecture 8Memory ManagementAbsolute AddressesDynamic Address TranslationSimple Base and Bound TranslationSeparate Areas for Program and DataMemory FragmentationPaged Memory SystemsPrivate Address Space per UserWhere Should Page Tables Reside?Page Tables in Physical MemoryCS152 AdministriviaA Problem in the Early SixtiesManual OverlaysDemand Paging in Atlas (1962)Hardware Organization of AtlasAtlas Demand Paging SchemeCaching vs. Demand PagingModern Virtual Memory Systems Illusion of a large, private, uniform storeLinear Page TableSize of Linear Page TableHierarchical Page TableAddress Translation & ProtectionTranslation Lookaside BuffersTLB DesignsHandling a TLB MissHierarchical Page Table Walk: SPARC v8Address Translation: putting it all togetherAcknowledgementsCS 152 Computer Architecture and Engineering Lecture 9 - Address TranslationKrste AsanovicElectrical Engineering and Computer SciencesUniversity of California at Berkeleyhttp://www.eecs.berkeley.edu/~krstehttp://inst.eecs.berkeley.edu/~cs1522/24/2009 CS152-Spring’092Last time in Lecture 8•Multi-level cache hierarchies to reduce miss penalty–3 levels common in modern systems–Inclusive versus exclusive caching policy–Can change design tradeoffs of L1 cache if known to have L2•Reducing cost of associativity–Way-prediction (L1 instruction cache, and L2 data caches)–Victim caches•Non-blocking caches–Allow hits and maybe misses while misses in flight•Prefetching: retrieve data from memory before CPU request–Prefetching can waste bandwidth and cause cache pollution–Software vs hardware prefetching2/24/2009 CS152-Spring’093Memory Management•From early absolute addressing schemes, to modern virtual memory systems with support for virtual machine monitors•Can separate into orthogonal functions:–Translation (mapping of virtual address to physical address)–Protection (permission to access word in memory)–Virtual memory (transparent extension of memory space using slower disk storage)•But most modern systems provide support for all the above functions with a single page-based system2/24/2009 CS152-Spring’094Absolute Addresses•Only one program ran at a time, with unrestricted access to entire machine (RAM + I/O devices)•Addresses in a program depended upon where the program was to be loaded in memory•But it was more convenient for programmers to write location-independent subroutinesEDSAC, early 50’sHow could location independence be achieved?Linker and/or loader modify addresses of subroutines and callers when building a program memory image2/24/2009 CS152-Spring’095Dynamic Address TranslationMotivationIn the early machines, I/O operations were slow and each word transferred involved the CPU Higher throughput if CPU and I/O of 2 or more programs were overlapped.How?multiprogrammingLocation-independent programsProgramming and storage management ease need for a base registerProtectionIndependent programs should not affecteach other inadvertently need for a bound registerprog1prog2Physical Memory2/24/2009 CS152-Spring’096Simple Base and Bound TranslationLoad XProgramAddressSpaceBoundRegisterBoundsViolation?Main MemorycurrentsegmentBaseRegister+PhysicalAddressEffectiveAddressBase and bounds registers are visible/accessible only when processor is running in the supervisor modeBase Physical AddressSegment Length2/24/2009 CS152-Spring’097Separate Areas for Program and DataWhat is an advantage of this separation?(Scheme used on all Cray vector supercomputers prior to X1, 2002)Load XProgramAddressSpaceMain MemorydatasegmentData BoundRegisterEffective AddrRegisterData BaseRegister+BoundsViolation?Program BoundRegisterProgramCounterProgram BaseRegister+BoundsViolation?programsegment2/24/2009 CS152-Spring’098Memory Fragmentation As users come and go, the storage is “fragmented”. Therefore, at some stage programs have to be moved around to compact the storage. OSSpace16K24K24K32K24Kuser 1user 2user 3OSSpace16K24K16K32K24Kuser 1user 2user 3user 5user 48KUsers 4 & 5 arriveUsers 2 & 5leaveOSSpace16K24K16K32K24Kuser 1user 48Kuser 3free2/24/2009 CS152-Spring’099•Processor generated address can be interpreted as a pair <page number, offset>•A page table contains the physical address of the base of each pagePaged Memory SystemsPage tables make it possible to store the pages of a program non-contiguously.01230123Address Spaceof User-1Page Table of User-11023page number offset2/24/2009 CS152-Spring’0910Private Address Space per User• Each user has a page table • Page table contains an entry for each user pageVA1User 1Page Table VA1User 2Page Table VA1User 3Page Table PhysicalMemoryfreeOSpages2/24/2009 CS152-Spring’0911Where Should Page Tables Reside?•Space required by the page tables (PT) is proportional to the address space, number of users, ... Space requirement is large Too expensive to keep in registers•Idea: Keep PTs in the main memory–needs one reference to retrieve the page base address and another to access the data word doubles the number of memory references!2/24/2009 CS152-Spring’0912Page Tables in Physical MemoryVA1User 1PT User 1 PT User 2 VA1User 22/24/2009 CS152-Spring’0913CS152 Administrivia•Quiz 2: Tuesday March 3. Covers Lectures 6-8, PS2, and Lab 22/24/2009 CS152-Spring’0914A Problem in the Early Sixties•There were many applications whose data could not fit in the main memory, e.g., payroll–Paged memory system reduced fragmentation but still required the whole program to be resident in the main memory•Programmers moved the data back and forth from the secondary store by overlaying it repeatedly on the primary storetricky programming!2/24/2009 CS152-Spring’0915Manual Overlays Ferranti Mercury195640k bitsmain640k bitsdrumCentral Store•Assume an instruction can address all the storage on the drum•Method 1: programmer keeps track of addresses in the main memory and initiates an I/O transfer when required•Method 2: automatic initiation of I/O transfers by software address translation Brooker’s interpretive coding, 1960Method1: Difficult, error proneMethod2: InefficientNot just an ancient black art, e.g., IBM Cell microprocessor explicitly managed local store has same issues2/24/2009 CS152-Spring’0916Demand Paging in Atlas (1962)Secondary(Drum)32x6 pagesPrimary32 Pages512 words/pageCentral
View Full Document
Unlocking...