Given the recent success of Deep Learning applied to a variety of single tasks, it is natural to consider more human-realistic settings. Perhaps the most difficult of these settings is that of continual lifelong learning, where the model must learn online over a continuous stream of non-stationary data. A successful continual lifelong learning system must have three key capabilities: it must learn and adapt over time, it must not forget what it has learned, and it must be efficient in both training time and memory. Recent techniques have focused their efforts primarily on the first two capabilities while questions of efficiency remain largely unexplored. In this paper, we consider the problem of efficient and effective storage of experiences over very large time-frames. In particular we consider the case where typical experiences are O(n) bits and memories are limited to O(k) bits for k

Many storage channels admit reading and rewriting of the content at a given cost. We consider rewritable channels with a hidden state which models the unknown characteristics of the memory cell. In addition to mitigating the effect of write noise, rewrites can help the write controller obtain a better estimate of the hidden state. The paper has two contributions. The first is a lower bound on the capacity of a general rewritable channel with hidden state. The lower bound is obtained using a coding scheme that combines Gelfand-Pinsker coding with superposition coding. The rewritable AWGN channel is discussed as an example. The second contribution is a simple coding scheme for a rewritable channel where the write noise and hidden state are both uniformly distributed. It is shown that this scheme is asymptotically optimal as the number of rewrites gets large.

In this paper, we consider orthogonal multiple access coding schemes, where correlated sources are encoded in a distributed fashion and transmitted through additive white Gaussian noise (AWGN) channels to an access point (AP). At the AP, component decoders, which are associated with the source encoders, iteratively exchange soft information by taking into account the source correlation. The first goal of this paper is to investigate the ultimate achievable performance limits in terms of a multi-dimensional feasible region in the space of channel parameters, deriving insights on the impact of the number of sources. The second goal is the design of pragmatic schemes, where the sources use “off-the-shelf” channel codes. In order to analyze the performance of given coding schemes, we propose an extrinsic information transfer-based approach, which allows to determine the corresponding multi-dimensional feasible regions. On the basis of the proposed analytical framework, the performance of pragmatic coded schemes, based on serially concatenated convolutional codes, is discussed.

A number of modern storage technologies, when written to, exhibit substantial variability in the outcome of a write action. It is possible to mitigate the effect of the write uncertainty through the use of a feedback loop that rewrites the memory whenever judged necessary, in effect reshaping the write noise. This scheme highlights a tradeoff between the storage capacity of the memory and the cost of writing to it, measured for example in the number of rewrites. We have developed the model of a rewritable channel to provide an explicit form for this tradeoff and study other performance characteristics of such memories. In this paper, we describe some initial results on the information-theoretic analysis of the rewritable channel. We first consider the problem of determining the capacity of this channel with input cost constraints, and obtain a variety of results from which we extract insights that we believe are of value to memory designers. Our results include an upper bound on capacity of the form log (Γκ), where Γ is a constant that can be easily calculated from the channel's statistics and κ is an average cost parameter. We also provide a lower bound on capacity with a similar form. We analyze the particular case of uniform write noise in detail, obtaining a closed form expression for the capacity-cost tradeoff for all possible cost parameters. We explore this formula from the capacity per unit cost perspective and establish that in order to achieve optimal energy and memory-wear per bit, it is sometimes strictly better to take advantage of the rewriting capability as opposed to writing only once; this observation has significant practical implications. We also include a discussion of the relevance of our work to real emerging memory technologies.

In wireless networks, base stations are responsible for operating on large amounts of traffic at high speed rates. With the advent of new standards, as 4G, further pressure is put in the hardware requirements to satisfy speeds of up to 1 Gbps. In this work, we study the applicability and potential benefits of the IBM PowerEN processor (a multi-core, massively multithreaded platform) in the realm of base stations for the 3G and 4G standards. The approach involves exploiting the throughput computation capabilities of the PowerEN processor, replacing the bus-attached special-function accelerators with a layer of in-line universal acceleration support, incorporated within the cores. A key feature of this in-line accelerator is a bank-based very-large register file, with embedded SIMD support. This processor-in-regfile (PIR) strategy is implemented as local computation elements (LCEs) attached to each bank, overcoming the limited number of register file ports. Because each LCE is a SIMD computation element, and all of them can proceed concurrently, the PIR approach constitutes a highly-parallel super-wide-SIMD device. To target a broad spectrum of applications for base stations, we also consider a PIR-based architecture built upon reconfigurable LCEs. In this paper, we evaluate the in-line universal accelerator and the PIR strategy focusing on two specific applications for base stations: FFT and Turbo Decoding.

Phase Change Memory (PCM) is a promising technology for building future main memory systems. A prominent characteristic of PCM is that it has write latency much higher than read latency. Servicing such slow writes causes significant contention for read requests. For our baseline PCM system, the slow writes increase the effective read latency by almost 2X, causing significant performance degradation. This paper alleviates the problem of slow writes by exploiting the fundamental property of PCM devices that writes are slow only in one direction (SET operation) and are almost as fast as reads in the other direction (RESET operation). Therefore, a write operation to a line in which all memory cells have been SET prior to the write, will incur much lower latency. We propose PreSET, an architectural technique that leverages this property to pro-actively SET all the bits in a given memory line well in advance of the anticipated write to that memory line. Our proposed design initiates a PreSET request for a memory line as soon as that line becomes dirty in the cache, thereby allowing a large window of time for the PreSET operation to complete. Our evaluations show that PreSET is more effective and incurs lower storage overhead than previously proposed write cancellation techniques. We also describe static and dynamic throttling schemes to limit the rate of PreSET operations. Our proposal reduces effective read latency from 982 cycles to 594 cycles and increases system performance by 34%, while improving the energy-delay-product by 25%.

Many storage channels admit reading and rewriting of the content at a given cost. We consider rewritable channels with uniform write noise and a hidden state which models the unknown characteristics of the memory cell. In addition to mitigating the effect of the write noise, rewrites can help the write controller obtain a better estimate of the hidden state. We present two coding strategies, each of which yields a lower bound on the rewrite capacity. We show that the second strategy is asymptotically optimal as the number of rewrites gets large.

Phase Change Memory (PCM) may become a viable alternative for the design of main memory systems in the next few years. However PCM suffers from limited write endurance. Therefore future adoption of PCM as a technology for main memory will depend on the availability of practical solutions for wear leveling that avoids uneven usage especially in the presence of potentially malicious users. First generation wear leveling algorithms were designed for typical workloads and have significantly reduced lifetime under malicious access patterns that try to write to the same line continuously. Secure wear leveling algorithms were recently proposed. They can handle such malicious attacks, but require that wear leveling is done at a rate that is orders of magnitude higher than what is sufficient for typical applications, thereby incurring significantly high write overhead, potentially impairing overall performance system. This paper proposes a practical wear-leveling framework that can provide years of lifetime under attacks while still incurring negligible (<;1%) write overhead for typical applications. It uses a simple and novel Online Attack Detector circuit to adapt the rate of wear leveling depending on the properties of the memory reference stream, thereby obtaining the best of both worlds - low overhead for typical applications and years of lifetime under attacks. The proposed attack detector requires a storage overhead of 68 bytes, is effective at estimating the severity of attacks, is applicable to a wide variety of wear leveling algorithms, and reduces the write overhead of several recently proposed wear leveling algorithms by 16x-128x. The paradigm of online attack detection enables other preventive actions as well.

Phase Change Memory (PCM) is emerging as a promising technology to build large-scale main memory systems in a cost-effective manner. A characteristic of PCM is that it has write latency much higher than read latency. A higher write latency can typically be tolerated using buffers. However, once a write request is scheduled for service to a bank, it can still cause increased latency for later arriving read requests to the same bank. We show that for the baseline PCM system with read-priority scheduling, the write requests increase the effective read latency to 2.3x (on average), causing significant performance degradation. To reduce the read latency of PCM devices under such scenarios, we propose adaptive Write Cancellation policies. Such policies can abort the processing of a scheduled write requests if a read request arrives to the same bank within a predetermined period. We also propose Write Pausing, which exploits the iterative write algorithms used in PCM to pause at the end of each write iteration to service any pending reads. For the baseline system, the proposed technique removes 75% of the latency increase incurred by read requests and improves overall system performance by 46% (on average), while requiring negligible hardware and simple extensions to PCM controller.

We introduce a simple communication-theoretic model for phase-change memory (PCM), based on empirical observations. Our modeling effort is focused on capturing the effects of resistance drift, which is believed to be one of the major obstacles to achieving high bit/cell densities in PCM. The model is used to estimate how the information theoretic storage capacity of PCM evolves as the time gap between a write and its subsequent read widens. We use our model to evaluate the performance of simple modulation and detection schemes, also considering the use of trellis coded modulation (TCM). Our evaluation of these strategies shows that the use of TCM provides several benefits, including a significant increase in retention time, i.e., the expected maximum amount of storage time before which the stored data can be reliably retrieved.

We consider the problem of information storage in multilevel heterogeneous memories, where different cells can support different data level-sets. Such heterogeneity arises due to variability in the physical cell characteristics in emerging technologies such as Phase Change Memory (PCM) technology, which is our specific motivation. We show that the heterogeneous memory problem can be formulated in terms of the information-theoretic `Channel Coding with Side-Information at Transmitter' (CSIT) paradigm. We present a binary decomposition of the problem, and show that this decomposition allows for simple binary code constructions. We discuss one such code-construction based on binary Luby Transform (LT) code matrices. We present simulation results using cell variability data collected from a PCM test array, and show that the proposed approach can yield a significant advantage in storage capacity.

Phase Change Memory (PCM) is emerging as a scalable and power efficient technology to architect future main memory systems. The scalability of PCM is enhanced by the property that PCM devices can store multiple bits per cell. While such Multi-Level Cell (MLC) devices can offer high density, this benefit comes at the expense of increased read latency, which can cause significant performance degradation. This paper proposes Morphable Memory System (MMS), a robust architecture for efficiently incorporating MLC PCM devices in main memory. MMS is based on observation that memory requirement varies between workloads, and systems are typically over-provisioned in terms of memory capacity. So, during a phase of low memory usage, some of the MLC devices can be operated at fewer bits per cell to obtain lower latency. When the workload requires full memory capacity, these devices can be restored to high density MLC operation to have full main-memory capacity. We provide the runtime monitors, the hardware-OS interface, and the detailed mechanism for implementing MMS. Our evaluations on an 8-core 8GB MLC PCM-based system show that MMS provides, on average, low latency access for 95% of all memory requests, thereby improving overall system performance by 40%.

We present a closed form expression for the capacity of the uniform noise rewritable channel with average write cost and a constraint on the input range. We show the existence of a critical cost κ0such that for all costs κ ≥ κ0, the capacity/cost tradeoff is given by an offset added to the logarithm of the cost. Assuming κ0> 1, for 1 ≤ κ0the capacity/cost tradeoff grows faster than a logarithm.

We study binary Content Addressable Memories (CAMs) that employ a resistive element to store content. A CAM has a match line for every word stored which is sensed in order to determine a match/no match condition. We show how simple, low redundancy coding techniques can dramatically improve the ability to differentiate a match from a mismatch, effectively allowing a CAM design that stores nearly twice as many bits in the same memory as a competing design that stores each bit and its complement. The theory of coding for asymmetric errors is relevant in this problem; we rely on it to prove that ⌊n/2⌋ out of n constant weight codes are optimal for sensing.

We present a class of algorithms for encoding data in memories with stuck cells. These algorithms rely on earlier code constructions termed cyclic Partitioned Linear Block Codes. For the corresponding q-ary BCH-like codes for u stucks in a codeword of length n, our encoding algorithm has complexity O((u logqn)2) Fqoperations, which we will show compares favorably to a generic approach based on Gaussian elimination. The computational complexity improvements are realized by taking advantage of the algebraic structure of cyclic codes for stucks. The algorithms are also applicable to cyclic codes for both stucks and errors.

We consider storage channels that admit optional reading and rewriting of the content at a given cost. This is a general class of channels that models many nonvolatile memories. We present recent results on such rewritable channels with constraints on both the maximum and the average number of atomic rewrite iterations. We derive a general lower capacity bound for rewritable storage channels impaired by additive noise. For the special case of uniform noise, we present tight upper and lower capacity bounds and suggest some capacity-achieving coding techniques.

The block erase requirement in NAND Flash devices leads to the need for garbage collection. Garbage collection results in write amplification, that is, to an increase in the number of physical page programming operations. Write amplification adversely impacts the limited lifetime of a NAND Flash device, and can add significant system overhead unless a large spare factor is maintained. This paper proposes a NAND Flash system which uses multi-write coding to reduce write amplification. Multi-write coding allows a NAND Flash page to be written more than once without requiring an intervening block erase. We present a novel two-write coding technique based on enumerative coding, which achieves linear coding rates with low computational complexity. The proposed technique also seeks to minimize memory wear by reducing the number of programmed cells per page write. We describe a system which uses lossless data compression in conjunction with multi-write coding, and show through simulations that the proposed system has significantly reduced write amplification and memory wear.

We present some recent results on rewritable channels, that is, storage channels that admit optional reading and rewriting of the content at a given cost. This is a general class of channels that models many nonvolatile memories. We focus on the storage capacity of rewritable channels affected by data-dependent noise. We prove tight upper and lower bounds on the storage capacity of a simple yet significant channel model and suggest some simple capacity-achieving coding techniques. Lower bounds on the storage capacity of Gaussian rewritable channels with data-dependent noise are also shown.

We study memories capable of storing multiple bits per memory cell, with the property that certain state transitions “wear” the cell. We introduce a model that is relevant for Phase Change Memory, a promising emerging nonvolatile memory technology that exhibits limitations in the number of particular write actions that one may apply to a cell before rendering it unusable. We exploit the theory of Write Efficient Memories to derive a closed form expression for the storage capacity/lifetime fundamental tradeoff for this model. We then present families of codes specialized to distinct ranges for the target lifetimes, covering the full range from moderate redundancy to an arbitrarily large lifetime increase. These codes have low implementation complexity and remarkably good performance; for example in an 8 level cell we can increase the lifetime of a memory by a factor of ten while sacrificing only 2/3 of the uncoded storage capacity of the memory.

Phase Change Memory (PCM) is an emerging memory technology that can increase main memory capacity in a cost-effective and power-efficient manner. However, PCM cells can endure only a maximum of 107 - 108 writes, making a PCM based system have a lifetime of only a few years under ideal conditions. Furthermore, we show that non-uniformity in writes to different cells reduces the achievable lifetime of PCM system by 20x. Writes to PCM cells can be made uniform with Wear-Leveling. Unfortunately, existing wear-leveling techniques require large storage tables and indirection, resulting in significant area and latency overheads.

In this paper, we present a novel pragmatic approach, referred to as detection by multiple trellises, to perform trellis-based detection over realistic channels. More precisely, we consider channels with unknown parameters and apply the concept of detection by multiple trellises to forward-backward (FB) algorithms. The key idea of our approach consists, first, of properly quantizing the channel parameters and, then, considering replication of coherent FB algorithms operating on parallel trellises, one per hypothetical quantized value. In order to make the receiver robust against a possibly time-varying channel parameters, the proposed soft-output algorithms perform a proper "manipulation" of the forward and backward metrics computed by the parallel FB algorithms at regularly spaced trellis steps. We consider two significant examples of application: detection over (i) phase-uncertain channels and (ii) fading channels. The performance of the proposed algorithms is investigated considering differentially encoded (DE) quaternary phase shift keying (QPSK) and iterative detection schemes based on low-density parity-check (LDPC) codes. Besides having a low complexity, the proposed soft-output algorithms turn out to be robust, flexible, blind, in the sense that no knowledge of the channel parameter statistics is required, and highly parallelizable, as it is desirable in high-throughput future wireless communication systems.

In this paper, we investigate the ultimate performance limits, in terms of achievable information rate (IR), of communication systems impaired by impulse noise. We compare single carrier (SC) and multi-carrier (MC) transmission systems employing quadrature amplitude modulation (QAM) formats. More precisely, we consider SC schemes with coded modulations and MC systems based on orthogonal frequency division modulation (OFDM). For the MC schemes, we introduce a theoretically equivalent channel model which makes the computation of the IR feasible. This simple channel model will be referred to as interleaved MC. We show that, in the presence of impulse noise and except for systems operating at very high spectral efficiency, the IR of MC schemes is lower than that of SC schemes. More precisely, use of MC schemes may lead to an unavoidable fundamental loss with respect to SC schemes at typical coding rates, whereas MC schemes are to be preferred for very high coding rates or in uncoded systems. These results hold for additive white Gaussian noise (AWGN) and dispersive channels, either considering plain OFDM or MC schemes employing water-filling and bit-loading algorithms. In order to validate our theoretical results, we also obtain the bit error rate (BER) performance of SC and MC schemes through Monte Carlo simulations. A few trellis-coded modulation (TCM) and low-density parity-check (LDPC)-coded schemes are considered. The obtained SNR loss in the BER curves between the AWGN and impulse noise channels matches well with the corresponding IR gap.

In this letter, we discuss the performance of low-density parity-check (LDPC) codes on memoryless channels. Using a recently proposed analysis technique based on extrinsic information transfer (EXIT) charts, we present an interpretation of the known fact that the bit-error rate (BER) performance of an ensemble of LDPC codes shows little dependence on the specific memoryless channel. This result has been partially observed in the literature for symmetric channels and is here extended to asymmetric channels. We conjecture and demonstrate that the performance of an ensemble of LDPC codes depends primarily and solely on the mutual information (MI) between the input and the output of the channel. As a validation of this conjecture, we compare the performance of a few LDPC codes with various rates for five representative memoryless (both symmetric and asymmetric) channels, obtaining results in excellent agreement with the EXIT chart-based prediction

In this paper, we consider the asymptotic (for high signal-to-noise ratio, SNR) behavior of the mutual information (MI) between the input and the output of a two-dimensional additive white Gaussian noise (AWGN) channel with continuous input distributions. In particular, the obtained results apply to modulation formats with dense constellations. The accuracy of the presented results is the higher the denser are the considered constellations. We find two simple expressions relating the MI of the considered continuous input distribution, as a function of the SNR, to that of the Gaussian input distribution, in one- and two-dimensional cases, respectively.

In this paper, we present a novel class of simple soft-input soft-output (SISO) detection algorithms for transmission over phase-uncertain channels. In order to limit the complexity, the set of possible phase values (i.e., the interval [0,2pi)) is properly quantized. We then use a forward-backward (FB) algorithm in correspondence to each quantized phase value. The forward and backward metrics computed by the different FB algorithms are properly combined to make the receiver robust against the time-varying phase. We apply the proposed SISO algorithms to perform joint detection and decoding of serially concatenated low-density parity-check (LDPC) codes and differentially encoded (DE) quaternary phase shift keying (QPSK), transmitted over a phase-uncertain channel. As a validation of the effectiveness of the proposed algorithms, we show that the performance loss with respect to that of the corresponding ideal (i.e., perfectly coherent) system is limited. Besides having a limited complexity, the proposed SISO algorithms are blind, i.e., no knowledge of the channel phase statistics is required, and highly parallelizable, as desirable in high-throughput future wireless communication systems

In this paper, we consider serially concatenated schemes with outer novel and efficient low-density parity-check (LDPC) codes and inner modulations effective against channel impairments. With a pragmatic approach, we show how to design LDPC codes tailored for simple and robust modulation formats, such as differentially encoded (DE) modulations. The LDPC codes are optimized through the use of a recently proposed analysis technique based on extrinsic information transfer (EXIT) charts. In particular, we optimize, through a "clever" random walk in the parametric space, the degree distributions of the outer LDPC codes, obtaining significant insights on the impact of such distributions on the performance of the proposed concatenated schemes. The optimization is carried out for transmission over both the additive white Gaussian noise channel and a noncoherent channel. The performance predicted by the EXIT chart-based optimization is confirmed by results obtained via computer simulations, considering phase-shift keying and quadrature amplitude modulation at the transmitter side, and iterative demodulation/decoding at the receiver side. The significance of the proposed optimized design of LDPC-coded schemes with DE modulations is validated by the fact that standard nonoptimized LDPC codes perform poorly when used together with inner DE modulations.