Search

Transformer models gain popularity because of their superior inference accuracy and inference throughput. However, the transformer is computation-intensive, causing a long inference time. The existing works on transformer inference acceleration have limitations caused by either the modification of transformer architectures or the need of specialized hardware. In this paper, we identify the opportunities of using memoization to accelerate the self-attention mechanism in transformers without the above limitations. Built upon a unique observation that there is rich similarity in attention computation across inference sequences, we build a memoization database that leverages the emerging big memory system. We introduce a novel embedding technique to find semantically similar inputs to identify computation similarity. We also introduce a series of techniques such as memory mapping and selective memoization to avoid memory copy and unnecessary overhead. We enable 22% inference-latency reduction on average (up to 68%) with negligible loss in inference accuracy.

Magnetic random-access memory (MRAM) is a promising memory technology due to its high density, non-volatility, and high endurance. However, achieving high memory fidelity incurs significant write-energy costs, which should be reduced for large-scale deployment of MRAMs. In this paper, we formulate a \emph{biconvex} optimization problem to optimize write fidelity given energy and latency constraints. The basic idea is to allocate non-uniform write pulses depending on the importance of each bit position. The fidelity measure we consider is mean squared error (MSE), for which we optimize write pulses via \emph{alternating convex search (ACS)}. By using Karush-Kuhn-Tucker (KKT) conditions, we derive analytic solutions and propose an \emph{iterative water-filling-type} algorithm by leveraging the analytic solutions. Hence, the proposed iterative water-filling algorithm is computationally more efficient than the original ACS while their solutions are identical. Although the original ACS and the proposed iterative water-filling algorithm do not guarantee global optimality, the MSEs obtained by the proposed algorithm are comparable to the MSEs by complicated global nonlinear programming solvers. Furthermore, we prove that the proposed algorithm can reduce the MSE exponentially with the number of bits per word. For an 8-bit accessed word, the proposed algorithm reduces the MSE by a factor of 21. We also evaluate the proposed algorithm for MNIST dataset classification supposing that the model parameters of deep neural networks are stored in MRAMs. The numerical results show that the optimized write pulses can achieve \SI{40}{\%} write energy reduction for a given classification accuracy., Comment: arXiv admin note: substantial text overlap with arXiv:2001.03803

The min-entropy is a widely used metric to quantify the randomness of generated random numbers in cryptographic applications; it measures the difficulty of guessing the most likely output. An important min-entropy estimator is the compression estimator of NIST Special Publication (SP) 800-90B, which relies on Maurer's universal test. In this paper, we propose two kinds of min-entropy estimators to improve computational complexity and estimation accuracy by leveraging two variations of Maurer's test: Coron's test (for Shannon entropy) and Kim's test (for Renyi entropy). First, we propose a min-entropy estimator based on Coron's test. It is computationally more efficient than the compression estimator while maintaining the estimation accuracy. The secondly proposed estimator relies on Kim's test that computes the Renyi entropy. This estimator improves estimation accuracy as well as computational complexity. We analytically characterize the bias-variance tradeoff, which depends on the order of Renyi entropy. By taking into account this tradeoff, we observe that the order of two is a proper assignment and focus on the min-entropy estimation based on the collision entropy (i.e., Renyi entropy of order two). The min-entropy estimation from the collision entropy can be described by a closed-form solution, whereas both the compression estimator and the proposed estimator based on Coron's test do not have closed-form solutions. By leveraging the closed-form solution, we also propose a lightweight estimator that processes data samples in an online manner. Numerical evaluations demonstrate that the first proposed estimator achieves the same accuracy as the compression estimator with much less computation. The proposed estimator based on the collision entropy can even improve the accuracy and reduce the computational complexity.

Magnetic random-access memory (MRAM) is a promising memory technology due to its high density, non-volatility, and high endurance. However, achieving high memory fidelity incurs significant write-energy costs, which should be reduced for large-scale deployment of MRAMs. In this paper, we formulate an optimization problem for maximizing the memory fidelity given energy constraints, and propose a biconvex optimization approach to solve it. The basic idea is to allocate non-uniform write pulses depending on the importance of each bit position. The fidelity measure we consider is minimum mean squared error (MSE), for which we propose an iterative water-filling algorithm. Although the iterative algorithm does not guarantee global optimality, we can choose a proper starting point that decreases the MSE exponentially and guarantees fast convergence. For an 8-bit accessed word, the proposed algorithm reduces the MSE by a factor of 21.

Refresh is an important operation to prevent loss of data in dynamic random-access memory (DRAM). However, frequent refresh operations incur considerable power consumption and degrade system performance. Refresh power cost is especially significant in high-capacity memory devices and battery-powered edge/mobile applications. In this paper, we propose a principled approach to optimizing the refresh power allocation. Given a model for the bit error rate dependence on power, we formulate a convex optimization problem to minimize the word mean squared error for a refresh power constraint; hence we can guarantee the optimality of the obtained refresh power allocations. In addition, we provide an integer programming problem to optimize the discrete refresh interval assignments. For an 8-bit accessed word, numerical results show that the optimized nonuniform refresh intervals reduce the refresh power by 29% at a peak signal-to-noise ratio of 50dB compared to the uniform assignment., Comment: 6 pages

We study the design of storage-efficient algorithms for emulating atomic shared memory over an asynchronous, distributed message-passing system. Our first algorithm is an atomic single-writer multi-reader algorithm based on a novel erasure-coding technique, termed \emph{multi-version code}. Next, we propose an extension of our single-writer algorithm to a multi-writer multi-reader environment. Our second algorithm combines replication and multi-version code, and is suitable in situations where we expect a large number of concurrent writes. Moreover, when the number of concurrent writes is bounded, we propose a simplified variant of the second algorithm that has a simple structure similar to the single-writer algorithm. Let $N$ be the number of servers, and the shared memory variable be of size 1 unit. Our algorithms have the following properties: (i) The write operation terminates if the number of server failures is bounded by a parameter $f$. The algorithms also guarantee the termination of the read as long as the number of writes concurrent with the read is smaller than a design parameter $\nu$, and the number of server failures is bounded by $f$. (ii) The overall storage size for the first algorithm, and the steady-state storage size for the second algorithm, are all $N/\lceil \frac{N-2f}{\nu} \rceil$ units. Moreover, our simplified variant of the second algorithm achieves the worst-case storage cost of $N/\lceil \frac{N-2f}{\nu} \rceil$, asymptotically matching a lower bound by Cadambe et al. for $N \gg f, \nu \le f+1$. (iii) The write and read operations only consist of a small number (2 to 3) of communication rounds. (iv) For all algorithms, the server maintains a simple data structure. A server only needs to store the information associated with the latest value it observes, similar to replication-based algorithms.

Modern Operating Systems are typically POSIX-compliant. The system calls are the fundamental layer of interaction between user-space applications and the OS kernel and its implementation of fundamental abstractions and primitives used in modern computing. The next generation of NVM/SCM memory raises critical questions about the efficiency of modern OS architecture. This paper investigates how the POSIX API drives performance for a system with NVM/SCM memory. We show that OS and metadata related system calls represent the most important area of optimization. However, the synchronization related system calls (poll(), futex(), wait4()) are the most time-consuming overhead that even a RAMdisk platform fails to eliminate. Attempting to preserve the POSIX-based approach will likely result in fundamental inefficiencies for any future applications of NVM/SCM memory.

Maximum-distance separable (MDS) array codes with high rate and an optimal repair property were introduced recently. These codes could be applied in distributed storage systems, where they minimize the communication and disk access required for the recovery of failed nodes. However, the encoding and decoding algorithms of the proposed codes use arithmetic over finite fields of order greater than 2, which could result in a complex implementation. In this work, we present a construction of 2-parity MDS array codes, that allow for optimal repair of a failed information node using XOR operations only. The reduction of the field order is achieved by allowing more parity bits to be updated when a single information bit is being changed by the user., Comment: 5 pages, submitted to ISIT 2013