Memristive Data Ranking

Sorting is a fundamental operation in many large-scale data processing applications. In big data computing, sorting imposes a massive requirement on the available memory bandwidth because of its natural demand for pairwise comparison. This high bandwidth requirement often leads to a significant degradation in performance and energy-efficiency. Processing-in-memory has been examined as an effective solution to the memory bandwidth problem for SIMD and data-parallel operations, which does not necessarily solve the bandwidth problem for pairwise comparison. This paper proposes a viable hardware/software mechanism for performing large-scale data ranking in memory with a bandwidth complexity of O(1). Large-scale comparison that forms the core computation of sorting algorithms is reformulated in terms of novel bit-level operations within the physical memory arrays for in-situ ranking, thereby eliminating the need for any pairwise comparison outside the memory arrays. The proposed mechanism, called RIME, provides an API library granting the user application sufficient control over the fundamental operations for in-situ ranking, sorting, and merging. Our simulation results on a set of high-performance parallel sorting kernels indicate 12.4–50.7× throughput gains for RIME. When used for ranking and sorting in a set of database applications, graph analytics, and network processing, RIME achieves more than 90% energy reduction and 2.3–43.6 × performance improvements.