Accelerating <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math> </inline-formula>-Medians Clustering Using a Novel 4T-4R RRAM Cell

Abstract

Clustering is a crucial tool for analyzing data in virtually every scientific and engineering discipline. The U.S. National Academy of Sciences has recently announced “the seven giants of statistical data analysis” in which data clustering plays a central role. This report also emphasizes that more scalable solutions are required to enable time and space clustering for the future large-scale data analyses. As a result, hardware and software innovations that can significantly improve energy efficiency and performance of the data clustering techniques are necessary to make the future large-scale data analysis practical. This paper proposes a novel mechanism for computing bit-serial medians within resistive RAM arrays with no need to read out the operands from memory cells. We propose a novel four-transistor, four-memristor memory cell that enables in situ median computation within the data arrays. (If necessary, the proposed cell could be used as four ordinary one-transistor, one-memristor memory cells to store four bits of information.) The proposed hardware is used to accelerate a data clustering library using breast cancer samples, indoor localization, and the U.S. Census data sets, as well as two applications using k-means clustering. Our simulation results for the library indicate an average performance improvement of 15.5× and an energy reduction of 28.5× over a baseline CPU system. Also, we observe an overall speedup of 5.8× with an energy improvement of 14.1× over a baseline processing-in-memory accelerator. For the k-means applications, we observe speedups of 45.7× and 1.5× with respective energy improvements of 49.5× and 1.3× as compared with the CPU baseline.