CS 152 Computer Architecture and Engineering Lecture 9 Address Translation Krste Asanovic Electrical Engineering and Computer Sciences University of California at Berkeley http www eecs berkeley edu krste http inst eecs berkeley edu cs152 Last 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 prefetching 2 24 2009 CS152 Spring 09 2 Memory 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 system 2 24 2009 CS152 Spring 09 3 Absolute Addresses EDSAC early 50 s 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 subroutines How could location independence be achieved Linker and or loader modify addresses of subroutines and callers when building a program memory image 2 24 2009 CS152 Spring 09 4 Dynamic Address Translation Motivation Higher throughput if CPU and I O of 2 or more programs were overlapped How multiprogramming Physical Memory In the early machines I O operations were slow and each word transferred involved the CPU prog1 Location independent programs Programming and storage management ease need for a base register Protection prog2 Independent programs should not affect each other inadvertently need for a bound register 2 24 2009 CS152 Spring 09 5 Simple Base and Bound Translation Segment Length Load X Effective Address Bounds Violation Physical Address current segment Base Register Program Address Space Base Physical Address Base and bounds registers are visible accessible only when processor is running in the supervisor mode 2 24 2009 CS152 Spring 09 6 Main Memory Bound Register Data Bound Register Load X Program Address Space Bounds Violation Effective Addr Register Data Base Register Program Bound Register Bounds Violation program segment Program Counter Program Base Register data segment Main Memory Separate Areas for Program and Data What is an advantage of this separation Scheme used on all Cray vector supercomputers prior to X1 2002 2 24 2009 CS152 Spring 09 7 Memory Fragmentation OS Space Users 4 5 arrive OS Space Users 2 5 leave free OS Space user 1 16K user 1 16K user 2 24K user 2 user 4 24K 16K 8K user 4 16K 8K 32K user 3 32K user 3 32K 24K user 5 24K 24K user 3 user 1 16K 24K 24K As users come and go the storage is fragmented Therefore at some stage programs have to be moved around to compact the storage 2 24 2009 CS152 Spring 09 8 Paged Memory Systems Processor generated address can be interpreted as a pair page number offset page number offset A page table contains the physical address of the base of each page 0 1 2 3 Address Space of User 1 1 0 0 1 2 3 3 Page Table of User 1 2 Page tables make it possible to store the pages of a program non contiguously 2 24 2009 CS152 Spring 09 9 User 1 VA1 Page Table User 2 Physical Memory Private Address Space per User OS pages VA1 Page Table User 3 VA1 Page Table free Each user has a page table Page table contains an entry for each user page 2 24 2009 CS152 Spring 09 10 Where 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 09 11 Page Tables in Physical Memory PT User 1 VA1 PT User 2 User 1 VA1 User 2 2 24 2009 CS152 Spring 09 12 CS152 Administrivia Quiz 2 Tuesday March 3 Covers Lectures 6 8 PS2 and Lab 2 2 24 2009 CS152 Spring 09 13 A 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 store tricky programming 2 24 2009 CS152 Spring 09 14 Manual Overlays 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 1960 Method1 Difficult error prone Method2 Inefficient 40k bits main 640k bits drum Central Store Ferranti Mercury 1956 Not just an ancient black art e g IBM Cell microprocessor explicitly managed local store has same issues 2 24 2009 CS152 Spring 09 15 Demand Paging in Atlas 1962 A page from secondary storage is brought into the primary storage whenever it is implicitly demanded by the processor Tom Kilburn Primary 32 Pages 512 words page Primary memory as a cache for secondary memory User sees 32 x 6 x 512 words of storage 2 24 2009 Central Memory CS152 Spring 09 Secondary Drum 32x6 pages 16 Hardware Organization of Atlas Effective Address Initial Address Decode 48 bit words 512 word pages PARs 16 ROM pages 0 4 1 sec system code 2 subsidiary pages 1 4 sec system data not swapped not swapped 0 Main 32 pages 1 4 sec 1 Page Address 31 Register PAR effective PN status per page frame Drum 4 192 pages 8 Tape decks 88 sec word Compare the effective page address against all 32 PARs match normal access no match page fault save the state of the partially executed instruction 2 24 2009 CS152 Spring 09 17 Atlas Demand Paging Scheme On a page fault Input transfer into a free page is initiated The Page Address Register PAR is updated If no free page is left a page is selected to be
View Full Document
Unlocking...