A NEW PAGE TABLE FOR 64-BIT ADDRESS SPACESTHE PROBLEMCURRENT ORGANIZATIONS (I)CURRENT ORGANIZATIONS (II)CURRENT ORGANIZATIONS (III)What is wrong with them?CLUSTERED PAGE TABLESHow they workAdvantages of clustered PTsAre we really saving space?The answerHANDLING TLB MISSESSubblockingHandling complete subblockingHandling partial subblockingNoteProblemHintSolution (I)Solution (II)SuperpagesHandling superpages (I)Handling superpages (II)Handling superpages (III)CONCLUSIONSA NEW PAGE TABLE FOR 64-BIT ADDRESS SPACESM. Talluri, M. D. Hill, Y. A. KalidiUniversity of Wisconsin, MadisonSun Microsystems LaboratoriesTHE PROBLEM•Programs’ memory usage doubles every one or two years.•Most processor architectures are now moving from 32-bit to 64-bit virtual address spaces•How would current page table organizations scale up?–Will support very large butvery sparsely populated address spacesCURRENT ORGANIZATIONS (I)• Three main approaches:–Linear page tables: •PTs are too large to be stored in main memory•Store PT in virtual memory (VMS solution)•Very large page tables need more than 2 levels (3 levels on MIPS R3000)CURRENT ORGANIZATIONS (II)–Forward-mapped page tables: Virtual AddressPhysical AddressMASTER INDEXOffsetOffset1ary 2arySUBINDEX < Page Number >Frame NoFrameAddr. (unchanged)CURRENT ORGANIZATIONS (III)–Hashed (inverted) page tables:VPNhashVPNPPNVPN = virtual page numberPPN = “physical page” number = page frame numberWhat is wrong with them?•None of these solutions scales up to 64-bit addresses:–Linear and forward-mapped page tables require too many levels–Hashed page tables require too much space: •Must store the VPN and the next pointer in addition to PPNCLUSTERED PAGE TABLES•Variant of hashed page tables•Each entry stores mapping information for a cluster of consecutive page table entries•Number of pages in a cluster is called the clustering factor.How they workVPNhashVPNPPN0PPN1Clustering factor = 2Each entry maps 2 contiguous VPNsAdvantages of clustered PTs•Require much less space overhead: only one VPN and one next pointer per cluster•Take advantage of the fact that the address space of many programs consists of small clusters of pages •Interact much better with the TLB miss handling firmware or software.Are we really saving space?•Assume a clustering factor of 2–Each entry maps 2 pages and occupies 4×8 bytesVPNPPN0PPN1The answer–Without clustering, each entry maps one page and occupies 3×8 bytes•Clustering will save space if more than 67% of the page mappings are usefulVPNPPNHANDLING TLB MISSES•Page table organization should allow efficient handling of TLB misses by –firmware (classical solution)–software (MIPS, Alpha, UltraSPARC)•Should handle two recent TLB advances–subblocking–superpagesSubblocking•Associates multiple physical page numbers (PPN’s) with each TLB tag: –Complete subblocking allows the page frames containing the subblock pages to be anywhere in main memory (MIPS 4X00x)–Partial subblocking requires these page frames to be placed in a single, aligned block of main memory; there is one PPN per TLB tag.Handling complete subblocking •Have cluster size of PT equal to subblocking factorVPNhashVPNPPN0PPN1Handling partial subblocking •Since all page frames are contiguous, have a single PPN per cluster•Bitmap (bm) indicateswhich pages are in memoryVPNhashVPN0PPN0bmNote•Each page table entry maps two virtual pages into two physical pages–Virtual page VPN0 is mapped into physical page PPN0–Virtual page VPN0 + 1 is mapped into physical page PPN0 + 1•These mappings are valid if the virtual page is actually in main memoryProblem•A virtual memory system has 64-bit addresses and a clustered page table with a clustering factor of 4. If each address occupies 8 bytes, what would be the length of a page table entry for:(a) partial subblocking ?(b) complete subblocking ?Hint•No additional space is required for bitmap•If page size is equal to 2p,page size will occupy 64 -p bits•In practice, page size > 1,024 and p > 10•Can use these p bits to store the bitmapSolution (I)•With complete subblocking, each PTE has:–one virtual page number–four physical page numbers–one pointer to next entry•6 entries × 8 bytes = 48 bytesSolution (II)•With partial subblocking, each PTE has:–one virtual page number–one physical page number–four bits of bitmap–one pointer to next entry•3 entries × 8 bytes = 24 bytesSuperpages•Sets of pages that are aligned both in virtual and in physical memory•Brought in memory and out of memory as a single entity•Size is a power-of-two multiple of the page size (MIPS, UltraSPARC, Alpha, PowerPC)• Large superpages (256KB and above) are especially useful for kernel dataHandling superpages (I)•We can:–Have one PTE for each page in the superpage Simplest solution but does not save space–Have one page table per superpage size (including isolated pages)Each page miss will now have to search several PTsHandling superpages (II)–Store superpage mappings at the appropriate level of a PTOnly works with multi-level PTs having a tree structure–Pick hash function such that all pages that are in the same superpage are in the same bucketResults in larger buckets and longer searchesHandling superpages (III)•Best solution seems to be –Use same data structures for small superpages and partial subblocks–Otherwise have one entry for each cluster in the superpage–Support very large superpages on an ad hoc basisThere will be very few of themCONCLUSIONS•64-bit addresses will force a rethinking of page table organization•New organizations must support efficient handling of TLB misses•Supporting partial subblocking is most important issue because partial subblocking requires simpler OS support than superpages and reduces more effectively page table