NCAM: Near-Data Processing for Nearest Neighbor Search
Preprint
Abstract
Deep down in many applications like natural language processing (NLP), vision, and robotics is a form of the k-nearest neighbor search algorithm (kNN). The kNN algorithm is primarily bottlenecked by data movement, limiting throughput and incurring latency in these applications. While there do exist well bounded kNN approximations that improve the performance of kNN, these algorithms trade-off accuracy and quickly degrade into linear search for high dimensionality. To address data movement, we designed the nearest neighbor content addressable memory (NCAM) which employs processing in-memory (PIM) to eliminate costly data transfers, and provides exact nearest neighbor search. NCAMs benefit from the modularity offered by 3D die-stacking technology which allows us to side-step the issues of direct integration with DRAM dies. The NCAM benefits from the higher density and speeds of emerging memory technologies and interfaces. We characterize a state-of-the-art software kNN implementation and expose the shortcomings of approximate kNN search. We present a full NCAM design and estimate its performance using post-placement and route estimates, and we show that its power characteristics are compatible with emerging memory substrates. We then evaluate energy efficiency and latency compared to modern multi-core CPUs and GPGPU platforms using parameters typical of mobile and server workloads. Our simulation results show that the NCAM can achieve up to 160x throughput per watt and three orders of magnitude latency improvement over a NVIDIA Titan X GPU for server workloads, and ~2413x throughput per watt and ~94.5x latency improvements over a multi-core Intel E5-2620 CPU. Finally, we show that the NCAM is not limited to just kNN and can be generalized to act as a content addressable memory (CAM) or ternary-CAM (TCAM).Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Near-Data Processing: Insights from a MICRO-46 WorkshopIEEE Micro, 2014
- An Efficient and Scalable Semiconductor Architecture for Parallel Automata ProcessingIEEE Transactions on Parallel and Distributed Systems, 2014
- Neural Codes for Image Retrieval2014
- Semi-Supervised Hashing for Large-Scale SearchIEEE Transactions on Pattern Analysis and Machine Intelligence, 2012
- Hybrid memory cube (HMC)2011
- LDAHash: Improved Matching with Smaller DescriptorsIEEE Transactions on Pattern Analysis and Machine Intelligence, 2011
- A survey of content-based image retrieval with high-level semanticsPattern Recognition, 2007
- Distinctive Image Features from Scale-Invariant KeypointsInternational Journal of Computer Vision, 2004
- Computational RAM: implementing processors in memoryIEEE Design & Test of Computers, 1999
- A case for intelligent RAMIEEE Micro, 1997