CS 162 Ch 7: Virtual Memory LECTURE 13Improving Cache Miss Latency-Reducing DRAM LatencyMain Memory Organizations Fig. 7.13Memory Access Time ExampleVirtual MemoryVirtual Memory has own terminologyMapping Virtual Memory to Physical MemoryHandling Page FaultsComparing the 2 levels of hierarchyHow to Perform Address Translation?Mapping Virtual to Physical AddressAddress TranslationAddress Translation: Page TableSlide 14Optimizing for SpaceHow Translate Fast?Typical TLB FormatTranslation Look-Aside BuffersPowerPoint PresentationReal Stuff: Pentium Pro Memory Hierarchy11999 ©UCBCS 162Ch 7: Virtual Memory LECTURE 13Instructor: L.N. Bhuyanwww.cs.ucr.edu/~bhuyan21999 ©UCBImproving Cache Miss Latency-Reducing DRAM Latency°Same as improving DRAM latency°What is random access memory (RAM)? What are static RAM (SRAM) and dynamic RAM (DRAM)?°What is DRAM Cell organization? How are the cells arranged internally? Memory addressing? Refreshing of DRAMs? Difference between DRAM and SRAM?°Access time of DRAM = Row access time + column access time + refreshing°What are page-mode and nibble-mode DRAMs?°Synchronous SRAM or DRAM – Ability to transfer a burst of data given a starting address and a burst length – suitable for transferring a block of data from main memory to cache.31999 ©UCBMain Memory Organizations Fig. 7.13CPUCacheBusMemoryCPUBusMemoryMultiplexorCacheCPUCacheBusMemorybank 1Memorybank 2Memorybank 3Memorybank 0one-word widememory organizationwide memory organizationinterleaved memory organizationDRAM access time >> bus transfer time41999 ©UCBMemory Access Time Example°Assume that it takes 1 cycle to send the address, 15 cycles for each DRAM access and 1 cycle to send a word of data.°Assuming a cache block of 4 words and one-word wide DRAM (fig. 7.13a), miss penalty = 1 + 4x15 + 4x1 = 65 cycles°With main memory and bus width of 2 words (fig. 7.13b), miss penalty = 1 + 2x15 + 2x1 = 33 cycles. For 4-word wide memory, miss penalty is 17 cycles. Expensive due to wide bus and control circuits.°With interleaved memory of 4 memory banks and same bus width (fig. 7.13c), the miss penalty = 1 + 1x15 + 4x1 = 20 cycles. The memory controller must supply consecutive addresses to different memory banks. Interleaving is universally adapted in high-performance computers.51999 ©UCBVirtual Memory°Idea 1: Many Programs sharing DRAM Memory so that context switches can occur°Idea 2: Allow program to be written without memory constraints – program can exceed the size of the main memory°Idea 3: Relocation: Parts of the program can be placed at different locations in the memory instead of a big chunk.°Virtual Memory:(1) DRAM Memory holds many programs running at same time (processes)(2) use DRAM Memory as a kind of “cache” for disk61999 ©UCBVirtual Memory has own terminology°Each process has its own private “virtual address space” (e.g., 232 Bytes); CPU actually generates “virtual addresses”°Each computer has a “physical address space” (e.g., 128 MegaBytes DRAM); also called “real memory”°Address translation: mapping virtual addresses to physical addresses•Allows multiple programs to use (different chunks of physical) memory at same time•Also allows some chunks of virtual memory to be represented on disk, not in main memory (to exploit memory hierarchy)71999 ©UCBMapping Virtual Memory to Physical Memory 0Physical MemoryVirtual MemoryHeap64 MB°Divide Memory into equal sized“chunks” (say, 4KB each)0°Any chunk of Virtual Memory assigned to any chunk of Physical Memory (“page”)StackHeapStaticCodeSingleProcess81999 ©UCBHandling Page Faults°A page fault is like a cache miss•Must find page in lower level of hierarchy°If valid bit is zero, the Physical Page Number points to a page on disk°When OS starts new process, it creates space on disk for all the pages of the process, sets all valid bits in page table to zero, and all Physical Page Numbers to point to disk •called Demand Paging - pages of the process are loaded from disk only as needed91999 ©UCBComparing the 2 levels of hierarchy°Cache Virtual Memory°Block or Line Page°Miss Page Fault°Block Size: 32-64B Page Size: 4K-16KB°Placement: Fully AssociativeDirect Mapped, N-way Set Associative°Replacement: Least Recently UsedLRU or Random (LRU) approximation°Write Thru or Back Write Back°How Managed: Hardware + SoftwareHardware (Operating System)101999 ©UCBHow to Perform Address Translation? °VM divides memory into equal sized pages°Address translation relocates entire pages•offsets within the pages do not change•if make page size a power of two, the virtual address separates into two fields:•like cache index, offset fieldsVirtual Page NumberPage Offsetvirtual address111999 ©UCBMapping Virtual to Physical AddressVirtual Page Number Page OffsetPage OffsetPhysical Page NumberTranslation31 30 29 28 27 .………………….12 11 1029 28 27 .………………….12 11 10 9 8 ……..……. 3 2 1 0Virtual AddressPhysical Address 9 8 ……..……. 3 2 1 01KB page size121999 ©UCBAddress Translation°Want fully associative page placement°How to locate the physical page?°Search impractical (too many pages)°A page table is a data structure which contains the mapping of virtual pages to physical pages•There are several different ways, all up to the operating system, to keep this data around°Each process running in the system has its own page table131999 ©UCBAddress Translation: Page TableVirtual Address (VA):virtual page nbroffsetPage TableRegisterPage Table is located in physical memoryindexintopagetable+PhysicalMemoryAddress (PA)Access Rights: None, Read Only, Read/Write, ExecutablePage TableVal-idAccessRightsPhysicalPageNumberV A.R. P. P. N.0 A.R.V A.R. P. P. N.......disk141999 ©UCBHandling Page Faults°A page fault is like a cache miss•Must find page in lower level of hierarchy°If valid bit is zero, the Physical Page Number points to a page on disk°When OS starts new process, it creates space on disk for all the pages of the process, sets all valid bits in page table to zero, and all Physical Page Numbers to point to disk •called Demand Paging - pages of the process are loaded from disk only as needed151999 ©UCBOptimizing for Space°Page Table too big!•4GB Virtual Address Space ÷ 4 KB page  220 (~ 1 million) Page Table Entries  4 MB just for Page Table of single process!°Variety of solutions to tradeoff Page Table size for slower performance when miss