Hamming Distance Computation in Unreliable Resistive Memory

Enabled by new storage mediums, Computation-in-Memory is a novel architecture thathas shown great potential in reducing the burden of massive data processing by bypassingthe communication and memory access bottleneck. Suggested by Cassuto and Crammer,allowing for ultra-fast Hamming distance computations to be performed in resistivememory with low-level conductance measurements has the potential to drastically speed upmany modern machine learning algorithms. Meanwhile, Hamming distance Computationin-Memory remains a challenging task as a result of the non-negligible device variabilityin practical resistive memory. In this thesis, as a follow-up to the work from Cassuto andCrammer, we study memristor variability due to two distinct sources: resistance variation,and the non-deterministic write process. First, we introduce a technique for estimating theHamming distance under resistance variation alone. Then, we propose error-detection anderror-correction schemes to deal with non-ideal write process. We then combine these resultsto concurrently address both sources of memristor variabilities. In order to preservethe low latency property of Computation-in-Memory, all of our approaches rely on only asingle vector-level conductance measurement. We use so-called inversion coding as a keyingredient in our solutions and we prove the optimality of this code given the restrictionson bit-accessible information. Lastly, we demonstrate the efficacy of our approaches on thek-nearest neighbors classifier