Hardware Translation Coherence for Virtualized Systems
Zi Yan Guilherme Cox Jan Vesely Abhishek Bhattacharjee

On The Compound MIMO Wiretap Channel with Mean Feedback
    ^†Amr Abdelaziz, ^†C. Emre Koksal and ^†Hesham El Gamal     ^*Ashraf D. Elbayoumy ^†Department of Electrical and Computer Engineering     ^*Department of Electrical Engineering

The Ohio State University     Military Technical College

Columbus, Ohio 43201     Cairo, Egypt

    December 30, 2023
======================================================================================================================================================================================================================================================================================

plain



To improve system performance, modern operating systems (OSes) often
undertake activities that require modification of virtual-to-physical
page translation mappings. For example, the OS may migrate data
between physical frames to defragment memory and enable
superpages. The OS may migrate pages of data between heterogeneous
memory devices. We refer to all such activities as page
remappings. Unfortunately, page remappings are expensive. We show that
translation coherence is a major culprit and that systems employing
virtualization are especially badly affected by their overheads. In
response, we propose  or , a readily
implementable hardware mechanism to piggyback translation coherence
atop existing cache coherence protocols. We perform detailed studies
using KVM-based virtualization, showing that HATRIC achieves up
to 30% performance and 10% energy benefits, for per-CPU area
overheads of 2%. We also quantify HATRIC's benefits on systems
running Xen and find up to 33% performance improvements.





§ INTRODUCTION

As the computing industry designs systems for big-memo­ry workloads,
systems architects have begun embracing heterogeneous memory
architectures. For example, Intel is integrating high-bandwidth
on-package memory in its Knight's Landing chip, and 3D Xpoint memory
in several products <cit.>. AMD and Hynix are releasing
High-Bandwidth Memory or HBM <cit.>. Similarly,
Micron's Hybrid Memory Cube <cit.> and
byte-addressable persistent memories <cit.> are quickly gaining
traction. Vendors are combining these high-performance memories with
traditional high-capacity and low-cost DRAM, prompting research on
heterogeneous memory architectures <cit.>.

Fundamentally, heterogeneous memories are dependent on the concept of
page remapping to migrate data between diverse memory devices for good
performance. Page remapping is not a new concept – OSes have long
used it to migrate physical pages to defragment memory and create
superpages <cit.>, to migrate pages among NUMA sockets
<cit.>, and to deduplicate memory by enabling
copy-on-write optimizations <cit.>. However, while page remappings were used sparingly
in those scenarios, they are likely to be used more frequently for
heterogeneous memories. This is because page remapping is essential to
adapt data placement to the memory access patterns of workloads, and
to harness the performance and energy potential of memories with
different latency, bandwidth, and capacity
characteristics. Consequently, developers at IBM and Redhat are
already deploying Linux patchsets to enable page remapping amongst
coherent heterogeneous memory devices <cit.>.




































Unfortunately, these efforts face an obstacle – the high performance
and energy penalty of page remapping. There are two components to this
cost. The first is the overhead of copying data. The second is the
cost of translation coherence. When privileged software remaps a
physical page, it has to update the corresponding virtual-to-physical
page translation in the page table. Translation coherence is the means
by which caches dedicated to translations (e.g., Translation Lookaside
Buffers or TLBs <cit.>, etc.) are kept up to date with the latest page table
mappings.

Past work has shown that translation coherence overheads can easily
consume 10-30% of system performance <cit.>. These overheads are even more
alarming on virtualized systems, which are used in the server and
cloud settings expected to be early adopters of heterogeneous
memories. We are the first to show that as much as 40% of their
runtime can be wasted on translation coherence. The key culprit is
virtualization's use of multiple page tables. Architectures with
hardware assists for virtualization like Intel VT-x and AMD-V use a
guest page table to map guest virtual pages to guest physical pages,
and a nested page table to map guest physical pages to system physical
pages. Changes to the guest page table and in particular, the nested
page table, prompt expensive translation coherence activity.

The problem of coherence is not restricted to translation mappings. In
fact, the systems community has studied problems posed by cache
coherence for several decades <cit.> and has developed
efficient hardware cache coherence protocols <cit.>. What
makes translation coherence challenging is that unlike cache
coherence, it relies on cumbersome software support. While this may
have sufficed in the past when page remappings were used relatively
infrequently, they are problematic for heterogeneous memories where
page remapping is more frequent. Consequently, we believe that there
is a need to architect better support for translation coherence. In
order to understand what this support should constitute, we list three
attributes desirable for translation coherence.


1 Precise
  invalidation: Processors use several hardware translation
structures – TLBs, MMU caches <cit.>, and nested TLBs (nTLBs) <cit.>
– to cache portions of the page table(s). Ideally, translation
coherence should invalidate the translation structure entries
corresponding to remapped pages, rather than flushing all the contents
of these structures.


2 Precise target
  identification: The CPU running privileged code that remaps a page
is known as the initiator. An ideal translation coherence
protocol would allow the initiator to identify and alert only CPUs
whose TLBs, MMU caches, and nTLBs actually cache the remapped page's
translation. By restricting coherence messages to only these targets, other CPUs remain unperturbed by coherence activity.


3 Lightweight
  target-side handling: Target CPUs should invalidate their
translation structures and relay acknowledgment responses to the
initiator quickly, without excessively interfering with workloads
executing on the target CPUs.


 Unfortunately, translation coherence meets none of these
goals today. Consider, for example, changes to the nested page
table. Further, consider 1; when hypervisors
change a nested page table entry, they track guest physical and system
physical page numbers, but not the guest virtual page. Unfortunately,
as we describe in Sec. <ref>, translation structures on
architectures like x86-64 permit invalidation of individual entries
only if their guest virtual page is known. Consequently, hypervisors
completely flush all translation structures, even when only a single
page is remapped. This degrades performance since virtualized systems
need expensive two-dimensional page table walks to re-populate the
flushed structures <cit.>.

Current translation coherence protocols also fail to achieve
2. Hypervisors track the subset of CPUs that a
guest VM runs on but cannot (easily) identify the CPUs used by a
process within the VM. Therefore, when the hypervisor remaps a page,
it conservatively initiates coherence activities on all CPUs that may
potentially have executed any process in the guest VM. While
this does spare CPUs that never execute the VM, it needlessly flushes
translation structures on CPUs that execute the VM but not the
process.

Finally, 3 is also not met. Initiators currently
use expensive inter-processor interrupts (on x86) or tlbi
instructions (on ARM, Power) to prompt VM exits on all target
CPUs. Translation structures are flushed on a VM re-entry. VM exits
are particularly detrimental to performance, interrupting the
execution of target-side applications <cit.>.

We believe that the solution to these problems is to implement
translation coherence in hardware. This view is inspired by prior work
on UNITD <cit.>, which showcased the potential
of hardware translation coherence. Unfortunately, UNITD is
energy inefficient and, like other recent proposals <cit.>, cannot support virtualized systems. In response,
we propose  or , a hardware mechanism to tackle these problems and
meet 1-3. HATRIC
extends translation structure entries with coherence tags (or co-tags)
storing the system physical address where the translation entry
resides (not to be confused with the physical address stored in the
page table). This solves 1, since translation
structures can now be identified by the hypervisor without
knowledge of the guest virtual address. HATRIC exposes co-tags
to the underlying cache coherence protocol, achieving
2 and 3.

We evaluate HATRIC for a forward-looking virtualized system with
a high-bandwidth die-stacked memory and a slower off-chip memory. HATRIC drastically reduces translation coherence overheads,
improving performance by 30%, saving as much as 10% of energy, while
adding less than 2% of CPU area. Overall, our contributions are:





  * We perform a characterization study to quantify the overheads of
  translation coherence on hypervisor-man­aged die-stacked
  memory. While we focus on KVM in this paper, we have also studied
  Xen and quantified its overheads.




  * We design HATRIC to subsume translation coherence in
  hardware by piggybacking on, without fundamentally changing,
  existing cache coherence protocols. HATRIC goes beyond UNITD <cit.> by a
  accommodating translation coherence for both bare-metal and
  virtualized scenarios; b extending coherence to
  not just TLBs, but also MMU caches and nTLBs; c
  and achieving better energy efficiency.




  * We perform several studies that illustrate the benefits of HATRIC's design decisions. Further, we discuss HATRIC's
  advantages over purely software approaches to mitigate translation
  coherence issues.


 

 Overall, HATRIC is efficient and versatile. While
we mostly focus on the particularly arduous challenges of translation
coherence due to nested page table changes, HATRIC is applicable
to guest page tables and non-virtualized systems.





To achieve this goal, we must architect mechanisms that are efficient
and general. In other words, we must improve not only
OS-initiated page remappings, but also hypervisor-initated remappings
in virtualized systems. Unfortunately, we find that translation
coherence performs particularly poorly on virtualized systems,
consuming as much as 30% of system runtime, and remains largely
ignored by prior work <cit.>. The key
culprit is virtualization's use of multiple page tables. Specifically,
architectures with hardware assists for virtualization like Intel VT-x
and AMD-V – generally preferred over other approaches (see
Sec. <ref>) – use a guest page table to map guest virtual
pages to guest physical pages, and a nested page table to map guest
physical pages to system physical pages. Changes to either page table
require expensive software coherence. Alarmingly, translation
coherence for nested page tables is particularly expensive. To
understand why, we list three attributes desirable for translation
coherence.



 Translation coherence for nested page tables meets none
of these goals. Consider 1; when hypervisors
change a nested page table entry, they track guest physical and system
physical page numbers, but not the guest virtual page. Unfortunately,
for reasons detailed in Sec. <ref>, translation structures
permit invalidation of select entries only if their guest virtual page
is known. As a result, hypervisors flush all the contents of all
translation structures, even when only a single page is remapped. This
degrades performance since virtualized systems suffer expensive
two-dimensional page table walks to re-populate the flushed structures
<cit.>.

Current translation coherence protocols also fail to achieve
2. Hypervisors track the subset of CPUs that a
guest VM runs on but cannot (easily) identify the CPUs that a process
within the VM runs on. Therefore, when the hypervisor remaps a page,
it conservatively initiates coherence activities on all CPUs that may
potentially have executed any process in the guest VM. This
needlessly flushes translation structures on more CPUs than necessary.

Finally, 3 is also not met. Initiators currently
use expensive inter-processor interrupts (on x86) or tlbi
instructions (on ARM, Power) to prompt VM exits on all target
CPUs. Translation structures are flushed on a VM re-entry. VM exits
are particularly detrimental to performance, interrupting the
execution of target-side applications <cit.>.

In response, we propose  or , a low-overhead
hardware mechanism that meets 1-3. HATRIC extends translation
structure entries with coherence tags (or co-tags) storing the system
physical address where the translation entry resides (not to be
confused with the physical address stored in the page table). This
solves 1, since translation structures can now be
identified by the hypervisor without knowledge of the guest
virtual address. Further, HATRIC exposes co-tags to the
underlying cache coherence protocol, achieving 2 and 3.

We evaluate HATRIC for a forward-looking virtualized system with
a high-bandwidth die-stacked memory and a slower off-chip memory. To
the best of our knowledge, we are the first to study how hypervisors
manage such a memory hierarchy. We show that HATRIC eliminates
most of the overheads of translation coherence, improving performance
by almost 30%, saving as much as 10% of system energy, while adding
less than 2% of CPU area. Overall, our contributions are:





  * We perform a characterization study to quantify the overheads of
  translation coherence on hypervisor-managed die-stacked
  memory. While we focus on KVM in this paper, we have also studied
  Xen and find that overheads remain similar.




  * We design HATRIC to subsume translation coherence in
  hardware by piggybacking on, without fundamentally changing,
  existing cache coherence protocols. While we are partly inspired by
  prior work on UNITD <cit.>, HATRIC goes beyond, by a accommodating
  translation coherence for both bare-metal and virtualized
  scenarios; b achieving better energy
  efficiency; c and extending coherence to not
  just TLBs, but also MMU caches and nTLBs.

 

 Overall, HATRIC is efficient and versatile. While we
mostly focus on the challenges of translation coherence due to nested
page table changes, HATRIC is equally applicable to guest page
table coherence, as well as non-virtualized coherence.





§ BACKGROUND

We begin by presenting an overview of the key hardware and software
structures involved in page remapping. Our discussion focuses on
x86-64 systems. Other architectures are broadly similar but differ in
some low-level details.



 §.§ HW and SW Support for Virtualization


Virtualized systems accomplish virtual-to-physical address translation
in one of two ways. Traditionally, hypervisors have used shadow page
tables to map guest virtual pages (GVPs) to system physical pages
(SPPs), keeping them synchronized with guest OS page tables
<cit.>. However, the overheads of page table
synchronization can often be high <cit.>. As a result,
most modern systems now use two dimensional page tables
instead. Figure <ref> illustrates
two-dimensi­o­nal page table walks (see past work for more details
<cit.>). Guest page tables
map GVPs to guest physical pages (GPPs). Nested page tables map GPPs
to SPPs. x86-64 systems use 4-level forward mapped radix trees for
both page tables <cit.>. We refer to these as levels 4 (the root level) to
1 (the leaf level) as per recent work <cit.>. When a process running in a
guest VM makes a memory reference, its GVP must be translated to an
SPP. Consequently, the guest CR3 register is combined with the
requested GVP (not shown in the picture) to deduce the GPP of level 4
of the guest page table (shown as GPP Req.). However, to look up
the guest page table (gL4-gL1), the GPP must be converted into
the SPP where the page table actually resides. Therefore, we first use
the GPP to look up the nested page tables (nL4-nL1), to find SPP
gL4. Looking up gL4 then yields the GPP of the next guest
page table level (gL3). The rest of the page table walk proceeds
similarly, requiring 24 memory references in total. This presents a
performance problem as the number of references is significantly more
than the 4 references needed for non-virtualized systems. Further, the
references are entirely sequential. CPUs use three types of
translation structures to accelerate this walk:




a Private per-CPU TLBs cache
the requested GVP to SPP mappings, short-circuiting the entire
walk. TLB misses trigger hardware page table walkers to look up the
page table.


b Private per-CPU MMU caches
store intermediate page table information to accelerate parts of the
page table walk <cit.>. There are two flavors of MMU cache. The first is a
page walk cache and is implemented in AMD chips
<cit.>. Figure
<ref> shows the information cached in page
walk caches. Page walk caches are looked up with GPPs and provide SPPs
where page tables are stored. The second is called a paging
  structure cache and is implemented by Intel <cit.>. Paging structure caches are looked up with GVPs
and provide the SPPs of page table locations. Paging structure caches
generally perform better, so we focus mostly on them
<cit.>.


c Private per-CPU nTLBs
short-circuit nested page table lookups by caching GPP to SPP
translations <cit.>. Figure
<ref> shows the information cached by nTLBs.


 Concomitantly, CPUs cache page table information in
private L1 (L2, etc.) caches and the shared last-level cache
(LLC). The presence of separate private translation caches poses
coherence problems. While standard cache coherence protocols ensure
that page table entries in private L1 caches are coherent, there are
no such guarantees for TLBs, MMU caches, and nTLBs. Instead,
privileged software keeps translation structures coherent with data
caches and one another.



 §.§ Page Remapping in Virtualized Systems


We now detail the ways in which a virtualized system can trigger
coherence activity in translation structures. All page remappings can
be classified by the data they move, and the software agent initiating
the move.


Remapped data: Systems may remap a page
storing (i) the guest page table; (ii) the nested page table; or (iii)
non-page table data. Most remappings are from (iii) as they constitute
most memory pages. We have found that less than 1% of page remappings
correspond to (i)-(ii). We therefore highlight HATRIC's
operation using (iii); nevertheless, HATRIC also implicitly
supports the first two cases.


Remapping initiator: Pages can be remapped
by (i) a guest OS; or (ii) the hypervisor. When a guest OS remaps a
page, the guest page table changes. Past work achieves low-overhe­ad
guest page table coherence with relatively low-complexity software
extensions <cit.>. Unfortunately, there are no such
workarounds to mitigate the translation coherence overheads of
hypervisor-initiated nested page table remappings. For these reasons,
cross-VM memory deduplication <cit.> and
page migration between NUMA memories on multi-socket systems
<cit.> are known to be
expensive. In the past, such overheads may have been mitigated by
using these optimizations sparingly. However, nested page table
remappings become frequent with heterogeneous memories, making
hypervisor-initiated translation coherence problematic.



§ SHORTCOMINGS OF CURRENT TRANSLATION COHERENCE MECHANISMS


Our goal is to ensure that translation coherence does not impede the
adoption of heterogeneous memories. We study forward-looking
die-stacked DRAM as an example of an important heterogeneous memory
system. Die-stacked memory uses DRAM stacks that are tightly
integrated with the processor die using high-bandwidth links like
through-silicon vias, or silicon interposers <cit.>.  Die-stacked memory is expected to be useful for
multi-tenant and rack-scale computing where memory bandwidth is often
a performance bottleneck, and will require a combination of
application, guest OS, and hypervisor management <cit.>. We take the first steps
towards this, by showing the problems posed by translation coherence
on hypervisor management.



 §.§ Translation Coherence Overheads


We quantify translation coherence overheads on a die-stacked system
that is virtualized with KVM. We modify KVM to page between the
die-stacked and off-chip DRAM. Since ours is the first work to
consider hypervisor management of die-stacked memory, we implement a
variety of paging policies. Rather than focusing on developing a
single “best” policy, our objective is to show that current
translation coherence overheads are so high that they curtail the
effectiveness of practically any paging policy.

Our paging mechanisms extend prior work that explores basic
software-guided die-stacked DRAM paging <cit.>. When off-chip
DRAM data is accessed, there is a page fault. KVM then migrates the
desired page into an available die-stacked DRAM physical page
frame. The GVP and GPP remain unchanged, but KVM changes the SPP and
hence, its nested page table entry. This triggers translation
coherence.

We run our modified KVM on the detailed cycle-accurate simulator
described in Sec. <ref>. Like prior work <cit.>,
we model a system with 2GB of die-stacked DRAM with 4× the
memory bandwidth of a slower off-chip 8GB DRAM. This is a total of
10GB of addressable DRAM. Further, we model 16 CPUs based on Intel's
Haswell architecture.



Figure <ref> quantifies the performance of
hypervisor-manag­ed die-stacked DRAM, and translation coherence's
impact on it. We normalize all performance numbers to the runtime of a
system with only off-chip DRAM and no high-bandwidth die-stacked DRAM
(no-hbm). Further, we show an unachievable best-case scenario
where all data fits in an infinite-sized die-stacked memory (inf-hbm). After profiling several paging strategies (evaluated in
detail in Sec. <ref>), we plot the best-performing ones with
the curr-best bars. These results assume cumbersome software
translation coherence mechanisms. In contrast, the achievable
bars represent the potential performance of the best paging policies
with zero-overhead (and hence ideal) translation coherence.

Figure <ref> shows that unachievable infinite
die-stacked DR­AM can improve performance by 25-75% (inf-hbm
versus no-hbm). Unfortunately, the current “best” paging
policies we achieve in KVM (curr-best) fall far short of the
ideal inf-hbm case. Translation coherence overheads are a big
culprit – when these overheads are eliminated in achievable,
system performance comes within 3-10% of the case with infinite
die-stacked DRAM capacity (inf-hbm). In fact, Figure
<ref> shows that translation coherence overheads can
be so high that they can prompt die-stacked DRAM to counterintuitvely
worsen performance. For example, data caching and tunkrank actually suffer 23% and 10% performance degradations in
curr-best, respectively, despite using high-bandwi­dth
die-stacked memory. Though omitted to save space, we have also
profiled the Xen hypervisors and found similar trends (presented in
Sec. <ref>). Overall, translation coherence overheads threaten
the use of die-stacked, and indeed any heterogeneous, memory.


We modify KVM to support paging between die-stacked and off-chip
DRAM. We design and evaluate several paging policies using the
real-system infrastructure of Sec. <ref>. Our
system takes an existing multi-socket NUMA system, and through the
introduction of memory contention, makes it behave like an
architecture with 2GB of die-stacked DRAM with 4× the memory
bandwidth of a slower off-chip 8GB DRAM, for a total of 10GB of
addressable DRAM. We use 16 Intel Sandybridge CPUs (though we also
evaluate the impact of CPU counts in Sec. <ref>).

We modify KVM to remap pages in the two-level memory, mirroring prior
work on software-guided (rather than hypervisor-guided) die-stacked
DRAM paging <cit.>. When off-chip DRAM data is accessed,
there is a page fault. KVM then migrates the desired page into an
available die-stacked DRAM physicala page frame. Therefore, the GVP
and GPP remain unchanged, but KVM changes the SPP and hence, its
nested page table entry. This triggers translation coherence. We study
several paging policies (detailed in Secs. <ref>
and <ref>), but rather than focusing on invidual ones, we show
that translation coherence comprehensively hampers them all.

Figure <ref> quantifies the performance of die-stacked
DRAM paging and translation coherence. We compare runtime with only
off-chip DRAM (slow) and when the entire workload fits in the
die-stacked memory (fast) by making the die-stacked memory as
big as needed. We also show the runtime of KVM's best-performing
paging strategy, with software translation coherence overheads (sw) and shows the benefits that could be achieved if translation
coherence were free (ideal).

Figure <ref> shows that die-stacked DRAM has potential
for signficant performance improvements (i.e., see fast) but we
are nowhere close to achieving them (i.e., see sw). Translation
coherence is a big culprit; when its overheads are eliminated in ideal, runtimes drop within 1% of fast. In fact, canneal, graph500, and facesim see 10-15% performance
improvements over sw. Other workloads (e.g., data caching
and tunkrank) actually experience performance degradations
with only software managed translation coherence. For example, data caching gets 23% slower with sw, despite having 2GB of
high-bandwidth stacked DRAM. With (ideal) however, performance
improves by 39%. In a nutshell, translation coherence overheads
threaten the use of die-stacked (and indeed any heterogeneous) DRAM.




 §.§ Page Remapping Anatomy




We now shed light on the sources of overheads from translation
coherence. While we use page migration between off-chip and
die-stacked DRAM as our driving example, the same mechanisms are used
today to migrate pages between NUMA memories, or to defragment memory,
etc.

When a VM is configured, KVM assigns it virtual CPU threads or
vCPUs. Figure <ref> assumes 3 vCPUs executing on physical
CPUs. Suppose vCPU 0 frequently demands data in GVP 3, which maps to
GPP 8 and SPP 5, and that SPP 5 resides in off-chip DRAM. The
hypervisor may want to migrate SPP 5 to die-stacked memory (e.g., SPP
512) to improve performance. On a VM exit (assumed to have occurred
prior in time to Figure <ref>), the hypervisor modifies the
nested page table to update the SPP, triggering translation
coherence. There are three problems with this:


All vCPUs are identified as targets: Figure
<ref> shows that the hypervisor initiates translation
coherence by setting the TLB flush request bit in every vCPU's kvm_vcpu structure. kvm_vcpu stores vCPU state; when a vCPU
is scheduled on a physical CPU, it provides register content,
instruction pointers, etc. By setting these bits, the hypervisor
signals that TLB, MMU cache, and nTLB entries need to be flushed.

Ideally, we would like the hypervisor to identify only the CPUs that
actually cache the stale translation as targets. The hypervisor does
spare physical CPUs that never executed the VM. However, it flushes
all physical CPUs that ran any of the vCPUs of the VM, regardless of
whether they cache the modified page table entries. 





One might consider (similar to Linux) tracking the subset of physical
 Naturally, this may be
conservative since the translations may have been evicted from the
TLBs, etc. Unfortunately, however, hypervisors are unable to achieve
even this type of coarse-grained target identification. In a nutshell,
hypervisors (in full- rather than para-virtualized scenarios
<cit.>) cannot easily identify the subset of vCPUs
and physical CPUs that individual processes have executed on. Instead,
they conservatively identify all vCPUs as targets.



All vCPUs suffer VM exits: In the next
step, the hypervisor launches inter-processor interrupts (IPIs) to all
the vCPUs. IPIs use the processor's advanced programmable interrupt
controllers (APICs). APIC implementations vary; depending on the APIC
technology, KVM converts broadcast IPIs into a loop of individual
IPIs, or a loop across processor clusters. We have profiled the
overheads of IPIs using microbenchmarks on Haswell systems, and like
past work <cit.>, find that they are
expensive, consuming thousands of clock cycles. If the receiving CPUs
are running vCPUs, they suffer VM exits, compromising
3 from Sec. <ref>. Targets then
acknowledge the initiator, which is paused waiting for all vCPUs to
respond.


All translation structures are flushed: The
next step is to invalidate stale mappings in translation structure
entries. Current architectures provide ISA and microarchitectural
support for this via, for example, invlpg instructions in x86,
etc. There are two caveats however. First, these instructions need the
GVP of the modified nested page table mapping to identify the TLB
entries that need to be invalidated. This is largely because modern
TLBs maintain GVP bits in the tag. While this is a good design choice
for non-virtualized systems, it is problematic for virtualized systems
because hypervisors do not have easy access to GVPs. Instead, they
have GPPs and SPPs. Consequently, KVM, Xen, etc., flush all TLB
contents when they modify a nested page table entry, rather than
selectively invalidating TLB entries. Second, there are currently no
instructions to selectively invalidate MMU caches or nTLBs, even
though they are tagged with GPPs and SPPs. The is because the marginal
benefits of adding ISA support for selective MMU cache and nTLB
invalidation are limited when the more performance-critical TLBs are
flushed.


One might consider solving this problem by re-designing the
guest-hypervisor interface. One possibility might be to create a
communication channel for the guest OS to pass information about GVP
changes to the hypervisor and guarantee synchronization of this
information between the guest and hypervisor. Unfortunately,
synchronizing on every guest page fault, address space switch, etc.,
is expensive, and re-introduces problems similar to those with shadow
paging <cit.>. In an alternative approach, we may
create a communication channel for the hypervisor to query GVP
information from the guest. However, the guest OS must not change GVPs
while the hypervisor uses it, introducing design complexity and
constraining guest OS operation. Overall, while software solutions
might be possible, they require complex changes to existing
guest-hypervisor interfaces.




 §.§ Hardware Versus Software Solutions


It is natural to ask whether translation coherence problems can be
solved with smarter software. We have studied this possibility and
have concluded that hardware solutions are superior. Fundamentally,
software solutions only partially solve the problem of flushing all
translation structures, and cannot solve the problem of identifying
all vCPUs as translation coherence targets and prompting VM exits.

Consider the problem of flushing all translation structures. One might
consider tackling this problem by modifying the guest-hypervisor
interface to enable the hypervisor to use existing ISA support (e.g.,
invlpg instructions) to selectively invalidate TLB entries. But
this only fixes TLB invalidation – no architectures today maintain
selective invalidation instructions for MMU caches and nTLBs, so these
would still have to be flushed.

Even if this problem could be solved, making target-side translation
coherence handling lightweight is challenging. Fundamentally, handling
translation coherence in software means that a context switch of the
CPUs is unavoidable. One alternative to expensive VM exits might be to
switch to lighterweight interrupts to query the guest OS for GVP-SPP
mappings. Unfortunately, even these interrupts remain
expensive. Specifically, we profiled interrupt costs using
microbe­nchmarks on Intel's Haswell machines and found that they
require 640 cycles on average, which is just half of the average of
1300 cycles required for a VM exit. HATRIC, however, entirely
eliminates these costs by never disrupting the operation of the
guest OS or requiring context switching.


Then, consider the problem of imprecise target identification. One
potential workaround might be to use the hypervisor's reverse mappings
to identify which virtual machines map a modified system physical
page. Unfortunately, the reverse mapping does actually maintain
information about which CPUs have actually cached the translation
mappings. In the absence of this information, the hypervisor has to
continue conservatively identifying all VM CPUs as targets. 



 §.§ Summary of Observations


In summary, software translation coherence a has
high overheads that jeapordize the benefits of die-stacked DRAM;
b requires comprehensive solutions that attack
the problems of translation structure flushing, imprecise target
identification, and VM exits. Further, we show (in Sec. <ref>)
that c translation coherence worsens as VMs are
assigned more vCPUs; and d because a process'
page remapping triggers coherence activity on all vCPUs of the VM,
co-running processes within the VM (with disjoint address spaces that)
needlessly suffer from translation coherence.





















§ MOTIVATION: DIE-STACKED DRAM


Virtualized page remapping suffers poor performance, jeapordizing the
benefits of memory defragmentation (to create superpages), memory
deduplication (with copy-on-writes), etc. Even worse, page remapping
is fundamental to emerging memory architectures with die-stacked
memory (e.g., Intel's 3D XPoint memory <cit.>, Micron's
Hybrid Memory Cube <cit.>, and AMD/Hynix's High-Bandwidth
Memory <cit.>), and byte-addressable non-volatile memories
<cit.>. We study translation
coherence in the context of die-stacked DRAM as representative of the
issues that arise more generally for heterogeneous memories.

Die-stacked memory tightly integrates DRAM stacks with the processor
die, using high-bandwidth links like through-silicon vias, or silicon
interposers <cit.>. Experts generally
believe that die-stacked DRAM will be managed by a combination of
microarchitectural innovations, and OS policies (possibly with
application-level guidance) <cit.>.

We perform the first studies on hypervisor-managed die-stacked DRAM,
going beyond past work on software-managed stacked DRAM
<cit.>. Die-stacked memory is expected to be useful for
bandwidth constrained multi-tenant and rack-scale computing
<cit.> and will likely require a
combination of application, guest OS, and hypervisor management. We
take the first steps towards achieving such a management stack, by
showing the problems posed by translation coherence on hypervisor
management.




 Die-stacked DRAM paging performance:
Figure <ref> quantifies the performance of die-stacked
DRAM paging. We use the real-system emulation framework described in
Sec. <ref> and model 2GB of die-stacked memory
and 8GB of off-chip memory, totallying 10GB of DRAM. This is
consistent with industry projections, where die-stacked memories are
expected to comprise 20% of total memory <cit.>. Like past
work <cit.>, we model a bandwidth differential of 4×
between die-stacked and off-chip DRAM. We use 16 Intel Xeon Haswell
cores (though Sec. <ref> studies the impact of core counts).

Figure <ref> compares runtime with only off-chip DRAM
(slow) and when the entire workload fits in the die-stacked
memory (fast) by artificially making the die-stacked memory as
big as needed. Die-stacked DRAM is potentially useful for these
workloads – if the die-stacked DRAM services all the memory
references (fast), runtime can be reduced to 30-40% of the
off-chip (slow) baseline. Our goal is to use finite-capacity
die-stacked DRAM to approach the fast results.

We modify KVM to support paging between die-stacked and off-chip
DRAM. Like prior work on software-managed die-stacked DRAM
<cit.>, we modify KVM to page fault on access to off-chip
DRAM pages. Faults migrate the desired page into an available
die-stacked DRAM physical page frame. The GVP and GPP remain
unchanged; however, the hypervisor changes the SPP and hence, the
nested page table. This triggers translation coherence.

To accommodate incoming pages from off-chip DRAM, the hypervisor must
employ a page replacement policy to choose what to evict from
die-stacked DRAM. We have studied several page replacement policies
(detailed in Sec. <ref>) but ultimately adopt
Linux's classic CLOCK algorithm <cit.> for pseudo-LRU
replacement, as this generally performs best. We have also studied
optimizations such as prefetching pages from off-chip DRAM, etc. We
detail these studies in Sec. <ref>, but for now,
showcase the problems with translation coherence for the
best-performing paging policy. Figure <ref> quantifies
the performance of this policy with the actual bars. The (ideal) bars further add zero-overhead (and hence unachieveable)
translation coherence to actual.

Figure <ref> shows that translation coherence degrades
performance. For example, canneal, graph500, and facesim see 10-15% performance improvements if translation
coherence overheads are entirely eliminated, achieving close to the
performance of fast. Moreover, some workloads (e.g., data
  caching and tunkrank) actually experience performance degradations with die-stacking because of translation coherence
overheads. For example, data caching gets 23% slower with actual, despite having 2GB of high-bandwidth stacked DRAM. But when
translation coherence overheads are removed (ideal), the
performance improves by 39%. In a nutshell, translation coherence
overheads are a performance bottleneck that threaten the very use of
die-stacked (and indeed any heterogeneous) DRAM.




 Translation coherence component
  overheads: Figure <ref> shows how we can
attack translation coherence overheads. We first plot, as a fraction
of the total benefits of zero-overhead translation coherence, the
benefits of selective invalidation of translation structures (prec-inv or 1 from
Sec. <ref>). We then add precise target identification
(prec-targ or 2 from
Sec. <ref>), and lightweight target-side handling (no-VM-exit or 3 from
Sec. <ref>). Translation coherence can be improved by
attacking all three problems. Workloads like canneal and
  graph500 especially need precise translation structure invalidation
as they have pseudo-random memory access patterns. This means that
repopulating flushed structures with two-dimensional page table walks
(which suffer cache misses) is expensive. Workloads like tunkrank and facesim benefit from eliminating VM exits. This
is partly because VM exits worsen shared lock contention among
parallel threads, when vCPUs holding locks take particularly long
resume.


 Summary: Overall, Figures
<ref>-<ref> show that
a translation coherence overheads hamper state of
the art page replacement (e.g., Linux's CLOCK LRU); and
b require comprehensive solutions that attack the
problems of translation structure flushing, imprecise target
identification, and VM exits. Further, we show (in Sec. <ref>)
that c translation coherence worsens as VMs are
assigned more vCPUs and are scheduled on more physical CPUs; and
d page remappings from any individual process
hurts all processes in a VM.





§ HARDWARE DESIGN


We now detail HATRIC's design, focusing mostly on
hyp­ervisor-initiated paging which modifies the nested page
table. HATRIC achieves all three goals set out in
Sec. <ref>. It does so by adding co-tags to translation
structures to achieve precise invalidation. It then exposes these
co-tags to the cache coherence protocol to precisely identify
coherence targets and to eliminate VM exits.




 §.§ Co-Tags





We describe co-tags by discussing what they are, what they accomplish,
how they are designed, and who sets them.


What are co-tags? Consider the page tables
of Figure <ref> and suppose that the hypervisor
modifies the GPP 2-SPP 2 nested page table mapping, making the TLB entry
caching information about SPP 2 stale. Since the TLB caches GVP-SPP
mappings rather than GPP-SPP mappings, this means that we'd like to
selectively invalidate GVP 1-SPP 2 from the TLB, and although not
shown, corresponding MMU cache and nTLB entries. Co-tags allow us to
do this by acting as tag extensions that allow precise identification
of translations when the hypervisor does not know the GVP. Co-tags
store the system physical address of the nested page table entry (nL1 from the bottom-most row in Figure
<ref>). For example, GVP 1-SPP 2 uses the
nested page table entry at system physical address 0x100c, which
is stored in the co-tag.


What do co-tags accomplish?  Co-tags not
only permit precise translation information identification but can
also be piggybacked on existing cache coherence protocols.  When the
hypervisor modifies a nested page table translation, cache coherence
protocols detect the modification to the system physical address of
the page table entry. Ordinarily, all private caches respond so that
only one amongst them holds the up-to-date copy of the cache line
storing the nested page table entry. With co-tags, HATRIC
extends cache coherence as follows. Coherence messages, previously
restricted to just private caches, are now also relayed to translation
structures. Co-tags are used to identify which (if any) TLB, MMU
cache, and nTLB entries correspond to the modified nested page table
cache line. Overall, this means that co-tags: a
pick up on nested page table changes entirely in hardware, without the
need for IPIs, VM exits, or invlpg instructions;
b rely on, without fundamentally changing,
existing cache coherence protocols; c permit
selective TLBs, MMU caches, and nTLBs rather than flushes.


How are co-tags implemented? Co-tags have
one important drawback. System physical addresses on 64-bit systems
require 8 bytes. If all 8 bytes are realized in the co-tag, each TLB
entry doubles in size. MMU cache and nTLB entries triple in
size. Since address translation can account for 13-15% of processor
energy <cit.>, these area and associated energy
overheads are unacceptable.

Therefore, we decrease the resolution of co-tags, using fewer
bits. This means that groups, rather than individual TLB entries may
be invalidated when one nested page table entry is changed. However,
judiciously-sized co-tags generally achieve a good balance between
invalidation precision, and area/energy overheads. Sec. <ref>
shows, using detailed RTL modeling, that 2-byte co-tags (a per-core
area overhead of 2%) strike a good balance. We specify the exact
subset of address bits make up the co-tag in subsequent sections.


Who sets co-tags? For good performance,
co-tags must be set by hardware without an OS or hypervisor
interrupt. HATRIC uses the page table walker to do this. On TLB,
MMU cache, and nTLB misses, the page table walker performs a
two-dimensional page table walk. In so doing, it infers the system
physical address of the page table entries and stores it in the TLB,
MMU cache, and nTLB co-tags.


When hypervisors change the nested page table to remap a page, they
have three pieces of information: (i) the GPP of the translation
entry; (ii) the SPP in the translation entry; and (iii) the SPP where
the translation entry is stored. Consider Figure <ref>, which
shows a guest OS-managed page table, a hypervisor-managed nested page
table and TLB hardware (hardware MMU caches and nTLBs are not
shown). The hypervisor knows that GPP0 maps to SPP0, and that this
translation is located in system memory address 0x1000. Since this
translation is being changed, the corresponding stale TLB entry must
be invalidated. The tags with which the TLBs may be looked up though,
are GVPs, which hypervisors in fully-virtualized scenarios cannot
easily extract.

Figure <ref> shows that we add co-tags (shown in green boxes)
to each TLB entry. Co-tags are bits that can be used to look up the
TLB, and hence act as tag extensions. We use co-tags to record the
system physical address storing the nested page table's translation
entry. For example, GVP->SPP0 uses address 0x1008 for its nested
translation; we therefore store 0x1008 in the co-tag. Similarly, we
add co-tags to MMU cache and nTLB entries.

Co-tags serve two goals. First, they allow the hypervisor to uniquely
identify translation structure entries with information they have
available, the system physical address of the nested page table entry
they are changing. Second, by recording system physical addresses,
co-tags can enables TLB coherence to bootstrap off standard cache
coherence protocols (which also operate on system physical addresses).

Co-tags have one important drawback. System physical addresses can be
up to 64 bits; recording full addresses can therefore double the size
of 8-byte TLB entries (and similarly enlarge MMU cache and nTLB
entries). This is a big area and energy overhead. Since address
translation can account for 13-15% of processor energy
<cit.>, this is unacceptable.

We address this problem by decreasing the resolution of co-tags, using
only a subset of the bits. This does mean that TLB entries cannot be
uniquely identified anymore and groups of TLB entries may need to be
invalidated when one nested page table entry is changed. However,
judiciously-sized co-tags generally achieve a good balance between
invalidation precision, and area/energy overheads. Sec. <ref>
shows, using detailed RTL modeling, that 2-byte co-tags in all the
translation structures (a per-core area overhead of 2%) strikes the
best balance. We defer a discussion of which exact subset of address
bits make up the co-tag to the following discussion on how co-tags
interface with the cache coherence protocol.




 §.§ Integration with Cache Coherence
 

Modern cache coherence protocols can integrate not only readable and
writable private caches, but also read-only instruction caches (though
instruction caches do not have to be read-only). Since TLBs, MMU
caches, and nested TLBs are fundamentally read-only structures, HATRIC integrates them into the existing cache coherence protocol
in a manner similar to read-only instruction caches. Beyond this, HATRIC has minimal impact on the cache coherence protocol. We
describe HATRIC's operation on a directory-based MESI protocol,
with the coherence directories located at the shared LLC cache
banks. Without loss of generality, we use dual-grain coherence
directories from recent work <cit.>.


Translation structure coherence states:
Since translation structures are read-only, their entries require only
two coherence states: Shared (S), and Invalid (I). These two states
may be realized using per-entry valid bits. When a translation
is entered into the TLB, MMU cache, or nTLB, the valid bit is
set, representing the S state; the translation can be accessed by the
local CPU. The translation structure entry remains in this state until
it receives a coherence message. Co-tags are compared to incoming
messages; when an invalidation request matches the co-tag, the
translation entry is invalidated.


Translation coherence initiators: Consider
Figure <ref>. Before detailing the numbered transactions,
let us consider HATRIC's components. We show a 4-CPU system,
with private L1 caches, 4 shared LLC banks, and per-bank coherence
directories. We show TLBs and though they also exist, we omit MMU
caches and nTLBs to save space. MMU caches and nTLBs interact with the
cache coherence protocol in a manner that mirrors TLBs. We show 8
cached page table entries, represented as green and black boxes.
Translation coherence is initiated by the hardware page table walker
or OS/hypervisor software.




Page table walkers: These are hardware
finite state machines that are invoked on TLB misses. Walkers traverse
the page tables and are responsible for filling translation
information into the translation structures and setting the
co-tags. Walkers cannot map or unmap pages.


OS and hypervisor: These can traverse,
map, and unmap page table entries using standard load/store
instructions. HATRIC picks up these changes, and keeps all
private cache and translation structures coherent.


Coherence directory: HATRIC minimally
changes the coherence directory. Key design considerations are:


 Directory entry changes: Figure
<ref> shows that the coherence directory tracks non-page
table and page table cache lines. We make a minor change to directory
entries, adding two bits to record whether cache lines belong to a
guest page table (gPT) or nested page table (nPT). HATRIC uses these bits to identify the case when a line holding
page table data is modified in the private caches. When this happens,
coherence transactions need to be sent to the translation structures.

The nPT and gPT bits are set by the hardware page table
walkers on fills to the TLBs, MMU caches, and nTLBs. One might
initially expect this to be problematic in the case where the OS or
hypervisor reads or writes a page table cache line in software. In
reality however, this does not present correctness issues. Two
situations are possible. In the first situation, the page table walker
has previously accessed the cache line, and has already set the nPT or gPT bit in the cache line's directory entry. There are
no correctness issues in this case. In the second situation, the OS or
hypervisor reads or writes a page table cache line that has previously
never been looked up by the page table walker. In this case, there is
actually no need to set the nPT or gPT bits in the
coherence directory entry yet since no translations from this line are
cached in the TLB, MMU cache, or nTLB anyway. Modifying the cache line
at this point does not require coherence messages to be sent to the
translation structures. When the page table walker does eventually
access a translation from this cache line and fills it into the
translation structures, it checks the access bit already
maintained by x86-64 translation entries. The access bit records
whether an entry has previously been filled into the TLB or accessed
by the page table walker <cit.>. If this bit is
clear, this means that the entry (and hence the cache line it resides
in) has not been accessed by the page table walker yet. In this case,
the page table walker sends a message to the coherence directory to
update the nPT and gPT bits of the relevant cache line.


Coherence granularity: Figure
<ref> shows that directory entries store information at
the cache line granularity. x86-64 systems cache 8 page table entries
per 64-byte cache line. Hence, similar to false sharing in caches
<cit.>, HATRIC conservatively invalidates all
translation structure entries caching these 8 page table entries, even
if only a single page table entry is modified. For example, consider
CPU 3 in Figure <ref>, where the TLB caches two
translations mapped to the same cache line. If any CPU modifies either
one of these translations, HATRIC has to invalidate both TLB
entries. This has implications on the size of co-tags. Recall that in
Sec. <ref>, we stated that co-tags use a subset of the address
bits. We want use the least significant, and hence, highest entropy
bits as co-tags. But since cache coherence protocols track groups of
8 translations, co-tags do not store the 3 least significant address
bits. Our 2 byte co-tags use bits 19-3 of the system physical address
storing the page table. Naturally, this means that translations from
different addresses in the page table may alias to the same co-tag. In
practice, this has little adverse affect on HATRIC's
performance.


Coherence specificity issues: To simplify
hardware, coherence directories do not track where among the private
caches, TLB, MMU cache, and nTLB the page table entries are
cach­ed. Instead, coherence directories are pseudo-specific. For example, Figure <ref> shows that
CPU 0 caches page table entries in the TLB and L1 cache, CPU 1 only
caches them in the L1 cache, while CPU 3 only caches them in the
TLB. Nevertheless, the coherence directory's sharer list does not
capture this distinction. Therefore, when a CPU modifies page table
contents and invalidation messages need to be sent to the sharers,
they are relayed to the L1 caches and all translation
structures, regardless of which ones actually cache page tables. This
results in spurious coherence activity (e.g., CPU 3's L1 cache need not
be relayed an invalidation message for any of the page table entries
shown). In practice though, because modifications of the page table
are rare compared to other coherence activity, this additional traffic
is tolerable. Ultimately, the gains from eliminating high-latency
software TLB coherence far outweigh these relatively minor overheads
(see Sec. <ref>).


Cache and translation structure evictions:
Directories track translations in a coarse-grained and pseudo-specific
manner. This has important implications on cache line
evictions. Ordinarily, when a private cache line is evicted, the
coherence directory is relayed a message to update the line's sharer
list <cit.>. An up-to-date sharer list eliminates
spurious coherence traffic to this line in the future. We continue to
employ this strategy for non-page table cache lines but use a slightly
different approach for page tables. When a cache line holding page
table entries is evicted, its content may still be cached in the TLB,
MMU cache, nTLB. Even worse, other translations with matching co-tags
may still be residing in the translation structures. One option may be
to detect all translations with matching co-tags and invalidate
them. This hurts energy because of the additional translation
structure lookups, and performance because of unnecessary TLB, MMU
cache, and nTLB entry invalidations.



Figure <ref> shows how HATRIC handles this problem,
contrasting it with traditional cache coherence. Suppose CPU 0 evicts
a cache line with page table entries. Both approaches relay a message
to the coherence directory. Ordinarily, we remove CPU 0 from the
sharer list. However, if HATRIC sees that this message
corresponds to a cache line storing a page table (by checking the
directory entry's page table bits), the sharer list is untouched.
This means that if CPU 1 subsequently writes to the same cache line,
HATRIC sends spurious invalidate messages to CPU 0, unlike
traditional cache coherence. However, we mitigate frequency of
spurious messages; when CPU 0 sees spurious coherence traffic, it
sends a message back to the directory to demote CPU 0 from the sharer
list. Sharer lists are hence lazily updated. For similar reasons,
evictions from translation structures also lazily update coherence
directory sharer lists.


Cache coherence protocols pay attention to two categories of
evictions. First, consider evictions from private caches. These
usually relay messages to the directory to update the appropriate
entry's sharer list <cit.>. HATRIC however,
changes this aspect of the protocol. Since the sharer list tells us
whether page table is cached in some combination of the CPU's
translation structures and caches, individual evictions do not
guarantee that the page table entry has been removed from all
structures. One might initially consider handling this issue by
scanning all translation structures and caches to find out whether the
evicted translation is indeed being evicted by all of them. Aside from
the fact that this consumes non-trivial energy, it requires that we
also invalidate any other translation information with the same
co-tag. Since co-tags provide a coarser tracking granularity, we find
that this degrades performance (see Sec. <ref>).

Instead, our approach is to lazily update eviction information in
coherence directory. When translation information is evicted from a
CPU's L1 cache or translation structures, we do not transmit this
information to the coherence directory. Since this makes the sharer
list stale, modifications of translation information on another core
may prompt spurious coherence messages to be relayed. HATRIC
mitigates this problem in the following way. If invalidation messages
sent to a core find no entries with matching co-tags in the
translation structures, and no entries with matching tags in the L1
cache, the core relays a message back to the coherence directory from
demotion from the sharer list. This approach generally provides good
performance (see Sec. <ref>).



Directory evictions: Finally, past work
shows that coherence directory entry evictions require
back-invalidations of the associated cache lines in the cores
<cit.>. This is necessary for correctness; all lines in
private caches must always have a directory entry. HATRIC
extends this approach to relay back-invalidations to the TLBs, MMU
caches, and nTLBs too.



 §.§ Putting It All Together


Figure <ref> details HATRIC's overall
operation. Initially, CPU 0's TLB and L1 caches are empty. On a memory
access, CPU 0 misses in the TLB and walks the page table
1. Whenever a request is satisfied from a page
table line in the L1 cache in the M, E, or S state, there is no need
to initiate coherence transactions. However, suppose that the last
memory reference in the page table walk from Figure
<ref> is absent in the L1 cache. A read
request is sent to the coherence directory in step 2.

Two scenarios are possible. In the first, the translation may be
uncached in the private caches, and there is no coherence directory
entry. A directory entry is allocated and the gPT or nPT
bit is set. In the second scenario (shown in Figure
<ref>), the request matches an existing directory
entry. The nPT bit already is set and HATRIC reads the
sharer list which identifies CPUs 1 and 3 as also caching the desired
translation (and the 7 adjacent translations in the cache line) in
shared state. In response, the cache line with the desired
translations is sent back to CPU 0 (from CPU 1, 3, or memory,
whichever is quicker), updating the L1 cache 3a and
TLB 3b. Subsequently, the sharer list adds CPU 0.

Now suppose that CPU 1 runs the hypervisor and unmaps the solid green
translation from the nested page table in step 4. To transition the L1 cache line into the M state, the cache
coherence protocol relays a message to the coherence directory. The
corresponding directory entry is identified in 5,
and we find that CPU 0 and 3 need to be sent invalidation
requests. However, the sharer list is (i) coarse-grained and (ii)
pseudo-specific. Because of (i), CPU 0 has to invalidate not only its
TLB entry 6a but also 8 translations in the L1 cache
6b, and CPU 3 has to invalidate the 2 TLB entries
with matching co-tags 6c. Because of (ii), CPU 1's L1
cache receives a spurious invalidation message 6d.



Steps 6a-6d
constitute these messages. Because page table entries are tracked at a
cache line granularity by the coherence protocol, CPU0 has to
invalidate 8 translations, as per usual 6b. HATRIC uses co-tags to go beyond traditional cache coherence to
invalidate the TLB's copy of the solid green translation too
6a. CPU3 also attempts to invalidate its copies
of the now stale translation. However, because of coarser-grained
co-tags, CPU3 has to invalidate the striped black translation in
addition to the solid green one 6c. Further, as
the sharer list does not more precisely indicate where within the
translation structures and L1 caches a page table entry resides,
CPU3's L1 cache is spuriously looked up 6d.



















 §.§ Other Key Observations


Scope: HATRIC is applicable to virtualized and
non-virtualized systems. For the latter, the co-tags may simply be
used to store the physical addresses of page tables. Further, while we
have focused on nested page table coherence, HATRIC can also be
trivially modified to support shadow page tables too
<cit.>. The co-tags merely have to store the memory
addresses where shadow page tables are stored.


Metadata updates: Beyond software changes
to the translations, they may also be changed by hardware page table
walkers. Specifically, page table walkers update dirty and access bits
to aid page replacement policies <cit.>. But since these
updates are picked up by the standard cache coherence protocol, HATRIC naturally handles these updates too.


Prefetching optimizations: Beyond simply
invalidating stale translation structure entries, HATRIC could
potentially directly update (or prefetch) the updated mappings into
the translation structures. Since a thorough treatment of these
studies requires an understanding of how to manage translation access
bits while speculatively prefetching into translation structures
<cit.>, we leave this for future work.


Coherence protocols: We have studied a MESI
directory based coherence protocol but we have also implemented HATRIC atop MOESI protocols too, as well as snooping protocols like
MESIF <cit.>. HATRIC requires no fundamental
changes to support these protocols.


Synonyms and superpages: HATRIC
naturally handles synonyms or virtual address aliases. This is because
synonyms are defined by unique translations in separate page table
locations, and hence separate system physical addresses. Therefore,
changing or removing a translation has no impact on other translations
in the synonym set, allowing HATRIC to be agnostic to
synonyms. Similarly, HATRIC supports superpages, which also
occupy unique translation entries and can hence be easily detected
by co-tags.


Multiprogrammed workloads: One might expect
that when an application's physical page is remapped, there is no need
for translation coherence activities to the other applications,
because they operate on distinct address spaces. Unfortunately,
however, hypervisors do not know which physical CPUs an application
executed on; all they know is the vCPUs and the physical the entire VM
uses. Therefore, the hypervisor conservatively flushes the even the
translation structures of CPUs that never ran the offending
application.  HATRIC completely eliminates this problem by
precisely tracking the correspondence between translations and CPUs.


Comparison to past approaches: HATRIC
is inspired by past work on UNITD <cit.>. Like
HATRIC, UNITD piggybacks translation coherence atop cache
coherence protocols. Unlike HATRIC however, UNITD cannot
support virtualized systems or MMU cache and nTLB coherence. Further,
HATRIC uses energy-frugal co-tags instead of UNI­TD's
large reverse-lookup CAM circuitry, achieving far grea­ter energy
efficiency. We showcase this in Sec. <ref> where we compare
the efficiency of HATRIC versus an enhanced UNITD design
for virtualization. Beyond UNITD, past work on DiDi
<cit.> also targets translation coherence for
non-virt­ualized systems. Similarly, recent work investigates
translation coherence overheads in the context of die-stacked DRA­M
<cit.>. While this work mitigates translation coherence
overheads, it does so specifically for non-virtualized x86
architectures, and ignores MMU caches and nTLBs. Finally, recent work
uses software mechanisms to reduce translation overheads for guest
page table modifications <cit.>, while HATRIC
also solves the problem of nested page table coherence.



§ METHODOLOGY

Our experimental methodology has two steps. First, we modify KVM to
implement paging on a two-level memory with die-stacked DRAM. Second,
we use detailed cycle-accurate simulation to assess performance and
energy.



 §.§ Die-Stacked DRAM Simulation

We evaluate HATRIC's performance on a detailed cycle-accurate
simulation framework that models the operation of a 32-CPU Haswell
processor. We assume 2GB of die-stacked DRAM with 4× the
bandwidth of slower 8GB off-chip DRA­M, similar to prior work
<cit.>. Each CPU maintains 32KB L1 caches, 256KB L2 caches,
64-entry L1 TLBs, 512-entry L2 TLBs, 32-entry nTLBs
<cit.>, and 48-entry paging structure MMU caches
<cit.>. Further, we assume a 20MB LLC.  We model the
energy usage of this system using the CACTI framework
<cit.>. We use Ubuntu 15.10 Linux as our guest
OS. Further, we evaluate HATRIC in detail using KVM. Beyond
this, we have also run Xen to highlight HATRIC's generality with
other hypervisors.

We use a trace-based approach to drive our simulation framework. We
collect instruction traces from our modified hypervisors with 50
billion memory references using a modified version of Pin which tracks
all GVPs, GPPs, and SPPs, as well as changes to the guest and nested
page tables. In order to collect accurate paging activity, we collect
these traces on a real-system. Ideally, we would like this system to
use die-stacked DRAM but since this technology is in its infancy, we
are inspired by recent work <cit.> to modify a real-system to
mimic the activity of die-stacking. We take an existing multi-socket
NUMA platform, and by introducing contention, creates two different
speeds of DRAM. We use a 2-socket Intel Xeon E5-2450 system, running
our software stack. We dedicate the first socket for execution of the
software stack and mimicry of fast or die-stacked DRAM. The second
socket mimics the slow or off-chip DRAM. It does so by running several
instances of memhog on its cores. Similar to prior work
<cit.>, we use memhog to carefully generate memory contention to achieve the
desired bandwidth differential between the fast and slow DRAM of
4×. By using Pin to track KVM and Linux paging code on this
infrastructure, we accurately generate instruction traces to test HATRIC.




 §.§ Real-System Die-Stacked DRAM Mimicry

We would like to modify KVM to study translation coherence on a real
die-stacked system. Unfortunately, die-stacked DRAM is in its infancy,
with products just beginning to ship. Instead, we take inspiration
from recent work <cit.> to create a modeling infrastructure
that takes an existing multi-socket NUMA platform, and by introducing
contention, creates two different speeds of DRAM. We use a 2-socket
Intel Xeon E5-2450 system with Sandybridge CPUs, running Ubuntu 15.10
with v4.4 kernels and the latest version of KVM. Each socket has 8
cores, hyperthreaded 2 ways (8×2 or 16 hardware
contexts). Further, each core uses 32KB L1 caches, 256KB L2 caches,
64-entry L1 TLBs, 512-entry L2 TLBs, 32-entry nTLBs
<cit.>, and 48-entry paging structure MMU cache
<cit.>. Socket use a 20MB LLC and 16GB DDR3
DRAM.

We use this multi-socket system to mimic a die-stacked memory
architecture. We dedicate the first socket for execution of the
software stack and mimicry of fast or die-stacked DRAM. The second
socket mimics the slow or off-chip DRAM. It does so by running several
instances of memhog on its cores. Similar to prior work
<cit.>, we use memhog to carefully generate
memory contention to achieve bandwidth differential between the fast
and slow DRAM of 4×. This is typical of expected die-stacked
DRAM architectures <cit.>. Overall, our system emulates an
architecture with 2GB of die-stacked DRAM, and 8GB of off-chip DRAM,
matching projections where die-stacked DRAM is expected to account for
roughly 20% of total DRAM <cit.>.



 §.§ Die-Stacked DRAM Simulation


After evaluating KVM's translation coherence overheads on long-running
workloads with full-system effects, we design an in-house simulation
framework which models a 32-core Haswell based processor, with the
cache and TLB configuration detailed in
Sec. <ref>. We collect memory traces with 50
billion memory references using a modified version of Pin which tracks
all GVPs, GPPs, and SPPs, as well as changes to the guest and nested
page tables. Like the emulator, we assume 2GB of die-stacked DRAM and
8GB off-chip slow DRAM. Furthermore, we faithfully model the
internals of KVM's paging stack.





 §.§ KVM Paging Policies


Our goal is to showcase the overheads imposed by translation coherence
on paging decisions rather than design the optimal paging policy,
leaving this for future work. So, we pick well-known paging policies
that cover a wide range of design options. For example, we have studied
FIFO and LRU replacement policies, finding the latter to perform
better, as expected. We implement LRU policies in KVM by repurposing
Linux's well-known pseudo-LRU CLOCK policy <cit.>. LRU
alone doesn't always provide good performance since it is expensive to
traverse page lists to identify good candidates for eviction from
die-stacked memory. Instead, performance is improved by moving this
operation off the critical path of execution; we therefor
pre-emptively evict pages from die-stacked memory so that a pool of
free pages are always maintained. We call this migration daemon
and combine it with LRU. We have also investigated the benefits of
page prefetching; that is, when an application demand fetches a page
from off-chip to die-stacked memory, we also prefetch a set number of
adjacent pages. Generally, we have found that the best paging policy
uses a combination of these approaches.



 §.§ Workloads


Our focus is on two sets of workloads. The first set comprises
applications that benefit from the higher bandwidth of die-stacked
memory. We use canneal and facesim from the Parsec suite
<cit.>, data caching and tunkrank from
Cloudsuite <cit.>, and graph500 as part of
this group. We also create 80 multiprogrammed combinations of
workloads from all the Spec applications to showcase the problem of
imprecise target identification in virtualized translation coherence.

Our second group of workloads is made up of smaller-footprint
applications whose data largely fits within the die-stacked DRAM. We
use these workloads to evaluate HATRIC's overheads in situations
where hypervisor-mediated paging (and hence translation coherence)
between die-stacked and off-chip DRAM is rarer. We use the remaining
Parsec applications, and Spec applications for these studies.



§ EVALUATION





 Performance as a function of vCPU counts:
Figure <ref> shows HATRIC's runtime, normalized as a
fraction of application runtime in the absence of any die-stacked
memory (no-hbm from Figure <ref>). We compare
runtimes for the best KVM paging policies (sw), HATRIC,
and ideal unachievable zero-overhead translation coherence (ideal). Further, we vary the number of vCPUs per VM and observe the
following.

HATRIC is always within 2-4% of the ideal
performance. In some cases, HATRIC is instrumental in achieving
any gains from die-stacked memory at all. Consider data caching,
which slows down when using die-stacked memory, because of translation
coherence overheads. HATRIC cuts runtimes down to roughly 75%
of the baseline runtime in all cases.

Figure <ref> also shows that HATRIC is valuable at all
vCPU counts. In some cases, more vCPUs exacerbate translation
coherence overheads. This is because IPI broadcasts become more
expensive and more vCPUs suffer VM exits.  This is why, for example,
data caching and tunkrank become slower (see sw)
when vCPUs increase from 4 to 8. HATRIC eliminates these
problems, flattening runtime improvements across vCPU counts. In other
scenarios, fewer vCPUs worsen performance since each vCPU performs
more of the application's total work. Here, the impact of a full TLB,
nTLB, and MMU cache flush for every page remapping is very expensive
(e.g., graph500 and facesim). Here, HATRIC again
eliminates these overheads almost entirely.





 Performance as a function of paging
  policy: Figure <ref> also shows HATRIC performance,
but this time as a function of different KVM paging policies. We study
three policies with 16 vCPUs. First, we show lru, which
determines which pages to evict from die-stacked DRAM. We then add the
migration daemon (&mig-dmn), and page prefetching
(&pref).

Figure <ref> shows HATRIC improves runtime substantially
for any paging policy. Performance is best when all techniques are
combined, but HATRIC achieves 10-30% performance improvements
even for just lru. Furthermore, Figure <ref> shows that
translation coherence overheads can often be so high that the paging
policy itself makes little difference to performance. Consider tunkrank, where the difference between lru versus the &pref bars is barely 2-3%. With HATRIC, however, paging
optimizations like prefetching and migration daemons help. 







Impact of translation structure sizes: One
of HATRIC's advantages is that it converts translation structure
flushes to selective invalidations. This improves TLB, MMU cache, and
nTLB hit rates substantially, obviating the need for expensive
two-dimensional page table walks. We expect HATRIC to improve
performance even more as translation structures become bigger (and
flushes needlessly evict more entries). Figure <ref> quantifies
the relationship. We vary TLB, nTLB, and MMU cache sizes from the
default (see Sec. <ref>) to double (2×) and
quadruple (4×) the number of entries.

Figure <ref> shows that translation structure flushes largely
counteract the benefits of greater size. Specifically, the sw
results see barely any improvement, even when sizes are
quadrupled. Inter-DRAM page migrations essentially flush the
translation structures so often that additional entries are not
effectively leveraged. Figure <ref> shows that this is a wasted
opportunity since zero-overhead translation coherence (ideal)
actually does enjoy 5-7% performance benefits. HATRIC solves
this problem, comprehensively achieving within 1% of the ideal,
thereby exploiting larger translation structures.




Multi-programmed workloads: We now focus on
multiprogrammed workloads made up sequential applications. Each
workload runs 16 Spec benchmarks on a Linux VM atop KVM. As is
standard for multiprogrammed workloads, we use two performance metrics
<cit.>. The first is weighted runtime
improvement, which captures overall system performance. The second is
the runtime improvement of the slowest application in the workload,
capturing fairness.

Figure <ref> shows our results. The graph on the left plots the
weighted runtime improvement, normalized to cases without die-stacked
DRAM. As usual, sw represents the best KVM paging policy. The
x-axis represents the workloads, arranged in ascending order of
runtime. The lower the runtime, the better the performance. Similarly,
the graph on the right of Figure <ref> shows shows the runtime
of the slowest application in the workload mix; again, lower runtimes
indicate a speedup in the slowest application.

Figure <ref> shows that translation coherence can be disastrous
to the performance of multiprogrammed workloads. More than 70% of the
workload combinations suffer performance degradation with
die-stacking. These applications suffer from unnecessary translation
structure flushes and VM exits, caused by software translation
coherence's imprecise target identification. Runtime is more than
2× for 11 workloads. Additionally, translation coherence
degrades application fairness. For example, in more than half the
workloads, the slowest application's runtime is (2×)+ with a
maximum of (4×)+. Applications that struggle are usually those
with limited memory-level parallelism that benefit little from the
higher bandwidth of die-stacked memory and instead, suffer from the
additional translation coherence overheads.

HATRIC solves all these issues, achieving improvements for every
single weighted runtime, and even for each of the slowest
applications. In fact, HATRIC entirely eliminating translation
coherence overheads, reducing runtime to 50-80% of the baseline
without die-stacked DRAM. The key enabler is HATRIC's precise
identification of coherence targets – applications that do not need
to participate in translation coherence operations have their
translation structure contents left unflushed and do not suffer VM
exits.




Performance-energy tradeoffs: Intuitively,
we expect that since HATRIC reduces runtime substantially, it
should reduce static energy sufficiently to offset the higher energy
consumption from the introduction of co-tags. Indeed, this is true for
workloads that have sufficiently large memory footprints to trigger
inter-memory paging. However, we also assess HATRIC's energy
implications on workloads that do not frequently remap pages (i.e.,
their memory footprints fit comfortably within die-stacked
DRAM). 

The graph on the left of Figure <ref> plots all the workloads
including the single-threaded and multithreaded ones that benefit from
die-stacking and those whose memory needs fit entirely in die-stacked
DRAM. The x-axis plots the workload runtime, as a fraction of the
runtime of sw results. The y-axis plots energy, similarly
normalized. We desire points that converge towards the lower-left
corner of the graph.

The graph on the left of Figure <ref> shows that HATRIC
always boosts performance, and almost always improves energy
too. Energy savings of 1-10% are routine. In fact, HATRIC even
improves the performance and energy of many workloads that do not page
between the two memory levels. This is because these workloads still
remap pages to defragment memory (to support superpages) and HATRIC mitigates the associated translation coherence
overheads. There are some rare instances (highlighted in black) where
energy does exceed the baseline by 1-1.5%. These are workloads for
whom efficient translation coherence does not make up for the
additional energy of the co-tags. Nevertheless, these overheads are
low, and their instances rare.


Co-tag sizing: We now turn to co-tag
sizing. Excessively large co-tags consume significant lookup and
static energy, while small ones force HATRIC to invalidate too
many translation structures on a page remap. The graph on the right of
Figure <ref> shows the performance-energy implications of
varying co-tag size from 1 to 3 bytes.

First and foremost, 2B co-tags – our design choice – provides the
best balance of performance and energy. While 3B co-tags track page
table entries at a finer granularity, they only modestly improve
performance over 2B co-tags, but consume much more energy. Meanwhile
1B co-tags suffer in terms of both performance and energy. Since 1B
co-tags have a coarser tracking granularity, they invalidate more
translation entries from TLBs, MMU caches, and nTLBs than larger
co-tags. And while the smaller co-tags do consume less lookup and
static energy, these additional invalidations lead to more expensive
two-dimensional page table walks and a longer system runtime. The end
result is an increase in energy too. 


Coherence directory design decisions:
Sec. <ref> detailed the nuances modifying traditional
coherence directories to support translation coherence. Figure
<ref> captures the performance and energy (normalized to
those of the best paging policy or sw in previous graphs) of
these approaches. We consider the following options, beyond baseline
HATRIC.




EGR-dir-update: This is a design that
eagerly updates coherence directories whenever a translation entry is
evicted from a CPU's L1 cache or translation structures. While this
does reduce spurious coherence messages, it requires expensive lookups
in translation structures to ensure that entries with the same co-tag
have been evicted. Figure <ref> shows that the performance
gains from reduced coherence traffic is almost negligible, while
energy does increase, relative to HATRIC.


FG-tracking: We study a hypothetical design
with greater specificity in translation tracking. That is, coherence
directories are modified to track whether translations are cached in
the TLBs, MMU caches, nTLBs, or L1 caches. Unlike HATRIC, if a
translation is cached only in the MMU cache but not the TLB, the
latter is not sent invalidation requests. Figure <ref>
shows that while one might expect this specificity to result in
reduced coherence traffic, system energy is actually slightly higher
than HATRIC. This is because more specificity requires more
complex and area/energy intensive coherence directories. Further, since
the runtime benefits are small, we believe HATRIC remains the
  smarter choice.


No-back-inv: We study an unrealistically
ideal design with infinitely-sized coherence directories which never
need to relay back-invalidations to private caches or translation
structures. We find that this does reduce energy and runtime, but not
significantly from HATRIC's dual-grain coherence directory based
on <cit.>.


All: Figure <ref> compares HATRIC to an approach which marries all the optimizations
discussed. HATRIC almost exactly meets the same performance and
is actually more energy-efficient, largely because the eager updates
of coherence directories add significant translation structure lookup
energy.


Comparison with UNITD: We now compare HATRIC to prior work on UNITD <cit.>. To do
this, we first upgrade the baseline UNITD design in several
ways. First, and most importantly, we extend add support for
virtualization by storing the system physical address of nested page
tables entries are stored in the reverse-lookup CAM originally
proposed <cit.>. Second, we extend UNITD to
work seamlessly with coherence directories. We call this upgraded
design UNITD++.

Figure <ref> compares HATRIC and UNITD++ results,
normalized to results from the case without die-stacked DRAM. As
expected, both approaches outperform a system with only traditional
software-based translation coherence (sw). However, HATRIC
typically provides an additional 5-10% performance boost versus UNITD++ by also extending the benefits of hardware translation
coherence to MMU caches and nTLBs. Further, HATRIC is more
energy efficient than UNI­TD++ as it boosts performance (saving
static energy) but also does not need reverse-lookup CAMs.




Xen results: In order to assess HATRIC's generality across hypervisors, we have begun studying it's
effectiveness on Xen. Because our memory traces require months to
collect, we have thus far evaluated canneal and data
  caching, assuming 16 vCPUs. Our initial results show that Xen's
performance is improved by 21% and 33% for canneal and data caching respectively, over the best paging policy employing
software translation.



§ CONCLUSION

We present a case for folding translation coherence atop existing
hardware cache coherence protocols. We achieve this with simple
modifications to translation structures (TLBs, MMU caches, and nTLBs)
and with state-of-the-art coherence protocols. Our solutions are
general (they support nested and guest page table modifications) and
readily-implementable. We believe, therefore, that HATRIC will
become essential for upcoming systems, especially as they rely on page
migration to exploit heterogeneous memory systems.

ieeetr



