CPU cache

Related publications (100)

Software Support for Non-Volatile Memory (NVM) Programming

David Teksen Aksun

Non-Volatile Memory (NVM) is an emerging type of memory device that provides fast, byte-addressable, and high-capacity durable storage. NVM sits on the memory bus and allows durable data structures designs similar to the in-memory equivalent ones. Expensive serialization/deserialization operations, usually associated with block-based storage, are not necessary. Unfortunately, using NVM is not as simple as placing a data structure in NVM and expecting persistence. As NVM sits on the memory bus, processor caches buffer the cache lines from it that are referenced by load and store instructions. The volatility of the caches and possible power failures at a random point in a program complicate the design and require ways to handle these failures. Prior work focused on implementing crash-consistency mechanisms to correctly recover a program's data after a failure. The goal was to minimize the use of costly cache line write-back and fence instructions, which are necessary for correct durability. Moreover, commercial NVM devices are slower compared to DRAM and affect the design. In addition to performance overheads, correctly implementing crash consistency is hard. The programmers need to carefully reason about cache line write-back instructions and the order of persistent writes. Finding bugs can take from minutes to hours. In this thesis, we use checkpointing as an effective crash-consistency mechanism with low overhead for building durable data structures. We also describe an inter-procedural dataflow analysis for fast detection of NVM programming bugs. We show the practicality of these ideas through three primary contributions and their implementations. Firstly, we present InCLL to address NVM checkpointing. InCLL is a novel technique that uses fine-grained checkpointing and in-cache-line logging to minimize the number of explicit write-back and fence instructions in the fast path of data structure modifications. We evaluate InCLL both on DRAM and Optane devices for the Masstree data structure. Secondly, we present a new checkpointing design, CpNvm, which minimizes NVM write-back instructions on the critical path of the execution. We achieve low overheads for Masstree and Memcached for write-heavy workloads, and almost no overheads for read-only workloads. In addition, we present FlowNvm to find NVM programming bugs. FlowNvm can identify NVM programming pattern violations and anti-patterns at compile-time using inter-procedural dataflow analysis.

EPFL2021

Adaptive Cache Mode Selection for Queries over Raw Data

Anastasia Ailamaki, Tahir Azim, Azqa Nadeem

Caching the results of intermediate query results for future re-use is a common technique for improving the performance of analytics over raw data sources. An important design choice in this regard is whether to lazily cache only the offsets of satisfying tuples, or to eagerly cache the entire tuples. Lazily cached offsets have the benefit of smaller memory requirement and lower initial caching overhead, but they are much more expensive to reuse. In this paper, we explore this tradeoff and show that neither lazy nor the eager caching mode is optimal for all situations. Instead, the ideal caching mode depends on the workload, the dataset and the cache size. We further show that choosing the sub-optimal caching mode can result in a performance penalty of over 200%. We solve this problem using an adaptive online approach that uses information about query history, cache behavior and cache size to choose the optimal caching mode automatically. Experiments on TPC-H based workloads show that our approach enables execution time to differ by, at most, 16% from the optimal caching mode, and by just 4% on the average.

2018

TurboTag: Lookup Filtering to Reduce Coherence Directory Power

Daniel Crisan, Babak Falsafi, Michael Ferdman, Pejman Lotfi Kamran

On-chip coherence directories of today’s multi-core systems are not energy efficient. Coherence directories dissipate a significant fraction of their power on unnecessary lookups when running commercial server and scientific workloads. These workloads have large working sets that are beyond the reach of on-chip caches of modern processors. Limited to capturing a small part of the working set, private caches retain cache blocks only for a short period of time before replacing them with new blocks. Moreover, coherence enforcement is a known performance bottleneck of multi-threaded software, hence data-sharing in optimized high-performance software is minimal. Consequently, the majority of the accesses to the coherence directory find no sharers in the directory because the data are not available in the on-chip private caches, effectively wasting power on the coherence checks. To improve energy-efficiency for future many-core systems, we propose TurboTag, a filtering mechanism to eliminate needless directory lookups. We analyze full-system traces of server and scientific workloads and find that over 69% of accesses to the directory find no sharers and can be entirely avoided. Taking advantage of this behavior, TurboTag achieves a 58% reduction in the directory’s dynamic power consumption.

ACM2010

Disaggregated memory can address resource provisioning inefficiencies in current datacenters. Multiple software runtimes for disaggregated memory have been proposed in an attempt to make disaggregated memory practical. These systems rely on the virtual memory subsystem to transparently offer disaggregated memory to applications using a local memory abstraction. Unfortunately, using virtual memory for disaggregation has multiple limitations, including high overhead that comes from the use of page faults to identify what data to fetch and cache locally, and high dirty data amplification that comes from the use of page-granularity for tracking changes to the cached data (4KB or higher). In this paper, we propose a fundamentally new approach to designing software runtimes for disaggregated memory that addresses these limitations. Our main observation is that we can use cache coherence instead of virtual memory for tracking applications' memory accesses transparently, at cache-line granularity. This simple idea (1) eliminates page faults from the application critical path when accessing remote data, and (2) decouples the application memory access tracking from the virtual memory page size, enabling cache-line granularity dirty data tracking and eviction. Using this observation, we implemented a new software runtime for disaggregated memory that improves average memory access time by 1.7-5X and reduces dirty data amplification by 2-10X, compared to state-of-the-art systems.

ASSOC COMPUTING MACHINERY2021

Designing Low Power and Durable Digital Blocks Using Shadow Nanoelectromechanical Relays

Hossein Asadi, Paolo Ienne, Sadegh Yazdanshenas

Nanoelectromechanical (NEM) relays are a promising emerging technology that has gained widespread research attention due to its zero leakage current, sharp ON-OFF transitions, and complementary metal-oxide-semiconductor compatibility. As a result, NEM relays have been significantly investigated as highly energy-efficient design solutions. A major shortcoming of NEMs preventing their widespread use is their limited switching endurance. Hence, in order to utilize the low-power advantages of NEM relays, further device, circuit, and architectural techniques are required. In this paper, we introduce the concept of shadow NEM relays, which is a circuit-level technique to leverage the energy efficiency of the NEM relays despite their low switching endurance. This technique creates two virtual ground nodes in a block to allow: 1) a low power mode with functional NEM relays and 2) a normal mode with failed NEM relays. To demonstrate the applicability of this concept, we have applied it to a six-transistor SRAM cell as an illustrative example. We also investigate the applicability of this SRAM cell in field-programmable gate arrays and on-chip caches. Experimental results reveal that shadow NEM relays can reduce the power consumption of SRAM cells by up to 80% while addressing the limited switching endurance of NEM relays.

Institute of Electrical and Electronics Engineers2016

Improving Main-memory Database System Performance through Cooperative Multitasking

Georgios Psaropoulos

Database systems access memory either sequentially or randomly. Contrary to sequential access and despite the extensive efforts of computer architects, compiler writers, and system builders, random access to data larger than the processor cache has been synonymous to inefficient execution. Especially in the big data era, data processing is memory bound, and accesses to DRAM and non-volatile memory each take several tens or hundreds of nanoseconds respectively, posing a great challenge to current processors. Due to the mismatch between the way humans write code and the way processors execute this code, workload execution stalls on main memory access, instead of executing the other parallel work that typically exists in big data workloads. This thesis establishes cooperative multitasking as the principal way to hide memory latency in operations that consist of parallel tasks. We first systematize cooperative multitasking presenting an analogue of Amdahl's law for latency hiding. More importantly, we then introduce interleaving with coroutines, a general-purpose and practical technique to interleave the execution of parallel tasks within one thread interleaved execution and thereby hide memory access. This form of cooperative multitasking enables significant performance improvements for analytical and transactional use cases that suffer from unavoidable memory accesses, such as index joins and tuple reconstruction, as well as concurrent GET and PUT operations in key-value stores. Given enough parallel work, sufficient hardware support for concurrent memory accesses, and a low-overhead mechanism to switch between tasks, interleaved execution renders important database operations oblivious to memory latency and makes their execution behave as if all accessed data resides in the processor cache.

EPFL2019

Linebacker: Preserving Victim Cache Lines in Idle Register Files of GPUs

Yunho Oh

Modern GPUs suffer from cache contention due to the limited cache size that is shared across tens of concurrently running warps. To increase the per-warp cache size prior techniques proposed warp throttling which limits the number of active warps. Warp throttling leaves several registers to be dynamically unused whenever a warp is throttled. Given the stringent cache size limitation in GPUs this work proposes a new cache management technique named Linebacker (LB) that improves GPU performance by utilizing idle register file space as victim cache space. Whenever a CTA becomes inactive, linebacker backs up the registers of the throttled CTA to the off-chip memory. Then, linebacker utilizes the corresponding register file space as victim cache space. If any load instruction finds data in the victim cache line, the data is directly copied to the destination register through a simple register-register move operation. To further improve the efficiency of victim cache linebacker allocates victim cache space only to a select few load instructions that exhibit high data locality. Through a careful design of victim cache indexing and management scheme linebacker provides 29.0% of speedup compared to the previously proposed warp throttling techniques.

ASSOC COMPUTING MACHINERY2019

Near-Memory Address Translation

Javier Picorel Obando

Virtual memory (VM) is a crucial abstraction in modern computer systems at any scale, from handheld devices to datacenters. VM provides programmers the illusion of an always sufficiently large and linear memory, making programming easier. Although the core components of VM have remained largely unchanged since early VM designs, the design constraints and usage patterns of VM have radically shifted from when it was invented. Today, computer systems integrate hundreds of gigabytes to a few terabytes of memory, while tightly integrated heterogeneous computing platforms (e.g., CPUs, GPUs, FPGAs) are becoming increasingly ubiquitous. As there is a clear trend towards extending the CPU's VM to all computing elements in the system for an efficient and easy to use programming model, the continuous demand for faster memory accesses calls for fast translations to terabytes of memory for any computing element in the system. Unfortunately, conventional translation mechanisms fall short of providing fast translations as contemporary memories exceed the reach of today's translation caches, such as TLBs. In this thesis, we provide fundamental insights into the reason why address translation sits on the critical path of accessing memory. We observe that the traditional fully associative flexibility to map any virtual page to any page frame precludes accessing memory before translating. We study the associativity in VM across a variety of scenarios by classifying page faults using the 3C model developed for caches. Our study demonstrates that the full associativity of VM is unnecessary, and only modest associativity is required. We conclude that capacity and compulsory misses---which are unaffected by associativity---dominate, while conflict misses rapidly disappear as the associativity of VM increases. Building on the modest associativity requirements, we propose a distributed memory management unit close to where the data resides to reduce or eliminate the TLB miss penalty.

EPFL2017

STREX: Boosting Instruction Cache Reuse in OLTP Workloads Through Stratified Transaction Execution

Anastasia Ailamaki, Xin Tong, Pinar Tözün

Online transaction processing (OLTP) workload performance suffers from instruction stalls; the instruction footprint of a typical transaction exceeds by far the capacity of an L1 cache, leading to ongoing cache thrashing. Several proposed techniques remove some instruction stalls in exchange for error-prone instrumentation to the code base, or for a sharp increase the L1-I cache unit area and power. Others reduce instruction miss latency by better utilizing a shared L2 cache. SLICC, a recently proposed thread migration technique that exploits transaction instruction locality, is promising for high core counts but performs sub-optimally or may hurt performance when running on few cores. This paper corroborates that OLTP transactions exhibit significant intra- and inter-thread overlap in their instruction footprint, and analyzes the instruction stall reduction benefits. This paper presents STREX, a hardware, programmer-transparent technique that exploits typical transaction behavior to improve instruction reuse in first level caches. STREX time-multiplexes the execution of similar transactions dynamically on a single core so that instructions fetched by one transaction are reused by all other transactions executing in the system as much as possible. STREX dynamically slices the execution of each transaction into cache-sized segments simply by observing when blocks are brought in the cache and when they are evicted. Experiments show that, when compared to baseline execution on 2 -- 16 cores, STREX consistently improves performance while reducing the number of L1 instruction and data misses by 37% and 14% on average, respectively. Finally, this paper proposes a practical hybrid technique that combines STREX and SLICC, thereby guaranteeing performance benefits regardless of the number of available cores and the workload's footprint.

2013

When it comes to performance, embedded systems share many problems with their higher-end counterparts. The growing gap between top processor frequency and memory access speed, the memory wall, is one such problem. Driven, in part, by low energy consumption and low cost requirements, embedded systems are often customized to a single application, or a very small set of applications. In addition, time-to-market requirements and the increasing complexity of embedded systems drives the need for fully or partially automated design tools and also to the extensive use of caches and cache hierarchies. The introduction of multi-processor-based embedded platforms has accelerated this trend; as the design space for embedded systems has grown, designers have become unclear as to whether automatic processor customization tools can cope with this increased complexity. The recent introduction of new techniques addressing the automatic customization, such as Architecturally Visible Storage (AVS) memory-enhanced Instruction Set Extension (ISE) identification algorithms, has also created new challenges. AVS memories are distinct from the cache hierarchy and rely on Direct Memory Access (DMA) transfers to communicate with main memory. In an embedded system containing hardware-managed caches, these extra AVS memories, in combination with their corresponding DMA transfers, cause coherence and consistence problems. Although the problems of coherence and consistence are well known in multi-processor systems, conventional solutions may be expensive in terms of area and power consumption, rendering them unacceptable for use in embedded systems. This thesis presents two low cost coherence mechanisms that solve these two problems. The first mechanism addresses embedded systems that already contain a hardware coherence protocol, like many high-end embedded multi-processor systems. Traditionally, the DMA transactions are transparent to the hardware coherence protocol. By ensuring visibility of these DMA transactions to the hardware coherence protocol, coherence can be guaranteed between AVS memories and data cache(s). As a result, minor changes to the DMA engine are required. Moreover, by forcing the processor pipeline to stall if a DMA transfer is active, memory consistence can be guaranteed. This mechanism provides significant speedup when compared to the execution of a non-ISE-enhanced system; however, due to the increase in bus traffic, this speedup comes at the expense of an increase in energy consumption. Coherent and Speculative DMA are both implementations of this mechanism. Single-processor systems do not contain hardware coherence protocols, and would therefore benefit from a lower-cost solution to the coherence and consistence problems than a hardware coherence protocol. By tightly coupling the AVS memories to the hardware cache, coherence and consistence for the complete system can be guaranteed. This coupling requires insignificant changes to the hardware cache's hit detection circuitry and state machine without influencing its critical path, thus it is inherently inexpensive. This mechanism provides significant speedups and reduces the energy consumed if compared to the execution on non-ISE-enhanced systems. Furthermore, the tight coupling enables direct communication between the AVS memories and the data cache, making this mechanism independent from the processor-to-memory distance. Virtual Ways and Way Stealing are both implementations of this mechanism. Besides enforcing coherence and consistence, the ability to integrate the architectural changes into an automated design flow is important. This thesis shows the influence of Coherent DMA, Speculative DMA, Virtual Ways, and Way Stealing on the ISE-identification algorithm. It shows the architectural requirements and the cost for enforcing coherence and consistence that need to be taken into account when applying these mechanisms in an automated flow without formulating new algorithms.

EPFL2010