Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Approximate memory elements <s> Energy has become a first-class design constraint in computer systems. Memory is a significant contributor to total system power. This paper introduces Flikker, an application-level technique to reduce refresh power in DRAM memories. Flikker enables developers to specify critical and non-critical data in programs and the runtime system allocates this data in separate parts of memory. The portion of memory containing critical data is refreshed at the regular refresh-rate, while the portion containing non-critical data is refreshed at substantially lower rates. This partitioning saves energy at the cost of a modest increase in data corruption in the non-critical data. Flikker thus exposes and leverages an interesting trade-off between energy consumption and hardware correctness. We show that many applications are naturally tolerant to errors in the non-critical data, and in the vast majority of cases, the errors have little or no impact on the application's final outcome. We also find that Flikker can save between 20-25% of the power consumed by the memory sub-system in a mobile device, with negligible impact on application performance. Flikker is implemented almost entirely in software, and requires only modest changes to the hardware. <s> BIB001 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Approximate memory elements <s> Disciplined approximate programming lets programmers declare which parts of a program can be computed approximately and consequently at a lower energy cost. The compiler proves statically that all approximate computation is properly isolated from precise computation. The hardware is then free to selectively apply approximate storage and approximate computation with no need to perform dynamic correctness checks. In this paper, we propose an efficient mapping of disciplined approximate programming onto hardware. We describe an ISA extension that provides approximate operations and storage, which give the hardware freedom to save energy at the cost of accuracy. We then propose Truffle, a microarchitecture design that efficiently supports the ISA extensions. The basis of our design is dual-voltage operation, with a high voltage for precise operations and a low voltage for approximate operations. The key aspect of the microarchitecture is its dependence on the instruction stream to determine when to use the low voltage. We evaluate the power savings potential of in-order and out-of-order Truffle configurations and explore the resulting quality of service degradation. We evaluate several applications and demonstrate energy savings up to 43%. <s> BIB002 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Approximate memory elements <s> Memories today expose an all-or-nothing correctness model that incurs significant costs in performance, energy, area, and design complexity. But not all applications need high-precision storage for all of their data structures all of the time. This paper proposes mechanisms that enable applications to store data approximately and shows that doing so can improve the performance, lifetime, or density of solid-state memories. We propose two mechanisms. The first allows errors in multi-level cells by reducing the number of programming pulses used to write them. The second mechanism mitigates wear-out failures and extends memory endurance by mapping approximate data onto blocks that have exhausted their hardware error correction resources. Simulations show that reduced-precision writes in multi-level phase-change memory cells can be 1.7× faster on average and using failed blocks can improve array lifetime by 23% on average with quality loss under 10%. <s> BIB003 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Approximate memory elements <s> Approximate computing explores opportunities that emerge when applications can tolerate error or inexactness. These applications, which range from multimedia processing to machine learning, operate on inherently noisy and imprecise data. We can trade-off some loss in output value integrity for improved processor performance and energy-efficiency. As memory accesses consume substantial latency and energy, we explore load value approximation, a micro architectural technique to learn value patterns and generate approximations for the data. The processor uses these approximate data values to continue executing without incurring the high cost of accessing memory, removing load instructions from the critical path. Load value approximation can also inhibit approximated loads from accessing memory, resulting in energy savings. On a range of PARSEC workloads, we observe up to 28.6% speedup (8.5% on average) and 44.1% energy savings (12.6% on average), while maintaining low output error. By exploiting the approximate nature of applications, we draw closer to the ideal latency and energy of accessing memory. <s> BIB004 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Approximate memory elements <s> This paper demonstrates how to utilize the inherent error resilience of a wide range of applications to mitigate the memory wall -- the discrepancy between core and memory speed. We define a new microarchitecturally-triggered approximation technique called rollback-free value prediction. This technique predicts the value of safe-to-approximate loads when they miss in the cache without tracking mispredictions or requiring costly recovery from misspeculations. This technique mitigates the memory wall by allowing the core to continue computation without stalling for long-latency memory accesses. Our detailed study of the quality trade-offs shows that with a modern out-of-order processor, average 8% (up to 19%) performance improvement is possible with 0.8% (up to 1.8%) average quality loss on an approximable subset of SPEC CPU 2000/2006. <s> BIB005 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Approximate memory elements <s> Modern processors contain large last level caches (LLCs) that consume substantial energy and area yet are imperative for high performance. Cache designs have improved dramatically by considering reference locality. Data values are also a source of optimization. Compression and deduplication exploit data values to use cache storage more efficiently resulting in smaller caches without sacrificing performance. In multi-megabyte LLCs, many identical or similar values may be cached across multiple blocks simultaneously. This redundancy effectively wastes cache capacity. We observe that a large fraction of cache values exhibit approximate similarity. More specifically, values across cache blocks are not identical but are similar. Coupled with approximate computing which observes that some applications can tolerate error or inexactness, we leverage approximate similarity to design a novel LLC architecture: the Doppelganger cache. The Doppelganger cache associates the tags of multiple similar blocks with a single data array entry to reduce the amount of data stored. Our design achieves 1.55×, 2.55× and 1.41 × reductions in LLC area, dynamic energy and leakage energy without harming performance nor incurring high application error. <s> BIB006 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Approximate memory elements <s> Spintronic memories are promising candidates for future on-chip storage due to their high density, non-volatility and near-zero leakage. However, the energy consumed by read and write operations presents a major challenge to their use as energy-efficient on-chip memory. Leveraging the ability of many applications to tolerate impreciseness in their underlying computations and data, we explore approximate storage as a new approach to improving the energy-efficiency of spintronic memories. We identify and characterize mechanisms in STT-MRAM bit-cells that provide favorable energy-quality trade-o?s, i.e., disproportionate energy improvements at the cost of small probabilities of read/write failures. Based on these mechanisms, we design a quality-configurable memory array in which data can be stored to varying levels of accuracy based on application requirements. We integrate the quality-configurable array as a scratchpad in the memory hierarchy of a programmable vector processor and expose it to software by introducing quality-aware load/store instructions within the ISA. We evaluate the energy benefits of our proposal using a device-to-architecture modeling framework and demonstrate 40% and 19.5% improvement in memory energy and overall application energy respectively, for negligible (< 0.5%) quality loss across a suite of recognition and vision applications. <s> BIB007 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Approximate memory elements <s> This paper proposes tailoring image encoding for an approximate storage substrate. We demonstrate that indiscriminately storing encoded images in approximate memory generates unacceptable and uncontrollable quality degradation. The key finding is that errors in the encoded bit streams have non-uniform impact on the decoded image quality. We develop a methodology to determine the relative importance of encoded bits and store them in an approximate storage substrate. The storage cells are optimized to reduce error rate via biasing and are tuned to meet the desired reliability requirement via selective error correction. In a case study with the progressive transform codec (PTC), a precursor to JPEG XR, the proposed approximate image storage system exhibits a 2.7x increase in density of pixels per silicon volume under bounded error rates, and this achievement is additive to the storage savings of PTC compression. <s> BIB008 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Approximate memory elements <s> The cost of moving and storing data is still a fundamental concern for computer architects. Inefficient handling of data can be attributed to conventional architectures being oblivious to the nature of the values that these data bits carry. We observe the phenomenon of spatio-value similarity, where data elements that are approximately similar in value exhibit spatial regularity in memory. This is inherent to 1) the data values of real-world applications, and 2) the way we store data structures in memory. We propose the Bunker Cache, a design that maps similar data to the same cache storage location based solely on their memory address, sacrificing some application quality loss for greater efficiency. The Bunker Cache enables performance gains (ranging from 1.08x to 1.19x) via reduced cache misses and energy savings (ranging from 1.18x to 1.39x) via reduced off-chip memory accesses and lower cache storage requirements. The Bunker Cache requires only modest changes to cache indexing hardware, integrating easily into commodity systems. <s> BIB009
Memory architectures that trade resource usage for correctness permit the value that is read from a given memory address to differ from the most recent value that was written. The traditional view of memory elements assumes that every memory access pair consisting of a write followed by a subsequent read operation, applied to a input I, results in the same read result for a given write value. In contrast, approximate memory elements may perform non-identity transformations of the input I. The benefits of doing so include reduced read/write latency, reduced read/write access energy, fewer accesses to memory, increased read/write bandwidth, increased capacity BIB008  BIB003 , improved endurance BIB003 , and reduced leakage power dissipation BIB001 . These techniques have been applied to memory components ranging from CPU registers BIB002 , caches BIB002 BIB009 BIB006 BIB004 , main memory BIB001 , to flash storage BIB008  BIB003 . One method for trading resource usage for correctness in memories is to predict memory values instead of performing an actual read operation. For example, on the occurrence of a cache miss, load value approximation (LVA) BIB004 BIB005 provides predicted data values to a processor which may differ from the correct values in main memory. Doing so hides cache miss latency and thereby reduces the average memory access time at the expense of having data values in the cache that differ from what they would be had they been faithfully loaded from main memory. The correct values in main memory may subsequently be read from memory to train the predictor and improve its accuracy, or the main memory access may be skipped entirely to save energy. Conventional value prediction considers any execution relying on predicted values speculative and provides expensive microarchitectural machinery to roll back execution in the case of a mismatch between the predicted and actual values. LVA, by contrast, allows imperfect predictions, trading correctness of values in the cache for reduced micro-architectural complexity and reduced memory latency. Several memory technologies expose circuit-level mechanisms to trade accuracy for reduction in latency or access energy (or both). For example, multi-level solid-state memories perform write operations iteratively, until the written value is in the desired range. By reducing the number of write iterations, approximate writes BIB003 significantly reduce the latency and energy of write operations, increasing write bandwidth as a side effect, at the expense of reduced data retention. In spintronic memories, such as STT-MRAM, reducing the read current magnitude can reduce energy of read operations at the expense of accuracy of the content being read. In contrast, significantly increasing the read current magnitude reduces the read pulse duration, decreasing the read latency while potentially disturbing the written content with noise. Such mechanisms can be leveraged at the architectural level through dedicated instructions for imprecise loads and stores BIB007 . The correctness of values obtained from memories can also be traded for an increase in effective storage capacity. One way to achieve this is to avoid storing similar data multiple times. For example, storing similar data in the same cache line can save on cache space in situations when substituting a data item for a similar one still yields acceptable application quality BIB009 BIB006 . Another way to trade errors for capacity is through deliberate reduction in storage resources dedicated to errorcorrection BIB008  . By providing weaker error-correction schemes for data whose accuracy does not have a critical impact on the output quality, significant storage savings have been demonstrated in the case of encoded images and videos BIB008  . For volatile memory technologies, such as SRAM and DRAM, voltage scaling approaches can be used to reduce the static energy at the expense of faults, observed as bit flips BIB002 . In the case of DRAM, the energy needed to retain data can be further reduced by less frequently refreshing the DRAM rows that contain data whose incorrectness applications can tolerate, compared to the rows that applications require to remain correct BIB001 . In solid-state memories, mapping data that applications can tolerate to be incorrect onto blocks that have exhausted their hardware error correction resources can significantly extend endurance BIB003 .