Processing-in-Memory (PIM) delivers enormous performance by taking advantage of internal DRAM bandwidth and parallelism. However, graph applications are difficult to adapt to PIM due to their irregular access patterns.We present the first Fine-Grained PIM (FGPIM) design that fully accelerates vertex-centric push-based graph applications by accelerating both their update (computing vertex updates) and apply (summing up the updates) phases. For the update phase, we design a tuple-based LLC that can coalesce at different granularities to group graph updates together and propose multi-DRAM column processing FGPIM instructions to match the cache coalescing to the row-level parallelism of the FGPIM. With this acceleration, the apply phase becomes the bottleneck, and we propose bank-parallel FGPIM instructions with predicates to allow FGPIM to accelerate the conditional updates as well. We achieve an average speedup in the region of interest of 1.8x/3x compared to naive FGPIM and 4.4x/9.8x compared to state-of-the-art non-PIM baseline (HBM2/DDR4), and DRAM energy reduction of 67%/86% and 88%/94%.These results show the importance of providing a complete solution that accelerates both the update and apply phases.

The long latencies of major page faults are often blamed on slow storage, but our study shows that with modern locally attached NVMe SSDs used as swap space, the real culprit is the Linux kernel itself. Indeed, kernel overhead from page table walks, swap cache lookups, block-layer bookkeeping, and interrupt handling frequently exceed the time spent on disk I/O. To explore this, we introduce a lightweight measurement methodology that accurately attributes page fault costs across kernel, I/O, and user-level components. Using representative workloads and microbenchmarks on a single-socket desktop machine, we show that NVMe SSD bandwidth is rarely the bottleneck, and that Linux’s default readahead policy can unpredictably amplify latency. Our findings challenge common assumptions, reveal hidden kernel costs, and point toward opportunities for redesigning page fault handling for modern systems.

As memory capacity has outstripped TLB coverage, large data applications suffer from frequent page table walks. We investigate two complementary techniques for addressing this cost: reducing the number of accesses required and reducing the latency of each access. The first approach is accomplished by opportunistically "flattening" the page table: merging two levels of traditional 4 KB page table nodes into a single 2 MB node, thereby reducing the table's depth and the number of indirections required to traverse it. The second is accomplished by biasing the cache replacement algorithm to keep page table entries during periods of high TLB miss rates, as these periods also see high data miss rates and are therefore more likely to benefit from having the smaller page table in the cache than to suffer from increased data cache misses.

Hybrid memory has become a promising new solution for meeting ever growing memory capacity demands in a cost-effective way. In hybrid memory systems, the fast and high bandwidth memory is used to store performance-critical data, while the slow and low bandwidth memory provides capacity backup. In supporting such hybridization, virtual memory is the key mechanism, which can combine different memory components to a single memory view. For efficient translation for virtual memory, page size has been growing. However, the hybrid memory support requires fine-grained migration to quickly move only necessary memory portions to the precious fast memory. To address the challenges posed by the conflicting goals in the hybrid memory support based on virtual memory, this paper investigates decoupling of address translation into a two-step process. With the two-level translation, the critical core-side TLBs perform the translation to an intermediate address space, and the memory-side translation provides the actual physical location in memory devices. As the second-level translation handling page migration across different memory types, is decoupled from the first-level translation, it allows dynamic adjustment of its mapping granularity to improve the efficiency of translation and data reuse in the fast memory. This paper proposes a hardware architecture which identifies the memory access behavior of an application online and selects the best mapping granularity for the second-level translation.

The SPEC CPU Benchmarks are used extensively for evaluating and comparing improvements to computer systems. This ubiquity makes characterization critical for researchers to understand the bottlenecks the benchmarks do and do not expose and where new designs should and should not be expected to show impact. However, in characterization there is a tradeoff between accuracy and reusability: The more precisely we characterize a benchmark’s performance on a given system, the less usable it is across different micro-architectures and varying memory configurations. For SPEC, most existing characterizations include system-specific effects (e.g., via performance counters) and/or only look at aggregate behavior (e.g., averages over the full application execution). While such approaches simplify characterization, they make it difficult to separate the applications’ intrinsic behavior from the system-specific effects and/or lose the diverse phase-based behaviors. In this work we focus on characterizing the applications’ intrinsic memory behaviour by isolating them from micro-architectural configuration specifics. We do this by providing a simplified generic system model that evaluates the applications’ memory behavior across multiple cache sizes, with and without prefetching, and over time. The resulting characterization can be reused across a range of systems to understand application behavior and allow us to see how frequently different behaviors occur. We use this approach to compare the SPEC 2006 and 2017 suites, providing insight into their memory system behaviour beyond previous system-specific and/or aggregate results. We demonstrate the ability to use this characterization in different contexts by showing a portion of the SPEC 2017 benchmark suite that could benefit from giga-scale caches, despite aggregate results indicating otherwise.

The support for the heterogeneous memory in the conventional virtual memory has an inherent problem. For the efficient translation in the critical translation lookaside buffers (TLBs), the page size has been growing. However, the heterogeneous memory management requires a nimble fine-grained migration mechanism to quickly move necessary memory portions to the precious fast memory.To address the challenges posed by the conflicting goals in the heterogeneous memory support, this paper proposes to decouple the address translation into a two-step process. The decoupling resolves the conflict as the critical core-side TLBs perform the translation to an intermediate address space, and the memory-side translation provides the actual physical location of the memory devices.

The availability of large pages has dramatically improved the efficiency of address translation for applications that use large contiguous regions of memory. However, large pages can be difficult to allocate due to fragmented memory, non-movable pages, or the need to split a large page into regular pages when part of the large page is forced to have a different permission status from the rest of the page. Furthermore, they can also be expensive due to memory bloating caused by sparse accesses to application data. In this work, we enable the allocation of large 2MB pages even in the presence of fragmented physical memory via perforated pages. Perforated pages permit the OS to punch 4KB page-sized holes in the physical address range allocated to a large page and re-map them to other addresses as needed. This not only enables the system to benefit from large pages in the presence of fragmentation, but also allows for different permissions to exist within a large page, enhancing sharing flexibility. In addition, it allows unused parts of a large page to be used elsewhere, mitigating memory bloating. To minimize changes to the system, perforated pages reuse the 4KBlevel page table entries to store the hole locations and translates holes into regular 4KB pages. For performance, the proposed technique caches the translations for hole pages in the TLBs and track holes via cached bitmaps in the L2 TLB. By enabling large pages in the presence of physical memory fragmentation, perforated pages increase the applicability and resulting benefits of large pages with only minor changes to the hardware and OS. In this work, we evaluate the effectiveness of perforated pages with timing simulations under diverse and realistic fragmentation scenarios. Our results show that even with fragmented memory, perforated pages accomplish 93.2% to 99.9% of the performance achievable by ideal memory allocation, and 2.0% to 11.5% better performance over the conventional system running with fragmented memory.

Characterizing the memory behaviour of SPEC CPU benchmarks is critical to analyze bottlenecks in the execution. Unfortunately, most prior characterizations are tied to a particular system (e.g., via performance counters, fixed configurations) and missing important time-based behaviour (e.g., average over execution). While performance counters are accurate for that particular system, the results are less accurate for different micro-architectures and configurations. Most importantly, aggregate statistics (e.g., average over full execution) miss important time-based information which reveal transient phases that have significant impact on the execution. This work focuses on micro-architecturally independent, time-based characterization and analysis of the memory system behavior of SPEC CPU 2017. By collecting micro-architecturally independent and time-based information, we provide reusable data for various memory configurations.

The proliferation of system virtualization poses a new challenge for the coarse-grained time sharing techniques for consolidation, since operating systems are running on virtual CPUs. The current system stack was designed under the assumption that operating systems can seize CPU resources at any moment. However, for the guest operating system on a virtual machine (VM), such assumption cannot be guaranteed, since virtual CPUs of VMs share a limited number of physical cores. Due to the time-sharing of physical cores, the execution of a virtual CPU is not contiguous, with a gap between the virtual and real time spaces. Such a virtual time discontinuity problem leads to significant inefficiency for lock and interrupt handling, which rely on the immediate availability of CPUs whenever the operating system requires computation. To reduce scheduling latencies of virtual CPUs, shortening time slices can be a straightforward strategy, but it may lead to the increased overhead of context switching costs across virtual machines for some workloads. It is challenging to determine a single time slice to satisfy all the VMs. In this article, we propose to have dual time slice to resolve the time slice conflict problem occurred in different types of virtual machines.

DRAM caches have emerged as an efficient new layer in the memory hierarchy to address the increasing diversity of memory components. When a small amount of fast memory is combined with slow but large memory, the cache-based organization of the fast memory can provide a SW-transparent solution for the hybrid memory systems. In such DRAM cache designs, their effectiveness is affected by the bandwidth and latency of both fast and slow memory. To quantitatively assess the effect of memory configurations and application patterns on the DRAM cache designs, this article first investigates how three prior approaches perform with six hybrid memory scenarios. From the investigation, we observe no single DRAM cache organization always outperforms the other organizations across the diverse hybrid memory configurations and memory access patterns. Based on this observation, this article proposes a reconfigurable DRAM cache design that can adapt to different hybrid memory combinations and workload patterns. Unlike the fixed tag and data arrays of conventional on-chip SRAM caches, this study advocates to exploit the flexibility of DRAM caches, which can store tags and data to DRAM in any arbitrary way. Using a sample-based mechanism, the proposed DRAM cache controller dynamically finds the best organization from three candidates and applies the best one by reconfiguring the tags and data layout in the DRAM cache. Our evaluation shows that the proposed morphable DRAM cache can outperform the fixed DRAM configurations across six hybrid memory configurations.

Consolidating multiple virtual machines into a single server has been widely adopted in cloud computing to improve system utilization. However, the sharing of physical CPUs among virtual machines in consolidated systems poses a new challenge in providing an illusion of continuous CPU execution to the guest operating systems (OS). Due to the time-sharing of physical CPUs, the execution of a guest OS is periodically interrupted, while the guest OS may not be aware of the discontinuity of virtual time against the real time. The virtual time discontinuity problem causes the delayed processing of critical OS operations, such as interrupt handling and lock processing. Although there have been several prior studies to mitigate the problem, they address only a subset of symptoms, require the modification of guest OSes, or change the processor architecture. This paper proposes a novel way to comprehensively reduce the inefficiency of guest OS execution in consolidated systems. It migrates the short-lived critical OS tasks to dedicated micro-sliced cores, minimizing the delays caused by time sharing. The hypervisor identifies the critical OS tasks without any OS intervention, and schedules the critical code sections onto the dynamically partitioned cores at runtime. The dedicated micro-sliced cores employ a short sub-millisecond quantum to minimize the response latencies for consolidated virtual machines. By readily servicing the critical tasks, the proposed scheme can minimize the adverse artifact of virtual machine consolidation without any modification of guest OSes.

Supporting atomic durability in emerging persistent memory requires data consistency across potential system failures. For atomic durability support in the non-volatile memory, the traditional write-ahead log (WAL) technique has been employed to guarantee the persistency of logs before actual data updates. Based on the WAL mechanism, recent studies proposed HWassisted logging techniques with undo, redo, or undo+redo principles. The HW log manager allows the overlapping of log writing and transaction execution, as long as the atomicity invariant can be satisfied. Although the efficiency of both log and data writes must be optimized, the prior work exhibit trade-offs in performance under various access patterns. The undo approach experiences performance degradation due to synchronous inplace data updates since the log contains only the old values. On the other hand, the undo+redo approach stores both old and new values, and does not require synchronous in-place data updates. However, the larger log size increases the amount of log writes. The prior redo approach demands extra NVM read bandwidth for indirectly updating in-place data from the new values in logs. To overcome the limitations of the previous approaches, this paper proposes a novel redo-based logging (ReDU), which performs direct and asynchronous in-place data update to NVM. ReDU exploits a small region of DRAM as a write-cache to remove NVM writes from the critical path. The experimental results show that the proposed logging mechanism provides the best performance under a variety of write patterns, showing 8.6%, 14.2%, and 23.6% better performance compared to the previous undo, redo, and undo+redo approaches, respectively.

To mitigate excessive TLB misses in large memory applications, techniques such as large pages, variable length segments, and HW coalescing, increase the coverage of limited hardware translation entries by exploiting the contiguous memory allocation. However, recent studies show that in non-uniform memory systems, using large pages often leads to performance degradation, or allocating large chunks of memory becomes more difficult due to memory fragmentation. Although each of the prior techniques favors its own best chunk size, diverse contiguity of memory allocation in real systems cannot always provide the optimal chunk of each technique. Under such fragmented and diverse memory allocations, this paper proposes a novel HW-SW hybrid translation architecture, which can adapt to different memory mappings efficiently. In the proposed hybrid coalescing technique, the operating system encodes memory contiguity information in a subset of page table entries, called anchor entries. During address translation through TLBs, an anchor entry provides translation for contiguous pages following the anchor entry. As a smaller number of anchor entries can cover a large portion of virtual address space, the efficiency of TLB can be significantly improved. The most important benefit of hybrid coalescing is its ability to change the coverage of the anchor entry dynamically, reflecting the current allocation contiguity status. By using the contiguity information directly set by the operating system, the technique can provide scalable translation coverage improvements with minor hardware changes, while allowing the flexibility of memory allocation. Our experimental results show that across diverse allocation scenarios with different distributions of contiguous memory chunks, the proposed scheme can effectively reap the potential translation coverage improvement from the existing contiguity.

Conventional translation look-aside buffers (TLBs) are required to complete address translation with short latencies, as the address translation is on the critical path of all memory accesses even for L1 cache hits. Such strict TLB latency restrictions limit the TLB capacity, as the latency increase with large TLBs may lower the overall performance even with potential TLB miss reductions. Furthermore, TLBs consume a significant amount of energy as they are accessed for every instruction fetch and data access. To avoid the latency restriction and reduce the energy consumption, virtual caching techniques have been proposed to defer translation to after L1 cache misses. However, an efficient solution for the synonym problem has been a critical issue hindering the wide adoption of virtual caching. Based on the virtual caching concept, this study proposes a hybrid virtual memory architecture extending virtual caching to the entire cache hierarchy, aiming to improve both performance and energy consumption. The hybrid virtual caching uses virtual addresses augmented with address space identifiers (ASID) in the cache hierarchy for common non-synonym addresses. For such non-synonyms, the address translation occurs only after last-level cache (LLC) misses. For uncommon synonym addresses, the addresses are translated to physical addresses with conventional TLBs before L1 cache accesses. To support such hybrid translation, we propose an efficient synonym detection mechanism based on Bloom filters which can identify synonym candidates with few false positives. For large memory applications, delayed translation alone cannot solve the address translation problem, as fixed-granularity delayed TLBs may not scale with the increasing memory requirements. To mitigate the translation scalability problem, this study proposes a delayed many segment translation designed for the hybrid virtual caching. The experimental results show that our approach effectively lowers accesses to the TLBs, leading to significant power savings. In addition, the approach provides performance improvement with scalable delayed translation with variable length segments.

Proliferation of virtualized systems opens a new opportunity to improve the scalability of multi-core architectures. Among the scalability bottlenecks in multi-cores, cache coherence has been one of the most critical problems. Although snoop-based protocols have been dominating commercial multi-core designs, it has been difficult to scale them for more cores, as snooping protocols require high network bandwidth and power consumption for snooping all the caches.In this paper, we propose a novel snoop-based cache coherence protocol, called virtual snooping, for virtualized multi-core architectures. Virtual snooping exploits memory isolation across virtual machines and prevents unnecessary snoop requests from crossing the virtual machine boundaries. Each virtual machine becomes a virtual snoop domain, consisting of a subset of the cores in a system. Although the majority of virtual machine memory is isolated, sharing of cachelines across VMs still occur. To address such data sharing, this paper investigates three factors, data sharing through the hypervisor, virtual machine relocation, and content-based sharing. In this paper, we explore the design space of virtual snooping with experiments on emulated and real virtualized systems including the mechanisms and overheads of the hypervisor. In addition, the paper discusses the scheduling impact on the effectiveness of virtual snooping.

Although time-sharing CPUs has been an essential technique to virtualize CPUs for threads and virtual machines, most of the commercial operating systems and hyper visors maintain relatively coarse-grained time slices to mitigate the costs of context switching. However, the proliferation of system virtualization poses a new challenge for the coarse-grained time sharing techniques, since operating systems are running on virtual CPUs. The current system stack was designed under the assumption that operating systems can seize CPU resources at any moment. However, for the guest operating system on a virtual machine (VM), such assumption cannot be guaranteed, since virtual CPUs of VMs share limited physical cores. Due to the time-sharing of physical cores, the execution of a virtual CPU is not contiguous, with a gap between the virtual and real time spaces. Such a virtual time discontinuity problem leads to significant inefficiency for lock and interrupt handling, which rely on the immediate availability of CPUs whenever the operating system requires computation. This paper investigates the impact of virtual time discontinuity problem for lock and interrupt handling in guest operating systems. To reduce the gap between virtual and physical time spaces, the paper proposes to shorten time slices for CPU virtualization to reduce scheduling latencies of virtual CPUs. However, shortening time slices may lead to the increased overhead of context switching costs across virtual machines. We explore the design space of architectural solutions to reduce context switching overheads with low-cost context-aware cache insertion policies combined with a state-of-the-art context prefetcher.