SkyAlign: a portable,work-efficient skyline algorithm for multicore and GPU architectures |
| |
Authors: | Kenneth S. Bøgh Sean Chester Ira Assent |
| |
Affiliation: | 1.Aarhus University,Aarhus N,Denmark;2.Norwegian University of Science and Technology (NTNU),Trondheim,Norway |
| |
Abstract: | The skyline operator determines points in a multidimensional dataset that offer some optimal trade-off. State-of-the-art CPU skyline algorithms exploit quad-tree partitioning with complex branching to minimise the number of point-to-point comparisons. Branch-phobic GPU skyline algorithms rely on compute throughput rather than partitioning, but fail to match the performance of sequential algorithms. In this paper, we introduce a new skyline algorithm, SkyAlign, that is designed for the GPU, and a GPU-friendly, grid-based tree structure upon which the algorithm relies. The search tree allows us to dramatically reduce the amount of work done by the GPU algorithm by avoiding most point-to-point comparisons at the cost of some compute throughput. This trade-off allows SkyAlign to achieve orders of magnitude faster performance than its predecessors. Moreover, a NUMA-oblivious port of SkyAlign outperforms native multicore state of the art on challenging workloads by an increasing margin as more cores and sockets are utilised. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|