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 February 18 2010 CS152 Spring 2010 Last 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 tiling February 18 2010 CS152 Spring 2010 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 February 18 2010 CS152 Spring 2010 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 February 18 2010 CS152 Spring 2010 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 February 18 2010 CS152 Spring 2010 5 Simple Base and Bound Translation Bound Register 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 February 18 2010 CS152 Spring 2010 6 Physical Memory Segment Length Data Bound Register Load X Program Address Space Bounds Violation Effective Addr Register Data Base Register Program Bound Register data segment Bounds Violation Physical Memory Separate Areas for Program and Data program segment Program Counter Program Base Register What is an advantage of this separation Scheme used on all Cray vector supercomputers prior to X1 2002 February 18 2010 CS152 Spring 2010 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 24K user 4 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 February 18 2010 CS152 Spring 2010 8 Paged Memory Systems Processor generated address can be split into 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 Physical Memory 3 Page Table of User 1 2 Page tables make it possible to store the pages of a program non contiguously February 18 2010 CS152 Spring 2010 9 Private Address Space per User User 1 OS pages VA1 User 2 Physical Memory Page Table VA1 Page Table User 3 VA1 Page Table free Each user has a page table Page table contains an entry for each user page February 18 2010 CS152 Spring 2010 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 February 18 2010 CS152 Spring 2010 11 Page Tables in Physical Memory VA1 Physical Memory PT User 1 PT User 2 User 1 Virtual Address Space VA1 User 2 Virtual Address Space February 18 2010 CS152 Spring 2010 12 CS152 Administrivia February 18 2010 CS152 Spring 2010 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 February 18 2010 CS152 Spring 2010 14 Manual Overlays Assume an instruction can address all the storage on the drum 40k bits main Method 1 programmer keeps track of addresses in the main memory and initiates an I O transfer when required 640k bits drum Difficult error prone Central Store Method 2 automatic initiation of I O transfers by software address translation Ferranti Mercury 1956 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 2010 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 February 18 2010 Central Memory CS152 Spring 2010 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 February 18 2010 CS152 Spring 2010 17 Atlas Demand Paging Scheme On a
View Full Document
Unlocking...