A New Page Table for 64-bit Address Spaces“*+illaril D. Hill*, Yousef A. Khalidi+~adhusudhan Tallurl ,*Computer Sciences DepartmentUniversity of WisconsinMadison, WI 53706, USA{talluri, mrrrkhill}@cs.wise.eduAbstractMost computer architectures are moving to 64-bitvirtual address spaces. We first discuss how thischange impacts conventional linear, forward-mapped, and hashed page tables. We then introducea new page table data structure—clusteredpage fa-ble—that can be viewed as a hashed page table aug-mented with subblocking. Specifically, it associatesmapping information for several pages (e.g., sixteen)with a single virtual tag and next pointer. Simulationresults with several workloads show that clusteredpage tables use less memory than alternatives with-out adversely affecting page table access time.Since physical address space use is also increas-ing, computer architects are using new techniques—such assuperpages, complete-subblocking, and partial-subblocking—to increase the memory mapped by atranslation lookaside buffer (TLB). Since these tech-niques are completely ineffective without page tablesupport, we next look at extending conventional andclustered page tables to support them. Simulation re-sults show clustered page tables support medium-sized superpage and subblock TLBs especially well.1 IntroductionOne long-standing computer trend is that pro-grams’ memory usage doubles each year or two[Henn90]. Theoretically therefore, systems that sup-port paged virtual memory [Denn70] should in-crease their virtual and physical address sizeslinearly each year. In practice, however, compatibili-‘llus work was pnmanly supported by a NationalSc~enceFounda-tion Presidential Young Investigator Award (MIPS-8957278) and aSun Microsystems External ResearchGrant. The experiments wereperformed on equipment donated by Sun Microsystems.Permission to make digital/hard copy of part or all of this work for personalor classroom use is ranted without fee provided that copies are not made1!or distributed for pro [t or commercial advantage, the copyright notice, thetitle of the publication and its date appear, and notice is given thatcopying is by permission of ACM, Inc. To copy otherwise, to republish, topost on servers, or to redistribute to lists, requires prior specific permissionand/or a fee.SIGOPS ’95 12/95 CO, USA01995 ACM 0-89791-71 5-4/95/0012...$3.50‘Sun Microsystems Laboratories2550 Garcia Ave., MTV-29Mountain View, CA 94043, USA{madhu,yak}@eng. sun.comty issues force address spaces to grow discontinu-ously, especially for virtual addresses. The industryis currently undergoing such a discontinuity withmost processor architectures moving from 32- to 64-bit virtual addresses (while more-modestly increas-ing the size of physical addresses). All things beingequal, increasing address space size adversely affectspage table and translation lookaside buffer (TLB)cost or performance. This paper explores the effect of64-bit addresses on page tables. Anaddress is a virtu-al address unless we explicitly identify it as a physi-cal address.Apage fable stores translation, protection, at-tribute and status information for (virtual) addresses[Huck93, Chan88, Levy82, Silh93, Lee89]. The infor-mation for each page is called apage iable entry(PTE). The TLB miss handler accesses the page tableon a TLB miss to load the appropriate PTE into theTLB. An ideal page table would facilitate a fast TLBmiss handler, use little virtual or physical memory,and flexibly support operating systems in page tablemodifications. Section 2 reviews conventional pagetables—linear, forward-mapped, and hashed—anddiscusses the challenges of extending conventionalpage tables to support 64-bit address spaces. It ex-plains why both linear and hashed page tables areviable for 64-bit addresses, and why forward-mapped page tables are probably impractical as eachTLB miss requires about seven memory references.Many processors now support TLB miss handling insoftware, e.g., MIPS [Kane92], Alpha [Site93], UltraS-PARC [Yung95]. This makes page table design an op-erating system issue and in this paper we explorealternate operating system data structures for storingpage tables and servicing TLB misses.Section 3 introduces the central contribution ofthis paper: theclustered page fable. It is a new page ta-ble data structure that can be viewed as a hashedpage table augmented withsubblocking, a simple buteffective technique used in hardware caches andTLBs [Lipt68, Good83, Hil184, Tal194]. Hashed pagetables associate a tag with every PTE. Clustered page184tables associate a single tag for an aligned group ofconsecutive pages (e.g., sixteen 4KB pages), called apageblock. Clustered page tables are effective whenspatial locality makes it likely that consecutive pagesare in contemporaneous use. For the assumptionsgiven in Section 3, for example, a clustered page ta-ble with 16 pages per page block uses less memorythan a hashed page table if six or more pages arepopulated. Experimental results (Figure 9) show thatclustered page tables use less memory than the bestconventional page tables—linear page tables fordense address spaces and hashed page tables forsparse address spaces.Hardware designers are increasing the effective-ness of TLBs for 64-bit systems using techniquessuch as .wperpuges [Tal192] andsubblocking [Kane92,Tal194]. These techniques are very effective at im-proving TLB performance, reducing the number ofTLB misses by 50% to 99%, and providing an aver-age execution time speedup of upto 20% for theworkloads we use [Tal195]. However, without sup-port in the page table to store such PTEs or in theTLB handler to traverse such page tables, these TLBtechniques are completely ineffective. Page tablesthat support conventional single-page-size TLBs alsocan use superpage or subblock techniques to reducepage table size by an order of magnitude (Figure 10)and get better cache performance.Sections 4 and 5 present the second contributionof this paper: extending page tables to support su-perpage and subblock PTEs. We suggest replicatingPTEs at each base site as a way to extend any con-ventional page table to support the new PTE formatswithout affecting TLB miss penalty. We also presentalternate solutions that have some drawbacks butare usable in specific situations. Section 5 then showshow clustered page tables are ideal for supportingmedium superpages or subblocks, as they result insmaller page tables, while retaining fast TLB