Slide 1Last 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 PagingSlide 20Linear 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 togetherAcknowledgementsFebruary 18, 2010 CS152, Spring 2010CS 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/~cs152February 18, 2010 CS152, Spring 20102Last time in Lecture 8•Multi-level cache hierarchies 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•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 prefetching•Software memory hierarchy optimizations–Loop interchange, loop fusion, cache tilingFebruary 18, 2010 CS152, Spring 20103Memory 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 systemFebruary 18, 2010 CS152, Spring 20104Absolute 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 imageFebruary 18, 2010 CS152, Spring 20105Dynamic 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 MemoryFebruary 18, 2010 CS152, Spring 20106Simple Base and Bound TranslationLoad XProgramAddressSpaceBoundRegisterBoundsViolation?Physical MemorycurrentsegmentBaseRegister+PhysicalAddressEffectiveAddressBase and bounds registers are visible/accessible only when processor is running in the supervisor modeBase Physical AddressSegment LengthFebruary 18, 2010 CS152, Spring 20107Separate Areas for Program and DataWhat is an advantage of this separation?(Scheme used on all Cray vector supercomputers prior to X1, 2002)Load XProgramAddressSpacePhysical MemorydatasegmentData BoundRegisterEffective AddrRegisterData BaseRegister+BoundsViolation?Program BoundRegisterProgramCounterProgram BaseRegister+BoundsViolation?programsegmentFebruary 18, 2010 CS152, Spring 20108Memory 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 3freeFebruary 18, 2010 CS152, Spring 20109•Processor-generated address can be split into:Paged Memory SystemsPage tables make it possible to store the pages of a program non-contiguously.01230123Address Spaceof User-1Page Table of User-11023page number offset•A page table contains the physical address of the base of each page:Physical MemoryFebruary 18, 2010 CS152, Spring 201010Private 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 Physical MemoryfreeOSpagesFebruary 18, 2010 CS152, Spring 201011Where 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!February 18, 2010 CS152, Spring 201012Page Tables in Physical MemoryVA1User 1 Virtual Address SpaceUser 2 Virtual Address SpacePT User 1 PT User 2 VA1Physical MemoryFebruary 18, 2010 CS152, Spring 201013CS152 AdministriviaFebruary 18, 2010 CS152, Spring 201014A 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!February 18, 2010 CS152, Spring 201015Manual 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–Difficult, error-prone!•Method 2: automatic initiation of I/O transfers by software address translation–Brooker’s interpretive coding, 1960–Inefficient!Not just an ancient black art, e.g., IBM Cell microprocessor using in Playstation-3 has explicitly managed local store!February 18, 2010 CS152, Spring 201016Demand Paging in Atlas (1962)Secondary(Drum)32x6 pagesPrimary32 Pages512 words/pageCentral
View Full Document
Unlocking...