The TLB is increasingly a bottleneck for big data applications. In most designs, the number
of TLB entries are highly constrained by latency requirements, and growing much more
slowly than the working sets of applications. Many solutions to this problem, such as huge
pages, perforated pages, or TLB coalescing, rely on physical contiguity for performance
gains, yet the cost of defragmenting memory can easily nullify these gains. This paper
introduces mosaic pages, which increase TLB reach by compressing multiple, discrete …

This article introduces mosaic pages, which increase TLB reach by compressing multiple,
discrete translations into one TLB entry. 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. Mosaic reduces TLB misses in several
workloads by 6–81%. Our results show that Mosaic's constraints on memory mappings do …