PhD student Vasileios Zois at the University of California, Riverside publishes a research paper explaining how UPMEM PIM solution accelerates multi-criteria search on large datasets.
Below is the abstract of the paper, entitled Massively Parallel Skyline Computation For Processing-In-Memory Architectures. The submission and reviews can be seen on the website of the International Conference on Parallel Architectures and Compilation Techniques (PACT 2018).
Authors :
Vasileios Zois (University of California, Riverside) ; Divya Gupta (UPMEM, SAS); Vassilis J. Tsotras (University of California, Riverside); Walid A. Najjar (University of California, Riverside); Jean-Francois Roy (UPMEM, SAS)
“Processing-In-Memory (PIM) is an increasingly popular architecture aimed at addressing the `memory wall’ crisis by prioritizing the integration of processors within DRAM. It promotes low data access latency, high bandwidth, massive parallelism, and low power consumption. The skyline operator is a known primitive used to identify those multi-dimensional points offering optimal trade-offs within a given dataset. For large multidimensional dataset, calculating the skyline is extensively compute and data intensive. Although, PIM systems present opportunities to mitigate this cost, their execution model relies on all processors operating in isolation with minimal data exchange. This prohibits direct application of known skyline optimizations which are inherently sequential, creating dependencies and large intermediate results that limit the maximum parallelism, throughput, and require an expensive merging phase.
In this work, we address these challenges by introducing the first skyline algorithm for PIM architectures, called \textit{DSky}. It is designed to be massively parallel and throughput efficient by leveraging a novel work assignment strategy that emphasizes load balancing. Our experiments demonstrate that it outperforms the state-of-the-art algorithms for CPUs and GPUs, in most cases. \textit{DSky} achieves to 1 higher throughput compared to the state-of-the-art solutions on competing CPU and GPU architectures. Furthermore, we showcase \textit{DSky’s} good scaling properties which are intertwined with PIM’s ability to allocate resources with minimal added cost. In addition, we showcase an order of magnitude better energy consumption compared to CPUs and GPUs. Despite our focus on the skyline problem, our work provides also the skeleton for a general parallel framework suitable for developing other important data processing applications on PIM systems.”