#43 Massively Parallel Skyline Computation For Processing-In-Memory Architectures


More

  • Bin Ren

  • Jean Luc Gaudiot (UCI)

Accepted

[PDF] Submission (5.2MB) Apr 14, 2018, 5:37:18 PM UTC · ca59a9752349d3015613c3ac9558aa3033af0e6cfa4ed7a8f634d9e240bb2ed0ca59a975

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 $2\times$ to $14\times$ 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.

V. Zois, D. Gupta, V. Tsotras, W. Najjar, J. Roy

To edit this submission, sign in using your email and password.

[Text] Reviews and comments in plain text