RT Journal Article
T1 SkyFlow: heterogeneous streaming for skyline computation using FlowGraph and SYCL
A1 Romero, José Carlos
A1 González-Navarro, María Ángeles
A1 Rodríguez-Moreno, Andrés
A1 Asenjo-Plaza, Rafael
K1 Lenguajes de programación
K1 Sistemas de informacion
K1 Sistemas de soporte a la decisión
AB 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.86×and 5.19×, 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.
PB Elsevier
YR 2022
FD 2022-11-24
LK https://hdl.handle.net/10630/26397
UL https://hdl.handle.net/10630/26397
LA eng
NO Romero, J. C., Navarro, A., Rodríguez, A., & Asenjo, R. (2023). SkyFlow: Heterogeneous streaming for skyline computation using FlowGraph and SYCL. Future Generation Computer Systems, 141, 269-283.
NO This work was partially supported by the Spanish projects PID2019-105396RB-I00, UMA18-FEDERJA-108 and P20-00395-R.  //   Funding for open access charge: Universidad de Málaga / CBUA .
DS RIUMA. Repositorio Institucional de la Universidad de Málaga
RD 21 ene 2026