With the end of Moore's Law, database architects are turning to hardware accelerators to offload computationally intensive tasks from the CPU. In this paper, we show that accelerators can facilitate far more than just computation: they enable algorithms and data structures that lavishly expand computation in order to optimize for disparate cost metrics. We introduce the Pliops Extreme Data Processor (XDP), a novel storage engine implemented from the ground up using customized hardware. At its core, XDP consists of an accelerated hash table to index the data in storage using less memory and fewer storage accesses for queries than the best alternative. XDP also employs an accelerated compressor, a capacitor, and a lock-free RAID sub-system to minimize storage space and recovery time while minimizing performance penalties. As a result, XDP overcomes cost contentions that have so far been inescapable.

In this paper, we extend the Blahut-Arimoto algorithm for maximizing Massey's directed information. The algorithm can be used for estimating the capacity of channels with delayed feedback, where the feedback is a deterministic function of the output. In order to maximize the directed information, we apply the ideas from the regular Blahut-Arimoto algorithm, i.e., the alternating maximization procedure, to our new problem. We provide both upper and lower bound sequences that converge to the optimum global value. Our main insight in this paper is that in order to find the maximum of the directed information over a causal conditioning probability mass function, one can use a backward index time maximization combined with the alternating maximization procedure. We give a detailed description of the algorithm, showing its complexity and the memory needed, and present several numerical examples.

In this paper, we consider the rate distortion problem of discrete-time, ergodic, and stationary sources with feed forward at the receiver. We derive a sequence of achievable and computable rates that converge to the feed-forward rate distortion. We show that for ergodic and stationary sources, the rate Rn(D) = 1/n min IX̂n→ Xn) is achievable for anyn, where the minimization is performed over the transition conditioning probability p(x̂n|xn) such that E [d(Xn, X̂n] ≤D. We also show that the limit of Rn(D) exists and is the feed-forward rate distortion. We follow Gallager's proof where there is no feed forward and, with appropriate modification, obtain our result. We provide an algorithm for calculating Rn(D) using the alternating minimization procedure and present several numerical examples. We also present a dual form for the optimization of Rn(D) and transform it into a geometric programming problem.

THIS PAPER IS ELIGIBLE FOR THE STUDENT PAPER AWARD. Consider the rate distortion problem of discrete-time, ergodic, and stationary sources with feed forward at the receiver. We derive a sequence of achievable and computable rates that converge to the feed forward rate distortion. For ergodic and stationary sources, we show that for any n, the rate Rn(D)=1/n min I(X̂n→Xn) is achievable, where the minimization is taken over the transition conditioning probability p(x̂n|xn) such that E[d(Xn, X̂n)] ≤ D. The limit of Rn(D) exists and is the feed forward rate distortion. We follow Gallager's proof where there is no feed forward, and, with appropriate modification, obtain our result. We provide an algorithm for calculating Rn(D) using the alternating minimization procedure, and present several numerical examples.