Collaborative Research: OAC Core: Efficient Indexing and Similarity Searches Exploiting Processing-in-Memory Architectures for Memory-Bound Scientific Workloads

Northern Arizona University, Flagstaff AZ

Investigators

Abstract

Modern scientific experiments and simulations generate enormous quantities of data. As a result, scientists in many fields need to process large scale datasets using a range of data analytics tools. Many such tools conduct computations that are data-intensive, which mean that they perform operations on a large quantity of data elements per unit time (rather than few data operations per unit time). These computations are typically memory-bound, implying that there is a very high ratio of memory operations to compute operations, and in this case, insufficient memory bandwidth (measured as the number of memory operations that can be carried out in a fixed time interval) creates a bottleneck. This means that multiple processors cannot access the data as quickly as they would like and so this limits the utilization of the processors which decreases performance. To address the above challenges, this project focuses on high performance data analytics by leveraging Processing-in-Memory (PIM) systems by performing data analytics inside memory chips. The PIM paradigm enables a new opportunity for designing efficient algorithms that can address these modern scientific datasets. With the advent of PIM hardware by several vendors, there is an opportunity to exploit real hardware and study the trade-offs of using this new paradigm for processing scientific datasets. PIM addresses the high energy and data movement costs between the CPU and memory by placing computational power near memory, thus limiting the need to perform all computations on the CPU. Moreover, programming real PIM systems is challenging for scientists due to complicated interfaces. This project will advance cyberinfrastructure research and will design new similarity search algorithms for point and polygon datasets for scientific fields such as geoscience, pathology, astronomy, and solar physics. Similarity searches find similar objects to a query object and provide the foundations for many data analytics tools used by scientists. By leveraging the proposed techniques, researchers in many science and engineering fields will be able to easily adapt their scientific applications to PIM hardware. This project will provide training and research projects for graduate students. Educational materials related to the research objectives will be developed, deployed in the classroom, and then disseminated through educational workshops presented at parallel computing venues.  This project will examine efficient indexing and similarity searches on high-dimensional points and polygons that are common to many scientific workloads which require optimizations at different levels, including: I/O, algorithmic innovations, and optimized communication patterns. The overarching goal is to advance new algorithmic designs that exploit the changing landscape of memory hardware. PIM-aware data structures including the R-tree, KD-tree, locality sensitive hashing, and product quantization will be designed and implemented. Range searches, similarity searches, and K-Nearest Neighbor searches for UPMEM PIM systems will be developed. For performance modeling of core algorithms, the project will leverage Roofline and Iso-Efficiency analysis on the PIM system. From the programmability and productivity perspective, the projectalso proposes to develop a communication-efficient library and a MapReduce-like programming interface for search-and-refine workloads. Broader impacts of this project include training graduate students, the dissemination of open source software, and the development, evaluation, and dissemination of pedagogic materials that train students to use PIM architectures. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.