Program execution speed critically depends on increasing cache hits, as cache hits are orders of magnitude faster than misses. To increase cache hits, we focus on the problem of cache replacement: choosing which cache line to evict upon inserting a new line. This is challenging because it requires planning far ahead and currently there is no known practical solution. As a result, current replacement policies typically resort to heuristics designed for specific common access patterns, which fail on more diverse and complex access patterns. In contrast, we propose an imitation learning approach to automatically learn cache access patterns by leveraging Belady’s, an oracle policy that computes the optimal eviction decision given the future cache accesses. While directly applying Belady’s is infeasible since the future is unknown, we train a policy conditioned only on past accesses that accurately approximates Belady’s even on diverse and complex access patterns, and call this approach Parrot. When evaluated on 13 of the most memory-intensive SPEC applications, Parrot increases cache miss rates by 20% over the current state of the art. In addition, on a large-scale web search benchmark, Parrot increases cache hit rates by 61% over a conventional LRU policy. We release a Gym environment to facilitate research in this area, as data is plentiful, and further advancements can have significant real-world impact.

Increasing memory demand and slowdown in technology scaling pose important challenges to total cost of ownership (TCO) of warehouse-scale computers (WSCs). One promising idea to reduce the memory TCO is to add a cheaper, but slower, "far memory" tier and use it to store infrequently accessed (or cold) data. However, introducing a far memory tier brings new challenges around dynamically responding to workload diversity and churn, minimizing stranding of capacity, and addressing brownfield (legacy) deployments. We present a novel software-defined approach to far memory that proactively compresses cold memory pages to effectively create a far memory tier in software. Our end-to-end system design encompasses new methods to define performance service-level objectives (SLOs), a mechanism to identify cold memory pages while meeting the SLO, and our implementation in the OS kernel and node agent. Additionally, we design learning-based autotuning to periodically adapt our design to fleet-wide changes without a human in the loop. Our system has been successfully deployed across Google's WSC since 2016, serving thousands of production services. Our software-defined far memory is significantly cheaper (67% or higher memory cost reduction) at relatively good access speeds (6us) and allows us to store a significant fraction of infrequently accessed data (on average, 20%), translating to significant TCO savings at warehouse scale.

This article proposes Benzene, an energy-efficient distributed SRAM/STT-RAM hybrid cache for manycore systems running multiple applications. It is based on the observation that a naïve application of hybrid cache techniques to distributed caches in a manycore architecture suffers from limited energy reduction due to uneven utilization of scarce SRAM. We propose two-level optimization techniques: intra-bank and inter-bank. Intra-bank optimization leverages highly associative cache design, achieving more uniform distribution of writes within a bank. Inter-bank optimization evenly balances the amount of write-intensive data across the banks. Our evaluation results show that Benzene significantly reduces energy consumption of distributed hybrid caches.

In mobile systems, such as smartphones, most of storage writes are incurred by the SQLite database (DB) system. These writes consist of two parts: writes to original data (e.g., SQLite DB file) and journaling-induced writes. In this paper, we first report our observations on the characteristics of these writes: (1) journaling writes dominate storage write, (2) overwrites are frequent in mobile storage, and most importantly, and (3) those overwrites change only a small portion of data. Based on these observations, we propose to employ small capacitor-backed nonvolatile write buffer and use it to durably store small writes without journaling. This allows us to completely avoid journal writes for those small writes, which contributes to significant reduction in journaling-induced writes while still providing the same level of data consistency and durability. In our mechanism, it is critical to minimize the capacity of nonvolatile write buffer so that the backing capacitor does not violate stringent resource/size requirements of mobile systems. Therefore, we propose three optimizations that make the best use of small write buffer: (1) write buffer that manages only the difference between old and new data, (2) a dynamic method to determine which data to store in the write buffer, and (3) an incremental flush policy, which controls the number of write buffer entries to be flushed. The experimental results show 92.4% and 85.1% storage write reductions on average when running single and multiple mobile applications, respectively, with only 8 KB write buffer and a tiny capacitor.

Quantization is considered as one of the most effective methods to optimize the inference cost of neural network models for their deployment to mobile and embedded systems, which have tight resource constraints. In such approaches, it is critical to provide low-cost quantization under a tight accuracy loss constraint (e.g., 1%). In this paper, we propose a novel method for quantizing weights and activations based on the concept of weighted entropy. Unlike recent work on binary-weight neural networks, our approach is multi-bit quantization, in which weights and activations can be quantized by any number of bits depending on the target accuracy. This facilitates much more flexible exploitation of accuracy-performance trade-off provided by different levels of quantization. Moreover, our scheme provides an automated quantization flow based on conventional training algorithms, which greatly reduces the design-time effort to quantize the network. According to our extensive evaluations based on practical neural network models for image classification (AlexNet, GoogLeNet and ResNet-50/101), object detection (R-FCN with 50-layer ResNet), and language modeling (an LSTM network), our method achieves significant reductions in both the model size and the amount of computation with minimal accuracy loss. Also, compared to existing quantization schemes, ours provides higher accuracy with a similar resource constraint and requires much lower design effort.

Modern DRAM suffers from a new problem called row hammering. The problem is expected to become more severe in future DRAMs mostly due to increased inter-row coupling at advanced technology. In order to address this problem, we present a probabilistically managed table (called PRoHIT) implemented on the DRAM chip. The table keeps track of victim row candidates in a probabilistic way and, in case of auto-refresh, the topmost entry is additionally refreshed thereby mitigating the row hammering problem. Our experiments with PARSEC benchmark and synthetic traces show that PRoHIT outperforms the state-of-the-art method, PARA, by 35.7% (PARSEC) in terms of the reduction ratio of row-hammer cases. Our proposed method also shows constantly superior performance to PARA for synthetic traces.

It is imperative to accelerate convolutional neural networks (CNNs) due to their ever-widening application areas from server, mobile to IoT devices. Based on the fact that CNNs can be characterized by a significant amount of zero values in both kernel weights and activations, we propose a novel hardware accelerator for CNNs exploiting zero weights and activations. We also report a zero-induced load imbalance problem, which exists in zero-aware parallel CNN hardware architectures, and present a zero-aware kernel allocation as a solution. According to our experiments with a cycle-accurate simulation model, RTL, and layout design of the proposed architecture running two real deep CNNs, pruned AlexNet [1] and VGG-16 [2], our architecture offers 4x/1.8x (AlexNet) and 5.2x/2.1x (VGG-16) speedup compared with state-of-the-art zero-agnostic/zero-activation-aware architectures.

In this article, we propose Aggregation-in-Memory (AIM), a new processing-in-memory system designed for energy efficiency and near-term adoption. In order to efficiently perform aggregation, we implement simple aggregation operations in main memory and develop a locality-adaptive host architecture for in-memory aggregation, called cache-conscious aggregation. Through this, AIM executes aggregation at the most energy-efficient location among all levels of the memory hierarchy. Moreover, AIM minimally changes existing sequential programming models and provides fully automated compiler toolchain, thereby allowing unmodified legacy software to use AIM. Evaluations show that AIM greatly improves the energy efficiency of main memory and the system performance.

Spin-transfer torque RAM (STT-RAM) has emerged as an energy-efficient and high-density alternative to SRAM for large on-chip caches. However, its high write energy has been considered as a serious drawback. Hybrid caches mitigate this problem by incorporating a small SRAM cache for write-intensive data along with an STT-RAM cache. In such architectures, choosing cache blocks to be placed into the SRAM cache is the key to their energy efficiency. This paper proposes a new hybrid cache architecture called prediction hybrid cache. The key idea is to predict write intensity of cache blocks at the time of cache misses and determine block placement based on the prediction. We design a write intensity predictor that realize the idea by exploiting a correlation between write intensity of blocks and memory access instructions that incur cache misses of those blocks. It includes a mechanism to dynamically adapt the predictor to application characteristics. We also design a hybrid cache architecture in which write-intensive blocks identified by the predictor are placed into the SRAM region. Evaluations show that our scheme reduces energy consumption of hybrid caches by 28 percent (31 percent) on average compared to the existing hybrid cache architecture in a single-core (quad-core) system.

Phase-change memory (PCM) has several benefits including low cost, non-volatility, byte-addressability, etc., and limitations such as write endurance. There have been several hardware approaches to exploit the benefits while minimizing the negative impact of limitations. Software approaches could give further improvements, when used together with hardware approaches, by taking advantage of write behavior present in the program, e.g., write behavior on dynamically allocated data, which is hardly captured by hardware approaches. This work proposes a software design methodology to reduce costly PCM writes. First, on top of existing hardware approach such as Flip-N-Write, we advocate exploiting the capability of PCM bit-level differential write in the software by judiciously reusing previously allocated memory resource. In order to avoid wear-out incurred by the reuse, we present software-based wear-leveling methods that distribute writes across PCM cells. In order to further reduce PCM writes, we propose identifying data, the loss of which does not affect the functionality of the underlying software, and then diverting write traffic for those data items to volatile memory. To evaluate the effectiveness of these methods, as a case study, we applied the proposed methods to the design of journaling in SQLite, which is an important database application commonly used in smartphones. For the experiments, we used an in-house PCM-based prototype board. Our experiments with four representative mobile applications show that the proposed design methods, which is applied on top of the hardware approach, Flip-N-Write, result in 75.2% further reduction in total bit updates in PCM, on average, without aggravating wear-out compared with the baseline of PCM-based journaling, which is based only on the hardware approach. Also, the proposed design methods result in 49.4% reduction in energy consumption and 52.3% reduction in runtime compared to a typical FIFO management of free resources.

The hybrid memory cube (HMC) is a 3-D-stacked DRAM architecture designed for substantially improved memory bandwidth. In particular, its I/O interface achieves up to 320 GB/s of external bandwidth through high-speed serial links. However, it comes at the cost of large static power of off-chip links, which dominates total power consumption of HMCs. In this paper, we propose an adaptive mechanism to partially disable off-chip links of HMCs to reduce the energy consumption of the off-chip links. In order to determine the number of the links to be disabled upon application loads, we develop a simple hardware module called link delay monitor to simulate all different link configurations at the same time and find the largest number of the links to be disabled while satisfying the given performance constraint. We also present two-level prefetching with in-HMC prefetch buffers to further improve the efficiency of our link power management scheme in the presence of prefetching. Evaluations show that our scheme reduces the energy consumption of HMCs by 52% on average with a negligible performance degradation.

Most previous researches on thermal management of many-core architectures focus on the control of either core resources or network resources only, even though both have significant thermal impacts. This paper proposes a holistic thermal management that applies dynamic voltage/frequency scaling to cores and routers together to maximize system performance under temperature constraint. The proposed method first determines a power budget given in aggregate weighted power for every pillar of vertically adjacent tiles. Then it performs voltage/frequency assignment under the budget while exploiting the characteristics of the applications. Experiments show that our approach outperforms existing methods.

The explosion of digital data and the ever-growing need for fast data analysis have made in-memory big-data processing in computer systems increasingly important. In particular, large-scale graph processing is gaining attention due to its broad applicability from social science to machine learning. However, scalable hardware design that can efficiently process large graphs in main memory is still an open problem. Ideally, cost-effective and scalable graph processing systems can be realized by building a system whose performance increases proportionally with the sizes of graphs that can be stored in the system, which is extremely challenging in conventional systems due to severe memory bandwidth limitations.

Processing-in-memory (PIM) is rapidly rising as a viable solution for the memory wall crisis, rebounding from its unsuccessful attempts in 1990s due to practicality concerns, which are alleviated with recent advances in 3D stacking technologies. However, it is still challenging to integrate the PIM architectures with existing systems in a seamless manner due to two common characteristics: unconventional programming models for in-memory computation units and lack of ability to utilize large on-chip caches.

This paper presents an energy-efficient exclusive last-level cache design based on STT-RAM, which is an emerging memory technology that has higher density and lower static power compared to SRAM. Exclusive caches are known to provide higher effective cache capacity than inclusive caches by removing duplicated copies of cache blocks across hierarchies. However, in exclusive cache hierarchies, every block evicted from the lower-level cache is written back to the last-level cache regardless of its dirtiness thereby incurring extra write overhead. This makes it challenging to use STT-RAM for exclusive last-level caches due to its high write energy and long write latency. To mitigate this problem, we design an SRAM/STT-RAM hybrid cache architecture based on reuse distance prediction. In our architecture, for the cache blocks evicted from the lower-level cache, blocks that are likely to be accessed again soon are inserted into the SRAM region and blocks that are unlikely to be reused are forced to bypass the last-level cache. Evaluation results show that the proposed architecture significantly reduces energy consumption of the last-level cache while slightly improving the system performance.

Graph computation is becoming more and more popular in machine learning, big data analytics, etc. For such workloads, GPU is considered as an efficient execution platform since graph computation is characterized by massively parallel computation and high demand of memory bandwidth. In our investigation, existing GPU programming methods for graph computation do not fully exploit high memory bandwidth as well as high computing power in GPU. We propose a novel optimization called locality-aware vertex scheduling, which aims at minimizing memory requests by adjusting the order of vertex computations to improve temporal locality of vertex data stored in on-chip caches. Experiments with nine real-world graphs and three graph algorithms on the recent GPU platform show that the proposed method offers a significant speedup (average 46%) over the state-of-the-art graph algorithm implementation on GPUs.

The Hybrid Memory Cube (HMC) is a 3D-stacked DRAM architecture designed for substantially improved memory bandwidth. In particular, its I/O interface achieves up to 320 GB/s of external bandwidth through high-speed serial links. However, it comes at a cost of large static power of off-chip links, which dominates total power consumption of HMCs. Therefore, we propose an adaptive mechanism to partially disable off-chip links of HMCs with a minimal performance impact. We also present two-level prefetching with in-HMC prefetch buffers to further improve its efficiency in the presence of prefetching. Evaluations show that our scheme reduces energy consumption of HMCs by 51% on average.

Spin-Transfer Torque RAM (STT-RAM) has been considered as a promising candidate for on-chip last-level caches, replacing SRAM for better energy efficiency, smaller die footprint, and scalability. However, it also introduces several new challenges into last-level cache design that need to be overcome for feasible deployment of STT-RAM caches. Among other things, mitigating the impact of slow and energy-hungry write operations is of the utmost importance. In this paper, we propose a new mechanism to reduce write activities of STT-RAM last-level caches. The key observation is that a significant amount of data written to last-level caches is not actually re-referenced again during the lifetime of the corresponding cache blocks. Such write operations, which we call dead writes, can bypass the cache without incurring extra misses by definition. Based on this, we propose Dead Write Prediction Assisted STT-RAM Cache Architecture (DASCA), which predicts and bypasses dead writes for write energy reduction. For this purpose, we first propose a novel classification of dead writes, which is composed of dead-on-arrival fills, dead-value fills, and closing writes, as a theoretical model for redundant write elimination. On top of that, we present a dead write predictor based on a state-of-the-art dead block predictor. Evaluations show that our architecture achieves an energy reduction of 68% (62%) in last-level caches and an additional energy reduction of 10% (16%) in main memory and even improves system performance by 6% (14%) on average compared to the STT-RAM baseline in a single-core (quad-core) system.

This brief presents an approach to reduce static power consumption in peripheral circuits of spin-transfer torque RAM (STT-RAM) instruction caches. It is based on the key observation that only a small set of instructions is accessed inside a program loop. We propose to add a small static RAM cache called loop cache between the processor and the L1 instruction cache made of STT-RAM. When the loop cache has an entire loop cached, the L1 instruction cache can be turned off to save energy during the execution of the loop. Experimental results show that the proposed approach achieves 49% reduction in energy consumption over the STT-RAM baseline.

Recent researches on STT-RAM revealed that device scaling makes its write operations unreliable. To mitigate the impact of this problem, this paper proposes a low-cost, ECC-based solution for STT-RAM caches. In particular, it proposes to share storage for ECC among different blocks within a set and to use them only for unsuccessful write operations. Experimental results show that our scheme reduces 74% to 98% of area overhead incurred by the conventional per-block ECC while maintaining system performance and reliability.

This paper presents a novel concept called write intensity prediction for energy-efficient non-volatile caches as well as the architecture that implements the concept. The key idea is to correlate write intensity of cache blocks with addresses of memory access instructions that incur cache misses of those blocks. The predictor keeps track of instructions that tend to load write-intensive blocks and utilizes that information to predict write intensity of blocks. Based on this concept, we propose a block placement strategy driven by write intensity prediction for SRAM/STT-RAM hybrid caches. Experimental results show that the proposed approach reduces write energy consumption by 55% on average compared to the existing hybrid cache architecture.

Coarse-grained reconfigurable architecture typically has an array of processing elements which are controlled by a centralized unit. This makes it difficult to execute programs having control divergence among PEs without predication. However, conventional predication techniques have a negative impact on both performance and power consumption due to longer instruction words and unnecessary instruction-fetching decoding nullifying steps. This article reveals performance and power issues in predicated execution which have not been well-addressed yet. Furthermore, it proposes fast and power-efficient predication mechanisms. Experiments conducted through gate-level simulation show that our mechanism improves energy-delay product by 11.9% to 23.8% on average.

Extensible processors have been widely used to achieve the conflicting demands for performance improvement, low power consumption, and flexibility. As extensible processors have become more popular, several algorithms have been proposed for automatically identifying instruction-set extensions in order to reduce the effort of manual design and verification. However, most of them focus on finding large and complex instructions that are used only once, rather than repeatedly used ones. Moreover, some other approaches that consider recurrence are limited to finding small instructions. This paper proposes a novel algorithm that considers the instruction reusability as well as input/output (I/O) serialization. In order to overcome the high complexity of the problem, we develop a canonical-form construction algorithm for fast isomorphism detection on directed acyclic graphs and an incremental template generation algorithm that identifies the best custom instruction in terms of a user-defined fitness function. Moreover, our algorithm serializes I/O operations so that the numbers of inputs and outputs of custom instructions are not limited by the microarchitecture. This paper also proposes an algorithm for multiple custom instructions utilizing a well-known iterative selection algorithm. Last, it presents a hybrid algorithm composed of our algorithm and the previous algorithm that does not consider reusability. Experimental results show that our isomorphism-aware algorithm achieves significant improvement over previous approaches in terms of algorithm runtime, as well as performance gain obtained by custom instructions.

As power-efficient design becomes more important, spin-transfer torque RAM (STT-RAM) has drawn a lot of attention due to its ability to meet both high performance and low power consumption. However, its high write energy incurs an increase of dynamic power consumption and may offset power saving due to its low static power. This paper proposes a novel technique called lower-bits caches for reducing write activities of STT-RAM L2 caches. Based on the observation that upper bits of data are not changed as frequently as lower bits in most applications, the technique tries to hide frequent bit changes in lower bits from the L2 cache. Experimental results show that our architecture reduced 25 percent of energy consumed by the L2 cache and slightly improved performance at the same time compared to the STT-RAM baseline.

This paper introduces an innovative algorithm for automatic instruction-set extension, which gives a pseudo-optimal solution within polynomial time to the size of a graph. The algorithm uses top-down dynamic programming strategy with the branch-and-bound algorithm in order to exploit overlapping of subproblems. Correctness of the algorithm is formally proved, and time complexity is analyzed from it. Also, it is verified that the algorithm gives an optimal solution for some type of merit functions, and has very small possibility of obtaining non-optimal solution in general. Furthermore, several experimental results are presented as evidence of the fact that the proposed algorithm has notable performance improvement.