SkyFlow: Heterogeneous streaming for skyline computation using FlowGraph and SYCL

Jose Carlos Romero, Angeles Navarro, Andres Rodrıguez, Rafael Asenjo
Department of Computer Architecture, University of Malaga, Spain
Future Generation Computer Systems, 2022


   title={SkyFlow: Heterogeneous streaming for skyline computation using FlowGraph and SYCL},

   author={Romero, Jose Carlos and Navarro, Angeles and Rodr{‘i}guez, Andr{‘e}s and Asenjo, Rafael},

   journal={Future Generation Computer Systems},




Download Download (PDF)   View View   Source Source   



The skyline is an optimization operator widely used for multi-criteria decision making. It allows minimizing an n-dimensional dataset into its smallest subset. In this work we present SkyFlow, the first heterogeneous CPU+GPU graph-based engine for skyline computation on a stream of data queries. Two data flow approaches, Coarse-grained and Fine-grained, have been proposed for different streaming scenarios. Coarse-grained aims to keep in parallel the computation of two queries using a hybrid solution with two state-of-the-art skyline algorithms: one optimized for CPU and another for GPU. We also propose a model to estimate at runtime the computation time of any arriving data query. This estimation is used by a heuristic to schedule the data query on the device queue in which it will finish earlier. On the other hand, Fine-grained splits one query computation between CPU and GPU. An experimental evaluation using as target architecture a heterogeneous system comprised of a multicore CPU and an integrated GPU for different streaming scenarios and datasets, reveals that our heterogeneous CPU+GPU approaches always outperform previous only-CPU and only-GPU state-of-the-art implementations up to 6.86x and 5.19x, respectively, and they fall below 6% of ideal peak performance at most. We also evaluate Coarse-grained vs Fine-Grained finding that each approach is better suited to different streaming scenarios.
No votes yet.
Please wait...

Recent source codes

* * *

* * *

HGPU group © 2010-2023 hgpu.org

All rights belong to the respective authors

Contact us: