Mosaic leverages virtual contiguity for locality, but does not use physical contiguity. Mosaic relies on recent advances in hashing theory to constrain memory mappings, in order to realize this physical address compression without reducing memory utilization or increasing swapping.

This paper presents a full-system prototype of Mosaic, in gem5 and modied Linux. In simulation and with comparable hardware to a traditional design, mosaic reduces TLB misses in several workloads by 6-81%. Our results show that Mosaic's constraints on memory mappings do not harm performance, we never see conicts before memory is 98% full in our experiments -at which point, a traditional design would also likely swap. Once memory is over-committed, Mosaic swaps fewer pages than Linux in most cases. Finally, we present timing and area analysis for a verilog implementation of the hashing function required on the critical path for the TLB, and show that on a commercial 28nm CMOS process; the circuit runs at a maximum frequency of 4 GHz, indicating that a mosaic TLB is unlikely to aect clock frequency.

Data-hungry applications, such as data and graph analytics, are often bottlenecked on the translation lookaside buer (TLB). A typical TLB can only cache a relatively small number of address translations-often caching fewer translations than the working sets of these applications. For example, the data-intensive Graph500 benchmark, when running a breadth rst search on a tree with over 2 20 nodes, has an approximate working set size of 215 MiB, whereas a typical TLB using 4 KiB pages can only cache translations for about 8.6 MiB of physical memory at once. Some of these applications, such as graph analytics, also tend to have irregular, pointer-based memory traversals with poor locality of reference, thwarting common heuristics such as prefetching. As a result, many modern applications report 20-30% overhead attributable to TLB misses [19,20,32,54], and some as high as 83% [5].

Address translation has become a bottleneck because TLBs have few entries, and their growth is much slower than system memory capacity growth. For instance, upcoming disaggregated memory technologies have increased main memory into the terabytes [35], yet Intel's recent Golden Cove server chips have only 2,488 discrete translations across all page sizes, even in the larger, L2 TLB [14]. TLBs have few entries to satisfy architectural constraints. L1 TLBs are on the critical path for L1 cache accesses, and therefore must be extremely fast. Moreover, TLBs tend to be power-hungry, consuming 3-13% of a processor's power, and higher associativity and deeper TLB hierarchies further increase dynamic energy usage [29].

One of the main techniques for increasing TLB reach is to increase the size of translation units, via the use of huge pages, segments, or opportunistic coalescing of contiguous entries. These techniques depend upon physical contiguity, and therefore incur the costs of defragmentation. Defragmenting physical memory is expensive and has no good solutions in the worst case-so much so that defragmentation can overwhelm any performance gains from greater TLB reach. For instance, Zhu et al. [66] recently report that a cold cache Redis workload shows a 29% throughput gain on Linux when switching from 4 KiB pages to transparent 2 MiB pages-with no fragmentation; when memory is 50% fragmented on Linux, however, throughput with 2 MiB pages drops to only 89% of the throughput with 4 KiB pages. The top depicts a stylized, traditional TLB, which maps virtual addresses (tags) to physical page frames. In this gure, a series of four virtually contiguous pages map to dierent physical addresses. The bottom shows how a Mosaic TLB compresses the same run of physical pages into one entry, by only storing the bucket and oset for each page. We note that the gures are truncated for brevity, but we assume a similar cache geometry for a traditional or Mosaic design.

Finally, some proposals mitigate fragmentation in large pages by adding more complex hardware, which can stitch together physically discontiguous sub-pages into a larger huge page [16,53,65]. For instance, perforated pages [40] introduce a shadow page table layer that redirects portions of a huge page to 4 KiB pages without the need to defragment. A key point about these designs is that the performance gains still come from the residual physical contiguity in the mappings; lling holes and combining sub-mappings is arguably more ecient in total than defragmenting memory.

This paper introduces mosaic pages, a technique for increasing TLB reach without using physical contiguity. Without the need for physical contiguity, one need not defragment memory. To demonstrate the feasibility and capabilities of mosaic pages, we present Mosaic, an end-to-end redesign of address translation mechanisms across the hardware TLBs and the OS. Mosaic internally uses the recently developed Iceberg hashing [8] for physical address compression and mitigating TLB conicts.

The key idea behind mosaic pages is to compress each address translation, so that multiple, virtually contiguous translations t into a single TLB entry, illustrated in Figure 1. We achieve our compression by restricting each virtual address to map to only a small number ⌘ of physical page frames (via hashing), so that a virtual page's physical address can be encoded using only log ⌘ bits. For concreteness, we set ⌘ = 104 in our experiments, which means we encode each translation in seven bits. In contrast, conventional virtual memory systems allow each virtual page to be mapped to (almost) any of the ? physical page frames, requiring log ? bits per address. We call one discrete translation a Compressed Physical Frame Number (CPFN), encoding which of the ⌘ page frames this virtual address maps to.

By compressing translations, we can pack translations for several contiguous virtual pages into a single TLB entry, expanding TLB reach by 0 = log ?/log ⌘ without increasing the number TLB entries. As we show in Section 3.1, we can increase coverage by at least 0 = 4 using TLB entries of the same size as in today's hardware. By widening TLB entries, we can plausibly increase 0 to 64 without prohibitive costs.

Like huge pages, mosaic pages leverage virtual contiguity but, unlike huge pages, do not require physical contiguity. In our design, each TLB sub-entry can be mapped independently. Furthermore, mosaic pages compose with other techniques, such as huge pages, because any base page size can be mapped by TLB sub-entries.

Mitigating conicts. The concern with reducing ⌘ is that it increases conflicts in mapping virtual addresses to physical pages, and resolving these conicts has a cost. Specically, when mapping a new virtual page, we may nd that its ⌘ allowed locations are already occupied by hot pages. In this case, the conict must be resolved, e.g., by swapping a conicting page to disk. Mapping restrictions may force the eviction of a hotter page than an unconstrained mapping would. The more restricted the mapping (i.e., the smaller ⌘), the more likely it is that a conict will make a worse eviction choice than an unconstrained mapping. On the other hand, smaller ⌘ decreases the size of TLB encodings, which mosaic uses to increase TLB reach. One of the principal contributions of this paper is showing that it is possible to have a small ⌘ with comparable swapping costs. Mosaic overview. Mosaic structures physical memory as a bucketed hash table, where each bucket consists of a collection of contiguous physical page frames, which we call slots. Each virtual address is hashed to a small number 3 of the buckets, and the virtual page may be placed in any of the ⌘ total slots among those 3 buckets. Thus, the TLB only needs to store an encoding of which of the ⌘ slots was chosen. In our experiments each virtual address is mapped to one bucket of 56 slots and 6 buckets of 8 slots, for a total of ⌘ = 104 slots, so the TLB entry eectively encodes a (bucket, slot) tuple as a small integer ( §2.2 and §3.1).

We note that although this paper uses hashing to increase TLB reach, mosaic does not require hashed or inverted page tables. A mosaic page table should support looking up the CPFN (instead of PFN) for a virtual address, but can otherwise be structured using radix trees, hash tables, etc. Our prototype uses a modied version of the standard radix-tree page table ( §3.1).

Mosaic's hashing scheme. The hash table underlying mosaic's page allocation should have the following properties: it must allocate pages to a small number of places (in order to reduce the size of a CPFN), it must, with very high probability, operate successfully at load factors within a few percent of 100% (so that each slot can be usefully occupied), and it must be stable, meaning that it does not move items to resolve conicts (to avoid complex and expensive page migration).

Interestingly, these properties seem to be at odds with each other, and it's not obvious that they can be attained simultaneously. For instance, one way to realize high load factors is to migrate entries in the table, as in cuckoo hashing, but this violates the stability goal. In fact, Iceberg hashing [7,8,38], the hashing scheme that we use in Mosaic, was rst proposed only last year and is the rst hash table to provably meet all of these criteria. Section 2.3 explains how iceberg hashing obtains all these seemingly contradictory properties simultaneously.

Our contributions. This paper contributes an end-to-end system co-design and implementation of mosaic pages, from the architecture to the OS. We implement the TLB changes in the gem5 simulator [12], and modify Linux to implement mosaic for anonymous, unshared pages.

Using this experimental infrastructure, we give a thorough demonstration that mosaic can indeed reduce TLB misses of realworld workloads, such as Graph500, by 6-81% in simulation with comparable TLB entry width as a current x86 chip.

Second, we contribute an implementation of our hashing scheme for the TLB in Verilog and measure it on an FPGA and with a 28nm commercial CMOS process. The timing analysis yields a maximum clock frequency of 4 GHz, indicating that the hashing we add to the critical path is unlikely to harm overall clock frequency or have signicant area cost.

Finally, the paper demonstrates empirically that mosaic under memory pressure has swapping comparable to an unconstrained page mapping. We measure swapping events on longer, bare metal workloads under two conditions: sucient memory and insucient memory. Our experiments show that, commensurate with Iceberg's probabilistic bounds, as long as only 2% of memory is held in reserve and the application(s) t into DRAM, conicts are not observed. We nd that the system swaps only after memory is over 98% utilizedsimilar to unmodied Linux swapping once memory is fully utilized. Once memory is over-subscribed, mosaic typically swaps less than default Linux.

Future work. The mosaic prototype leaves some features for future work. Most notably, we do not demonstrate support for shared memory mappings in the iceberg design, although we do outline how one might add this feature in future work ( §2.5). More broadly, modern memory protection has incorporated a number of features, such as encryption (Intel TME, AMD SEV), sub-page protections (e.g., Intel MPK), trusted execution environments (e.g., Intel's SGX), and nested paging; a production deployment of mosaic would need to integrate with a very long tail of features. This paper argues that the performance gains of mosaic are suciently appealing to warrant this future work.

In this section, we describe the design and theoretical background for mosaic pages.

A mosaic page is a large virtual page, composed of 0 virtually consecutive, but not necessarily physically contiguous, base pages (4 KiB). We say that 0 is the arity of a mosaic page. For concreteness, we use 0 = 4 as a default setting, but experiment with powers of two up to 64 in the evaluation ( §4). Moreover, it is even possible The TLB is indexed by the upper bits of the virtual address (the Mosaic virtual page number), and the TLB entry stores a run of 0 = 4 compressed physical addresses (CPFNs), which are virtually but not physically contiguous. Compression is realized through hashing a virtual address to a small number of physical frames; the TLB need only store which of the small number of frames was chosen-here, a bucket and oset.

that only a subset of the pages are in memory at any given moment. Hence, mosaic avoids the complexities and costs of maintaining physical contiguity.

The key idea is to compress each translation such that translations for all 0 = 4 base pages t in one TLB entry, as illustrated in Figure 2. Although the frames are allocated independently, we will ensure that each page's location can be encoded with just a few bits of information-these bits are known as the compressed physical frame number (CPFN) of the page. The TLB is indexed by mosaic virtual page number (MVPN) (or the aligned, virtual address of the mosaic page), and each entry in the TLB holds a series of CPFNs for each virtual page in that mosaic page. Together, we call these CPFNs the table of contents (ToC) for the mosaic page.

A TLB lookup for a virtual address returns the ToC for the relevant mosaic page. The base page oset within the mosaic page (or mosaic oset) then determines which entry in the )>⇠ corresponds to the desired virtual page. The CPU then uses the CPFN to compute the page's actual page frame number (PFN), which is explained in §2.2.

Mosaic pages increase the reach of the TLB by a factor of 0 by leveraging virtual locality, without requiring physical contiguity. To get a ballpark estimate of how much we can increase TLB reach, we consider current x86 TLBs, which use 36-bit physical frame numbers. If we use 8-bit CPFNs, then we can t 0 = 4 CPFNs in a single TLB entry, increasing TLB reach by a factor of 4. Furthermore, there is good reason to believe that we can actually increase the width of TLB entries without incurring too much cost in terms of power or chip area, so a future production implementation might have 0 = 16 or even larger.

TLBs typically store several pieces of metadata about each page, such as permissions and accessed/dirty bits. In our prototype, we store valid bits per CPFN, but assume other bits can be tracked at the granularity of a mosaic page, similar to other recent work on extending TLB reach [5,45]. We expect that most applications could be recompiled with linker directives to ensure all mappings are created with similar alignment and permissions. One could also widen the TLB and store all of these entries on a per-base-page basis.

Mosaic page tables map MVPNs to ToCs, but mosaic can use any page-table structure, such as radix trees, hash tables, or even a software-managed TLB, as long as they don't impose any page mapping restrictions that conict with mosaic's, described next.

The key to compressing PFNs is that whenever we need to allocate a physical frame for virtual address E, we limit ourselves to a small set of possible frames (⌘; for concreteness, ⌘ = 104 in our experiments). We use the term associativity to describe these limits on the number of frames that can map a given 4 KiB base page; although associativity is a common concept in hardware caches, here we are not discussing how data can be placed in CPU caches, but as a restriction on virtual page mappings. Thus the CPFN needs to indicate only which of the ⌘ options was chosen by the page allocator. This means that a CPFN can be stored simply as a number in the set {0, 1, , . . . , ⌘ 1}, which requires only log ⌘ bits.

Our page allocator treats the frames in physical memory as slots in a hash table, in which slots are grouped into buckets. Each VPN is mapped to one or more buckets via a hashing scheme, and the CPFN records which bucket and which slot within that bucket were chosen by the allocator. In practice, we hash (ASID, VPN) pairs, but for simplicity we omit the ASID except when relevant.

Note that this contrasts with conventional virtual memory schemes, in which every virtual page can be mapped to any physical frame. Thus, conventional virtual memory schemes are fully associative, whereas mosaic is a low-associativity virtual-memory scheme.

The potential drawback of low associativity is that, if it is implemented naively, then associativity conicts can become a problem. That is, because each virtual address has only ⌘ options for where it can go in physical memory, the system may be forced to swap some other virtual address that we would not otherwise choose to swap out. Thus, even if our working set size is smaller than physical memory, associativity conicts might prevent mapping the entire working set at once.

There are two core details to be lled in to complete this design: what hashing scheme do we use for page allocation, and what swapping algorithm to use?

The hashing scheme we use in our page allocation scheme must meet three criteria:

(1) Low Hashing Associativity: For each item (i.e., virtual address) the set of possible positions where the item could reside in the hash table is less than or equal to a small ⌘. (2) Stability: Once an item is inserted into the hash table, it is not moved until a future deletion removes it. This implies that once mapped, pages never need to be copied within memory to ensure good performance, whereas schemes like cuckooing must migrate elements to maintain performance. (3) High Utilization: If ? is the total number of slots in the hash table (i.e., the total number of physical frames), then the hash table can handle up to (1 X)? elements at a time for some small X (X ⇡ .02 in our experiments). Practically speaking, this means that nearly all of memory can be allocated (98% in our experiments) before seeing conicts, with extremely high probability.

Iceberg hashing. Mosaic allocates pages by using Iceberg hashing [8], a recently proposed hashing scheme that achieves the above three criteria simultaneously, which had long been an open problem in hash-table design. Many classical hash tables meet two of the three. For example, cuckoo hashing has low associativity and can have a load factor of > 90%, but moves items around (i.e., it is unstable). Other openaddressing schemes such as linear probing or quadratic probing can be stable and support high load factors, but have high associativity.

We now review Iceberg hashing, since it will be relevant to the overall design of mosaic. An Iceberg hash table consists of two components: a front yard and a (much smaller) backyard, illustrated in Figure 2. The front yard is broken into B bins of some xed size 5 = l (log log ?) (e.g., 5 = ⇥(log 2 log ?)). The backyard also consists of B bins, each with capacity 1 = ⇥(log log ?), where ? is the total number of slots in the hash table (i.e., the total number of frames in physical memory). Note that front yard and backyard buckets can be quite small in practice. For example, for 64-bit systems, log log ? ⇡ 5.7, so a reasonable choice would be front yard buckets of size 5.7 2 ⇡ 32 (or larger) and backyard buckets of size ⇡ 5.7 (or larger).

We illustrate insertion in Figure 3. Whenever an item G is inserted, it rst hashes to some bin ⌘ 0 (G) in the front yard. If there is a free slot in ⌘ 0 (G), then the insertion uses that slot (as illustrated in the rst case of Figure 3). Otherwise, if bin ⌘ 0 (G) is full, then G is placed into the backyard. Elements in the backyard are assigned a bin using the power of 3 choices: the element hashes to 3 bins ⌘ 1 (G), . . . , ⌘ 3 (G) and is placed in the emptiest of those bins. This is illustrated in the second case of Figure 3.

The full dynamics of the front yard/backyard scheme are quite dicult to analyze [8,9]. What one can show, however, is that as long as 5 = l (log log ?), then the number of elements in the backyard will always be > (?/log log ?). Then, a classic theoretical result on the power-of-3-choices [59] guarantees that the probability of bins in the backyard overowing is negligible, so the hash table supports space utilization 1 X for very small X = > (1). These Pages are divided into buckets, split into a front yard and backyard. For specicity, we illustrate using the mosaic prototype parameters: bucket size of 64 page frames, split into a front yard of 56 frames and a backyard of 8 frames. Gray frames are in use. The rst insertion of the fucshia page mapping uses ⌘ 0 to select a front yard bucket; in this case, there is space so the mapping is created. In the second insertion of the cyan page mapping, the front yard bucket is full. Thus, the hash scheme selects 3 = 6 backyard buckets and maps the cyan virtual page to a frame in the least full backyard.

theoretical guarantees hold with high probability over the random choices made by the algorithm, i.e., the choice of hash function, for any set of page requests made without knowledge of the algorithm's randomness (i.e., the hash function). We measure empirically in Section 4.2 that X is roughly 2%. Moreover, the hash table is stable and has associativity ⌘ = 5 + 3 • $ (log log ?). Thus Iceberg hashing is an ideal candidate to serve as the theoretical starting point for mosaic.

In our prototypes, we use front yard bins of size 5 = 56, backyard bins of size 8, and 3 = 6. As a consequence, the total associativity ⌘ is 104, so the number of bits in a CPFN is 7.

Mosaic frame allocation. Mosaic structures memory as an Iceberg hash table and uses Iceberg hashing for page allocation. Allocating a mosaic page is analogous to inserting into an Iceberg hash table: we hash the virtual address to a front yard bucket and, if there is room in the bucket, store the page there. Otherwise we attempt to store it in a backyard bucket chosen using the power of 3 choices.

When no slot is available for a new allocation, we must choose a page to evict. Specically, we must choose a page from among the buckets that can be used for the new allocation. To solve this problem, we propose a new eviction algorithm, Horizon LRU , that is designed specically to work with Mosaic. Horizon LRU is based on an algorithm with strong bounds on its paging costs (relative to baseline LRU) and, as we will see in §4, good performance in practice. The naive solution of simply evicting the least-recentlyused page in the target buckets does not have the same performance guarantees.

Horizon LRU builds on prior work [7], which described an ecient page-eviction algorithm for a low-associativity cache. The key idea in prior work is to simply implement cache replacement as if the cache were slightly smaller (less than 1 X in size), so that one never sees associativity conicts, only capacity evictions. The total number of evictions will be the same as LRU running on a fully associative cache of size (1 X)?. The downside of this algorithm is that it completely wastes a fraction X of memory.

Horizon LRU extends the above ideas, making two improvements while preserving the theoretically backed structure of the page eviction algorithm.

First, Horizon LRU does not evict any page until absolutely necessary. Rather, it marks pages that would be evicted unnecessarily as ghost pages. Ghost pages are kept in memory in case they are referenced again, but the page allocation algorithm treats them as if their frames are free. So, for example, if there is a ghost page in the front yard bucket for an allocation, then it actually evicts that page and uses its slot for the new allocation. In the backyard, ghost pages do not count towards a bucket's occupancy when choosing the least-occupied bucket in the power-of-3-choices algorithm.

Second, Horizon LRU exploits the local structure of the mosaic page-allocation scheme to implement LRU without having to maintain a global LRU list. Horizon LRU tracks the last time that each page was accessed, as well as a global time stamp, called the horizon, which is the high-water mark of the access times of all pages it has evicted. All pages whose most recent access time is prior to the current horizon are ghosts.

Horizon LRU simulates a global LRU algorithm because every time we update the horizon, we are marking all the pages with access times older than the new horizon as eectively evictedexactly the set of pages that a global LRU algorithm would have actually evicted.

There are some limitations that arise as a result of the dependence of PFNs on their corresponding VPNs and the process's ASID. In particular, the set of possible PFNs for one (ASID, VPN)-pair are generally completely distinct from those of a dierent (ASID, VPN)pair. As a result, mosaic pages as described above do not support duplicate mappings of the same physical memory within a single address space, or page sharing across address spaces. Similarly, as described above, mosaic does not support multiple mappings of the same le, even within a single address space.

We see several options in a large design space of possible solutions to the page sharing problem, either through special casing or a layer of indirection. We present a few representative solutions below. Ultimately, determining the best course will require careful empirical evaluation to ensure a careful balance among competing concerns, including latency, space usage, application requirements, and chip area.

A simple way to support page sharing is to introduce specialcasing for shared pages so that they use traditional (non-Mosaic) TLB entries.

There are also approaches that more directly integrate shared pages into the Mosaic framework. For example, rather than using (ASID, VPN) as the input to the hash function, we give each ToC a unique identier, which we call its location ID. Then, to determine the PFN of the 8th page within any mosaic page, we hash (location ID, 8) instead of (ASID, VPN). Now we can use the same ToC multiple times within a single process's address space (for, e.g. duplicate mmaps), or use it in dierent address spaces to create shared memory.

This approach has two costs. First, each TLB entry needs to store its ToC's location ID, so TLB entries get larger. Second, during address translation, the hash function cannot be evaluated until after the TLB lookup completes, whereas hashing (ASID, VPN) could be done in parallel with the TLB lookup. This could potentially increase the latency of address translations. We can compensate for the lack of parallelism as follows. First, we have the OS generate location IDs randomly. (Although this may cause a few ToCs to be assigned the same location ID, Iceberg hashing is robust enough to handle this.) Now we can use extremely simple, low-latency hash functions, because the inputs to the hash functions are already randomized.

One could also adapt techniques used in other contexts to address the problem. For instance, rather than assigning a unique location ID to every ToC, one could assign location IDs to each segment and use a modest table of segments to translate (ASID, VPN) pairs to (location ID, oset) pairs. Or one could adapt techniques for handling aliases in virtually indexed caches, which map one virtual address to another within the cache [64]. We leave it as future work to evaluate these approaches.

This section describes the gem5-based mosaic hardware simulator and prototype mosaic page allocator in Linux that we implemented in order to evaluate the performance and feasibility of mosaic pages. Mosaic pages require changes to four system components: the TLB, the page table, the OS page allocator, and the OS page eviction algorithm.

We implement mosaic pages using gem5 [12], a widely used architectural simulator. Our implementation involves systematically redesigning both the TLB and parts of the traditional radix-tree page table, and provides a full system simulation with support for mosaic pages.

Mosaic TLB. We extend gem5 to support mosaic TLB entries, using front yard buckets of size 5 = 56, backyard buckets of size 1 = 8, and 3 = 6 choices of backyards. Thus the total associativity of the page allocation scheme is 56 + 8 ⇥ 6 = 104. We encode CPFNs into 7 bits as follows. An unmapped page is the all-ones CPFN. Otherwise, the leading bit indicates whether the page is mapped to the front yard or the backyard. If it is mapped to the front yard, then the remaining 6 bits indicate the frame oset within the bucket. If it is mapped to the backyard, then the next 3 bits indicate which of the 6 backyard buckets was chosen, and the last 3 bits indicate the frame oset within that bucket. We store a valid bit per sub-page, and we use additional bits for permissions and other metadata, at mosaic page granularity.

Our mosaic TLB model takes as a parameter the mosaic arity, which may lead to very wide TLB entries when congured with large arity. By default our simulator uses an arity of 4 and 7-bit CPFNs. This yields ToCs of 28 bits, which mean that TLB entries are smaller than the 36-bit PFNs stored in most current x86 TLBs. Note that the mosaic TLB design changes the update and decode logic for TLB entries (and maybe their width), but the mosaic memory mapping restrictions are orthogonal to the associativity of the TLB itself. Therefore a mosaic TLB can store the TLB entries using any caching design that it could use for a conventional TLB. So, for example, the TLB hardware could store TLB entries in a fully associative cache, a direct-mapped cache, or an N-level associative cache. We analyze the eect of dierent TLB associativity levels in Section 4.1.

When the OS invalidates a mapping of a sub-page within a mosaic page and invalidates the TLB entry, our TLB model only invalidates the sub-page's entry within the larger mosaic page's ToC. We do not invalidate the entire mosaic page's entry in the TLB. Upon a capacity miss, the TLB manages its own space using LRU to evict TLB entries for an entire mosaic page.

In our gem5 model, for ease of simulation, we maintain one TLB for the conventional (vanilla) mode and another TLB for the mosaic mode; results are computed for both modes simultaneously. Each memory access is fed to both TLBs with a separate page table walker for each TLB to handle misses. In mosaic mode, a conventional mapping consumes an entire TLB entry. We did this to keep the total number of TLB entries consistent for the evaluation, while compensating for the lack of sharing (i.e., shared pages still take up space in the TLB).

We further note that our model treats all shared pages as if they were copied and unshared in a mosaic address space, and are therefore compressible. None of our workloads use shared memory other than for library code, but it does mean that our results reect a marginal trade of DRAM space for higher TLB reach.

Hash functions. In order to maintain TLB hit performance, we require a hash function that can run within the latency of the L1 TLB. Tabulation hashing is an established hashing technique that can produce high-quality hash values using small static tables [43]. Specically, for an input each byte 1 2 is an index into separate which may be any structure; here, we present a traditional radix tree. As an optimization, the leaf nodes are modied to store tables of contents (ToCs), which are decoded to identify the physical location of the pages, using the same logic as TLB entries.

tables, each with 256 entries. The values returned by all these tables are then XOR'd together to give the output of the hash.

To produce multiple hash results from a single set of tables we probe from the value of 1 using the hash function id as an oset. For example, with 4 hash functions and a static table ) , the hashes of an input would be 0

Probing in this way allows us to produce suciently random hash results without the need for additional tables (and thus power and chip area) for each hash function. This design is outlined in Figure 4.

Note that a hardware implementation can compute all the hash functions in parallel with the TLB lookup to obtain the CPFN. It can then use the CPFN to select the correct hash function's output and compute the PFN.

Mosaic page table structure and hardware. In large part, the changes required by mosaic pages are orthogonal to the page table design. In our simulation, we modify the leaves of the page table to map MVPNs to ToCs, illustrated in Figure 5, but we keep the overall radix-tree structure of the default gem5 page table. This structure allows the system to eciently fetch and map a virtual mosaic page to ToC translation.

Our current prototype stores permission, present, accessed, and dirty bits in the page table for each encoded physical page in the ToC, even though permission bits must be identical within a mosaic page. The TLB currently only caches the present bit per CPFN, and other bits at the granularity of a mosaic page. We retain this exibility in the page table to study the impact of this restriction in future work.

This section describes our prototype implementation of mosaic page management in Linux. This prototype is designed to run on unmodied hardware, so it implements only the restricted allocation and swapping mechanisms used in mosaic pages and uses the standard TLB and page table from x86 (in contrast to Section 3.1). However, all allocations and swaps obey the mosaic rules in Section 2, and so the prototype faithfully captures the conicts that a full mosaic paging system would incur.

Specically, we implement the mosaic page allocator in Linux kernel version 5.11.6. This allocator replaces the Linux allocator only for anonymous memory allocation. To support this, memory is split into two parts: at boot time a xed amount (4 GiB) of physical memory is reserved for the mosaic page allocator, and the rest is used for the Linux default page allocator. We allocate anonymous, unshared memory for the process under test from this pool; all shared mappings, le caches, and the kernel are still placed in pages used by the standard Linux page allocator. We evaluate the system with applications whose space usage is largely anonymous, unshared mappings. Our prototype does not support inheriting mosaic pages via fork(), which would cause anonymous pages to become shared; our test applications do not use fork() to create child processes.

Our prototype Linux mosaic page allocator uses the same parameters as our gem5 simulator, i.e., front yard buckets of size 5 = 56, backyard buckets of size 8, and 3 = 6 choices. Each bucket contains a linked list of free pages. When a process requests an anonymous page, the allocator hashes the (ASID, VPN)-pair in order to obtain the buckets which can be used for allocation, as in Section 2. We use xxHash [13], a fast hash algorithm available in the mainline Linux kernel. The allocation happens when the process accesses the page because Linux uses demand paging.

Horizon LRU in Linux. We implement swapping using the Horizon LRU algorithm as described in Section 2.4.

One challenge is that Horizon LRU requires access timestamps, but current hardware maintains only access bits, not timestamps. A real mosaic page system would store timestamps instead of access bits, so this is only a challenge for our prototype, not of a real mosaic system. Our implementation uses the access bits to emulate up-to-date timestamps. We create a background daemon, which scans mosaic memory at regular intervals (1 s by default). If a page has been accessed since the last scan, we update the timestamp and clear the accessed bit. In the x86 architecture, a processor invalidates TLB entry once software clears the access bit in the corresponding page table entry. This leads to a high TLB misses and becomes an overhead. To alleviate the overhead, we use a sampling based approach [32]. For each page, we maintain 8 recent histories of access status, and classify the page is hot or cold. During scanning, we always read and clear the access bit of cold pages. For hot pages, we read and clear the access bit for 20% of pages and we consider remaining 80% of pages as accessed.

This section presents experiments to answer the following questions about Mosaic performance:

Table 1a describes the system that we simulated using gem5. We vary the TLB in two dimensions. First, we vary the mosaic arity from 4 to 64, i.e., we vary the size of mosaic pages from 16 KiB to 256 KiB. Second we vary the associativity of the TLB from directmapped to fully associative. To study the TLB performance of Mosaic compared to a standard "vanilla" TLB, we run four widely used workloads, Graph500, BTree, GUPS, and XSBench using full system gem5 hardware simulation. Table 2 shows the total instructions simulated.

Figure 6 shows the number of TLB misses incurred during each workload. Vanilla represents standard Linux and x86 page tables. Although we disabled huge pages for application use, the Linux kernel itself was mapped using huge pages in vanilla, giving vanilla a slight advantage over mosaic.

The high-level take-away is that mosaic pages can reduce TLB misses across a wide variety of workloads and TLB associativities.

In many cases, Mosaic can reduce TLB misses by a dramatic amount, e.g., almost completely eliminating them in Graph500 and XSBench, reducing them by up to about half in B-Tree and about a quarter in GUPS.

Mosaic arity. In this experiment, we measure the sensitivity of the TLB misses to the number of CPFNs that are in one TLB entry (arity). We vary the number of CPFNs from 4 to 64. Note that with an arity of 4, all 4 CPFNs t in a single unmodied x86 TLB entry. Even with an arity of only 4 (Mosaic-4), Mosaic shows a substantial reduction of 6-81% in TLB misses for Graph500, BTree, and XSBench workloads, and with an arity of 64 (Mosaic-64) reduces misses by 11-98%. Mosaic shows less improvement on GUPS, which is unsurprising, because GUPS is a synthetic benchmark designed to stress the system with extremely random memory accesses. TLB associativity. As Figure 6 shows, increasing TLB associativity reduces TLB misses for all approaches due to reduced conict misses. However, switching from a vanilla TLB to a mosaic TLB is far more eective at reducing TLB misses than increasing the associativity of the TLB. For example, observe that a direct-mapped Mosaic-8 TLB outperforms a fully associative vanilla TLB for Graph500, BTree, and XSBench. In fact, the performance of Mosaic is not signicantly impacted by TLB-associativity indicating that a Mosaic system could use more ecient lower-associativity TLB designs.

We note that vanilla with a fully associative TLB out-performs Mosaic-4 on Graph500 and Mosaic-4-16 on GUPS. This is because vanilla Linux uses huge pages to map the kernel, eectively gaining a slightly larger TLB than Mosaic. Smaller experiments with huge pages fully disabled remove this artifact (giving all Mosaic arities fewer TLB misses than vanilla), but we were not able to complete all simulations with this change in time for the nal paper deadline.

In this section we empirically measure X, the memory overhead discussed in Section 2, and compare this to the memory utilization achieved by the default Linux virtual-memory subsystem.

The hardware and software used in these experiments are presented in Table 1b. Each data point reports the average and standard deviation of ten runs, unless otherwise stated. We use the seq-csr implementation of Graph500 unless otherwise stated. To reduce noise from various processes in the system, we use the Mosaic page allocator only for the benchmark process. All other processes on the system use the default Linux allocator.

We scale the workloads down to approximately 4 GiB and limit memory for the test workload to 4GiB, in order to work around missing features in our current prototype, such as the inability to put the kernel or shared mappings in mosaic pages. The other 28 GiB are available only for system background processes, not the benchmark. We limit application memory on unmodied Linux using cgroups. We restrict the amount of mosaic memory in our prototype to 4 GiB, except for a small amount of le memory (~400 KiB), which we could not easily restrict in the mosaic case. This memory split is an experimental artifact, not a design feature.

As discussed in Section 2, Mosaic may start to have associativity conicts once it hits a memory utilization of 1 X. However, memory Table 3: Memory utilization under the Mosaic page allocation at the point of the rst associativity conict, and the steady-state utilization over the entire workload. The standard Linux allocator begins swapping at about 99.2% memory utilization, so Mosaic has essetially no memory overhead in these benchmarks.

First associativity conict (1 X) utilization can go beyond 1 X due to ghost pages ( §2.4). To evaluate these two eects, we measure both the memory utilization when our benchmark experiences its rst associativity conict and its steady-state memory utilization over the entire benchmark run. We measure this by running Graph500, XSBench, and BTree congured to have memory footprints between 4.06GB to 4.80GB, so that, in a fully associative paging scheme, memory would be nearly 100% utilized. Table 3 presents the memory utilization at the time of the rst associativity conict (1 X) and the steady-state memory utilization.

As the table shows, the rst conict appears at around 98.03% utilization across all workloads, indicating that X is roughly 2%. In contrast, we observed that Linux with the default allocator began swapping once memory utilization reached 99.2% (because each memory zone has its own watermark). Thus Mosaic's associativity restrictions do not cause Mosaic to begin swapping signicantly sooner than with the default Linux allocator. Furthermore, over the entire execution, the workloads are able to utilize over 99.2% of available memory, and this increases as the footprint increases, so the overall memory overhead of Mosaic is less than 1%.

We run each workload with a variety of memory footprints, from just over the size of available memory to about 57% larger, and report the total number of swap I/Os as reported by sysstat. We use the same hardware and software as in the previous section. We present the average of 5 runs. Standard deviations were all below 5%.

Table 4 compares the behavior of Mosaic's swapping algorithm, Horizon LRU ( §2.4), to the default Linux implementation. The dierence column gives the percent reduction in swapping I/O performed by Mosaic (i.e. higher is better). Green cells indicate that Mosaic When the workload is just slightly over the size of available memory, Mosaic performs more swapping than the default Linux allocator. This is because, as we showed in Section 4.2, Linux is able to utilize about 1% more memory than Mosaic. However, once the workload footprint passes this edge case, Mosaic matches or outperforms Linux, sometimes by a signicant amount (up to 29% in the best case). This may be because the associativity restrictions in Mosaic slightly perturb LRU's choices, preventing it from suering from well-known bad cases, such as cyclic memory references.

We used a two-step hardware evaluation to assess the viability of our approach. Our rst set of evaluations were performed using an FPGA fabric. We then performed an evaluation using a 28nm CMOS process/foundry with more detailed timing analysis.

For our FPGA implementation, we evaluated the latency and area impact of adding hashing to the TLB hit path, as described in Synthesizing for an Artix-7 FPGA, we used simple lookup tables to implement the static tables. We found the latency of the Tabulation Hash circuit to be 2.155ns or a clock frequency of 464MHz. When varying the number of hash functions from 4-8, the clock frequency of the circuit was unchanged. Increasing the number of hash functions increases the number of values extracted from the static tables and the size of the post-table muxes. As the latency of the circuit is unchanged, generating multiple hash outputs by probing as described in §3.1 is an ecient approach. Furthermore, the Tabulation hash circuit with eight hash functions requires 6208 Slice LUTs, 32 Slice Registers, 2880 F7 Muxes, and 160 F8 Muxes. Table 5 gives the sizes of the circuit with other quantities of hash functions.

Encouraged by these results, we also then implemented our hardware changes in System Verilog and synthesized it using a commercial 28nm CMOS process. We implemented the static tables as registers, and used Cadence synthesis tools with standard cell libraries to generate results. We present results for the worst-case variation corner (i.e., Tr FF , Vdd MIN , and RC BEST , at 1V Vdd, 125 °C).

The synthesized circuit ran at a maximum frequency of 4 GHz and a latency of 220 ps and 20 picoseconds positive slack. Additionally, increasing the number of hash functions did not increase the latency while increasing the area minimally. This increase in area is due to larger muxes needed to select from more values looked up from the table. Therefore, generating multiple hash outputs by probing as described in §3.1 is an ecient approach. The design uses 13.806 KGE area for 8 hash functions, normalized to a 2-input NAND gate in our process node when using 8 hash functions.

Because virtual memory is a nearly ubiquitous abstraction for programmers, ensuring low address translation overheads is a perennial goal. Prior research on navigating the tension between increasing TLB reach and the costs of defragmentation spans decades. This section describes related work on improving TLB reach through larger pages and more ecient defragmentation, as well as MMU caching. Like Mosaic, hashed page tables use hashing to accelerate address translation, although hashed page tables are intended to reduce TLB miss costs and total space overhead of page tables, whereas mosaic increases TLB reach. We also summarize prior research that reduces the associativity of memory mapping.

On current hardware, one must balance the CPU costs and memory bandwidth of defragmentation against potential gains from huge pages, as one can easily squander the performance gains from huge pages on defragmentation overhead [32,39,66]. Several works have proposed techniques that balance the costs of defragmenting memory in the OS with gains from TLB coverage [32,37,62,66]. A related issue is memory bloat-when an application maps huge pages but would use considerably less space with smaller pages. Memory bloating increases memory pressure and can induce swapping [37]; for this reason, many databases recommend disabling huge pages [36,48,51,60]. An underlying reason for both issues is that performance gains from contiguity are all-or-nothing.

In order to mitigate defragmentation costs and memory bloat, one can tolerate some discontinuity in the physical memory backing a huge page, such as by adding an intermediate address translation layer and augment hardware [16,40,53,65]. A recent example is perforated pages [40], which start with a 2 MiB huge page but allow the OS to redirect individual 4 KiB "holes" to dierent physical pages. This requires an extended page table structure to map these hole pages and extend both the L1 and L2 TLB with bitmaps to lter holes and trigger additional page table traversals. This indirection is also sucient to handle issues such as sharing regions of memory across processes or unusable regions of DRAM ("dead pages"). The performance intuition behind these techniques is that if one could not form an entire huge page, but had enough contiguity to split the virtual huge page into a small number of discrete physical extents, this is an improvement over falling back to strictly using 4 KiB pages. Mosaic also composes larger pages from dis-contiguous physical pages; a key distinction is that mosaic leverages a low-associative hashing scheme to reduce hardware costs while providing sucient exibility for software.

In summary, the road to huge pages has not been smooth. Despite the appeal and apparent simplicity of huge pages and decades of research, transparent support for 2MiB pages is still under active development, and modern OSes do not transparently support 1 GiB pages yet.

Alternatively, there are approaches to increase the TLB reach by redesigning the TLB layout. A related strategy to leverage smaller contiguity than a huge page is to coalesce adjacent TLB entries into one entry if the entries happen to be both virtually and physically contiguous [45]. This approach adds modest hardware to infer when TLB entries can be coalesced; later work shows OS support for coalescing [42]. For TLB coalescing, the performance gains are proportional to the amount of physical and virtual contiguity, and unlike standard huge pages, this approach does not depend on 2MiB increments in contiguity.

In a cache design, subblocking (or sectoring) is a technique to leverage spatial locality to cache a larger block from a set of subblocks [23,33]. Correspondingly, there are approaches to apply subblocking to TLB design [55]. Some MIPS processors have a TLB with a subblock factor of two, which means single TLB entry stores two dierent PFNs for two adjacent VPNs [22], at a cost of widening the TLB entry by the additional PFNs. Mosaic can be viewed as a TLB with a subblocking factor of arity (four in our prototype), combined with PFN compression, which ensures that Mosaic pages t within the same TLB entry width.

Perhaps most similar to this work are several papers based in part on the observation that even non-contiguous pages are often nearby in physical memory, enabling a form of prex compression by sharing the upper bits in the physical address and packing the diering, lower bits into the entry [2,44,57]. All these papers and Mosaic improve TLB reach when virtual mappings are constrained. Although these papers relax the contiguity requirements, Mosaic removes the need for contiguity altogether.

Another approach to economize TLB entries is by introducing segmentation, specically on dedicated servers without multitenancy and workloads size matched to server memory capacity. Basu et al. [5] show that a single, variable-sized segment can eliminate nearly all TLB misses for a set of common workloads by increasing virtual and physical contiguity. This idea has been extended with multiple segments (or ranges) [28,41]. However, these approaches leverage deployment-specic characteristics, such as no swapping, that would not necessarily be true of all deployments.

Orthogonal designs have explored increasing TLB reach by moving the TLB o of the hit path for the L1 cache and onto the miss path. However, for this to work, caches accessed without the TLB must be indexed by a virtual address rather than a physical address, called virtual caching [6,18,30,41,61]. However, virtual address indexing complicates shared data handling. In contrast, mosaic techniques increase the reach of a TLB, regardless of whether the TLB is on the L1 cache hit path; however, the need to compress physical addresses is more acute when the TLB is accessed on the L1 hit path.

Reducing the associativity of virtual memory mappings has been used to optimize CPU cache behavior. Page coloring [31,58] is a technique to ensure that sequential virtual pages will not contend for the same cache line. However, the introduction of multi-way set-associative caches reduces the demand for page coloring. As a result, some OSes, including Linux, do not support page coloring [24]. Although page coloring restricts the physical page placement, the resulting associativity is much higher than Mosaic, e.g., in a system with 4 GiB RAM with 128 colors, each virtual page can be mapped to 8,192 physical page frames. Because Mosaic's mapping restrictions are more stringent than page coloring, it is unlikely that the two techniques can be protably combined. However, Mosaic's randomization of virtual-to-physical mappings may be sucient in expectation to avoid the cache pathologies prevented by page coloring, which we leave for future work.

Several works studied how to use main memory as set associative caches. Alan Jay Smith studied the performance of set associative main memory mapping, nding a small increase in the number of page faults compared to LRU in a fully associative memory mapping design [50]. More recently, Picorel et al. [47] proposed setassociative memory for near-memory processors. They observed that a 4-way set associative memory can eliminate most conict misses of a single process application. Conventionally, restricting physical page placement comes with a cost of a memory underutilization. To avoid this issue, Utopia [27] splits system memory into multiple segments, exible segments and restrictive segments; a restrictive segment is organized as a set associative memory. Utopia measures the number of TLB misses for each page and records the counter in the page table entry. Pages with a high TLB miss count are migrated into a restrictive segment. In summary, prior work has shown that the exibility of fully associative memory comes at a cost, and that this high degree of exibility may not be strictly necessary.

A complementary approach to increasing TLB reach is reducing the costs of a TLB miss. Specically, by caching portions of the page tables in hardware MMU caches [3,10,11], one can potentially eliminate a series of sequential loads to walk the page table data structure. These caches are also amenable to common optimizations such as pre-fetching and speculation [4,46], which can further reduce the TLB miss penalties. The eectiveness of these caches is also a function of the complexity of the underlying mapping structure: these caches are very eective for nested hardware page tables [1,4,10], where each memory access in the guest triggers a page table walk in the supervisor, Translation-triggered prefetching observes that by integrating MMU caches with data caches, one can use TLB miss information as a hint to prefetch the related data into the data caches, with very high accuracy. This prefetching can be further improved with modest changes to how the OS places page tables in physical memory [34]. The primary downside of these techniques is that they all require more chip area and power.

Hashing has also been used in page tables [15,17,21,25,26,56]. In a hashed page table, upon a TLB miss, the CPU hashes the requested virtual address and process identier to identify a bucket of page table entries. Ideally, this bucket holds only the target page table entry, and requires only one memory reference to determine the physical address. Much more commonly, this bucket stores a collision chain of such page table entries, requiring several memory references to identify the desired page table entry [3]-easily eroding the best-case gains in the worst cases. Recent work [49,52,63], however, suggests that these shortcomings may not be fundamental to the hashed page table approach, but rather to the choice of hashing schemes. More recent work also points out the opportunity for nested, hashed page tables to unlock more parallelism in the TLB miss path than a radix-tree page table structure [52].

A key distinction between Mosaic and hashed page tables is that Mosaic uses hashing to increase TLB reach (and, thus, the TLB hit rate), whereas hashed page tables reduce the TLB miss cost. Mosaic is compatible with any page table design, and in our prototype, we retain radix-tree page tables.

Mosaic's iceberg hashing may improve upon cuckoo hashing in the page table, which we will explore in future work. However, we do note that in cuckoo hashing-based page tables, the tables must be resized after they reach an occupancy threshold (60% occupied in Elastic Cuckoo Tables); at this point, page contents must be copied to new frames. A key improvement of Iceberg hashing is that it is stable and has a high load factor: even when memory is nearly full, page contents do not need to be copied to new frames to ensure the same performance as when the memory is not full. A key contribution of the mosaic design is delaying conicts (and conict resolution) until the system would swap anyway.

This paper shows how one can compress physical addresses in the TLB, thereby reducing TLB misses for big data workloads by 6-81% with comparable hardware, and even further with wider TLB entries. Many techniques for increasing TLB reach rely on physical contiguity, whereas Mosaic does not require contiguity or defragmentation. Moreover, we show that these constrained mappings do not induce additional swapping on average. Key to these results is a hashing scheme with the right properties for address translation: a high load factor, stability, and relatively few choices. Finally, Mosaic is compatible with many of the techniques in the literature to increase TLB reach, and these techniques can be protably composed in future work.

The data that support the ndings of this study are openly available in Zenodo at http://doi.org/10.5281/zenodo.7709303, reference number [67].

Verilog. The output of the analysis should be visible as a report in the verilog tools. Under "Route Design" you should nd a "Timing Summary -Route Design" le. This le will should state the worst slack and total violation is -0.155ns. Since the design was synthesized using a clock with a period of 2ns, this means the minimum operational clock period of the Verilog design is 2=B + .155=B = 2.155=B, which implies a maximum operational clock frequency of 464 MHz. Resource utlization can be found in the tabulationHash4_utilization_placed.rpt in reports.

We expect these results to be deterministic with respect to the input parameters.

Gem5. Our scripts support easy customization of simulation parameters including the table of contents (ToC) size (for Mosaic only), the associativity of the TLB, and the application to run. The scripts can be edited to adjust application parameters, or other architectural parameters we did not vary in the paper.